Project EulerのProblem 70(日本語)です。
070.rb
5/20に解いたProblem 69と似た問題でした。解き方についても悩んだのですが、一番、悩んだのは小数点演算です。実行すると9708131と出力されていたのですが、この間違いの原因を突きとめるにの多くの時間を費やしてしまいました。
結局、原因はphi関数の作り方でした。間違った答えを出すphi関数は以下です。
def phi arr
n = arr.reduce(:*)
(n * arr.inject(1){|result, item|
result*(1-1.0/item)
}).to_i
endこの関数に、[2687, 3613]*1を渡すと、9701831が返ってきます。正確には9701832なので、このわずかな誤差が誤答に繋がっていたのでした。phi関数をを利用して作成していれば、小数点演算を含まないため、今回のように悩むことはなかったのにと思います。
しかし、間違いを解決しようといろいろ検索したところ、下記の参考サイトで下限と上限を設定することができ、実行時間を大幅に短縮させるという、いいこともありました。
解き方は、他の多くの方と同様、nを2つの素数の積と考えています。を最大にするには、nが素数の方が望ましいのですが、
がnが置換したものになるという条件を満たすものはありませんでした。
*1:積は9708131
