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 $です.プログラムを組むまでもないんですね.