Project EulerのProblem 69(日本語)です。
069-1.rb
問題文を読んで、そのままプログラムにしたのが069-1.rbです。phi関数を作成し、ループを回していますが、実行してみると相当時間がかかります。あまりにも時間がかかりすぎるため、途中で実行を中止しました。
069-2.rb
次に作ったものが、069-2.rbです。「オイラーのφ関数 - Wikipedia」をみると、
と表されるので、
の最大値を求める方法で作ってみました。数式中の文字については、Wikipediaを参照してください。
この方法だと、1分ほどで実行することができるようになりました。
069.rb
しかし結局は、以下のように簡単にできるんですね。「Problem 69 - オイラーの関数 - ボクノス」を参考にさせて頂きました。今回の問題は、プログラミングとは何か?とか問題解決能力とは何か?というようなことを考えされられました。