昨日に引き続き、Project EulerのProblem 214(日本語)です。
いろいろと調べてみると、以下のページを見つけました。
効率よくオイラーのφ関数が計算できるようです。実際、自分でもトレースしてみましたが計算できています。しかし自分ではとても考え出せそうにありません。
昨日の実行時間は100分程度要しているのに対し、改訂版では1分程度で実行できています。昨日のプログラムはRubyだから遅いのではなく、アルゴリズムが悪いだけでした。アルゴリズムの重要性を再確認することができました。
