Problem 69 - Mae向きなブログ

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 - オイラーの関数 - ボクノス」を参考にさせて頂きました。今回の問題は、プログラミングとは何か?とか問題解決能力とは何か?というようなことを考えされられました。