Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

Problem 69

Project EulerProblem 69(日本語)です。

069-1.rb

問題文を読んで、そのままプログラムにしたのが069-1.rbです。phi関数を作成し、ループを回していますが、実行してみると相当時間がかかります。あまりにも時間がかかりすぎるため、途中で実行を中止しました。

069-2.rb

次に作ったものが、069-2.rbです。「オイラーのφ関数 - Wikipedia」をみると、


\varphi(n)=n \prod_{k=1}^{d}(1-\frac{1}{p_k})

と表されるので、

\frac{n}{\varphi(n)} = \frac{1}{\prod_{k=1}^{d}(1-\frac{1}{p_k})}

の最大値を求める方法で作ってみました。数式中の文字については、Wikipediaを参照してください。
この方法だと、1分ほどで実行することができるようになりました。

069.rb

しかし結局は、以下のように簡単にできるんですね。「Problem 69 - オイラーの関数 - ボクノス」を参考にさせて頂きました。今回の問題は、プログラミングとは何か?とか問題解決能力とは何か?というようなことを考えされられました。