問題
オイラーは以下の驚くべき二次式を見いだし、
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から始めて1ずつ増やしていくとき、連続で最も多く素数を生成する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の範囲をそれぞれ、奇数と素数に限定することで十分速くなりました。