Project Euler 69

解答:http://codepad.org/AWFZdG1J
最後にも述べていますが,プログラムを書く必要がない問題だと分かりました.電卓があれば良いです.

解説

 次の公式(2)を使用します:
$n$を素因数分解して, $$ \begin{equation} n = {p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots {p_k}^{\alpha_k}  (p_1 < p_2 < \cdots < p_k) \tag{1} \end{equation} $$ と書けるとすると, $$ \begin{equation} \varphi(n) = n\left( 1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) \cdots \left( 1 - \frac{1}{p_k} \right) \tag{2} \end{equation} $$ 式(2)の証明は調べるといろいろ出てきます.
 式(2)の両辺を$n$で割り,逆数をとると, $$ \begin{equation} \frac{n}{\varphi(n)} = \frac{p_1 p_2 \cdots p_k}{(p_1 - 1)(p_2 - 1) \cdots (p_k - 1)} \tag{3} \end{equation} $$ と書けます.左辺は今回の問で求めるべき関数です.右辺は,式(1)で出てきた$\alpha$に依らない,素数だけの関数です.
 さらに,右辺の関数は$k$について単調増加です.従って,$n$は1,000,000以下でかつ$n = 2 * 3 * 5 * \cdots $です.プログラムを組むまでもないんですね.