Project Eulerをhaskellで練習していく日記: Problem 27

問題

オイラーは以下の驚くべき二次式を見いだし、
n^2 + n + 41
これがn=0〜39まで全て素数となることを発見した。
n=40 の場合、40^2 + 40 + 41 = 40*(40 + 1) + 41となり、これは41で割り切れる。
また、n=41の場合、41^2 + 41 + 41も41で割り切れる。

また、
n^2 − 79n + 1601
は n=0〜79まで全て素数となる。
この時、この二次式の係数の積は、(-79) * 1601 = −126479 となる。

以下の二次式で、
n^2 + an + b, where |a| < 1000 and |b| < 1000
n = 0から始めて１ずつ増やしていくとき、連続で最も多く素数を生成するa,bの積を求めよ。

回答

import qualified List as L

-- 式 n^2+a*n+bで、b<0にすると、n=0の時に負の値になり素数とは言えない。したがって、b>0としてよい。
-- またn=0でも素数になることを考えると、bは素数。        
-- またn=1でも奇素数になることを考えると、aは奇数。

-- 素数判定
isprime x
 | x<2 = False
 | otherwise = all (\y->x `mod` y/=0) [2..truncate $ sqrt $ fromIntegral x]

-- a,bを与えて、何個まで素数を生成できるかを数える関数
numofprimes a b = length $ takeWhile (\x->isprime (snd x)) $ L.sort [(n,n^2+a*n+b)| n<-[0..b-1]]

-- a,bを与えて、高々何個まで素数を生成できるかを返す関数
ubound a b = if b-a>0 then min (abs b) (b-a)
                       else abs b

-- a,bの組の列を受け取って、最多の素数を生成するa,bを求める関数
-- 引数は「それまでの最大個数」「その最大を得たa,bの組」「(a,b)の列」
findmax u p [] = (fst p)*(snd p)
findmax u p (c:cs) = if ub<u then findmax u p cs
                             else let n = numofprimes a b in
                                  if u<n then findmax n c cs
                                         else findmax u p cs

                       where a = fst c
                             b = snd c
                             ub = ubound a b

main = do 
     print $ findmax 0 (0,0) [(a,b) | a<-[-999..999], b<-[42..999], odd a, isprime b]

感想

探索するa,bの範囲をそれぞれ、奇数と素数に限定することで十分速くなりました。