のてすきあ − 完全独習非プログラマー −

Haskell で Project Euler を解く素人遊び

Problem 27

n2 + an +b に n = 0,1,2,...と順に代入したときに、連続して素数を生成する式を作りたい。|a| <= 1000, |b| < 1000の範囲で、最も連続して素数を生成する組み合わせ (a,b)を探しだし、その積 ab を求める。
注意:a,bは負の数でも良い。

まず、n=0においても式は素数を生成しなければならないから、bは素数と分かる。さらに、n=1の時にも式が素数を生成することから、aは奇数のみ考えれば良い。(厳密にはb=2の場合を別に扱わなければならないが、それは後々得られた答えが2000以下だった場合に考慮すれば事足りる)

あとは、a,bの値を振っていくだけなので、リスト内包表記が便利だ。nを0から順に代入した時に、どこまで連続して素数を生成するかは、lengthで知ることができる。素直にプログラムを書けば問題は解けるが、意外に時間がかかってしまった。少し考えたが、本質的な効率化の手段は思い浮かばなかった。何か良い方法があるだろうか?

意外と計算が重い★