Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

Problem 243

Ruby Euler

Project EulerのProblem 243(日本語)です。
以前、Problem 69を解いたときに、「オイラーのφ関数 - Wikipedia」について学んでいたので、これを使えばいいとは思ったのですが、ただ素直に使うだけでは実行時間がかかりすぎました。
もう一歩、自分で考えつけばいいのでしょうけど、先人の知恵を利用させてもらいました。


\begin{eqnarray}R(d) & = & \frac{\phi(d)}{d-1}\\ & = & \frac{d}{d-1}\prod_{i=1}^{}(1-\frac{1}{p_i}) \\ \end{eqnarray}

なので、

\begin{eqnarray}R(kd) & = & \frac{\phi(kd)}{kd-1}\\ & = & \frac{kd}{kd-1}\prod_{i=1}^{}(1-\frac{1}{p_i}) \\ \end{eqnarray}

なんですね。

243.rb