読者です 読者をやめる 読者になる 読者になる

Mae向きなブログ

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

Problem 214(その2)

昨日に引き続き、Project EulerProblem 214(日本語)です。
いろいろと調べてみると、以下のページを見つけました。

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

214_1.rb