Project EulerのProblem 214(日本語)です。
久しぶりにProject Eulerを解いてみました。といっても、今日から解きはじめたわけではなくて、昨年末くらいから考えては諦め、諦めては考えというのを繰り返していました。1/19にエラトステネスの篩について書いていますが、これもこの問題を高速に解くために必要だと思ったからです。
当初は、各素数から1を引いた数に対して、オイラーのφ関数を計算して求めようと思っていましたが、数が大きくなると素因数分解するだけでも相当の時間を要してしまいます。結局、id:inamori さんが書かれているように、エラトステネスの篩のように、素数pの倍数を(p-1)/p倍するような方法に変更しました。しかしこれでも100分程度は要しています。更なる改善が必要そうです。
214.rb
追記(2013/02/04)
214.rbは非常に効率が悪いです。実行時間を大幅に短縮できる方法を2013/02/04の記事で紹介しています。
