Problem 27 (Project Euler) [原文]
オイラーは以下の二次式を考案している:
n2 + n + 41
この式は, nを0から39までの連続する整数としたときに40個の素数を生成する. しかし, n = 40のとき402 + 40 + 41 = 40(40 + 1) + 41となり41で割り切れる. また, n = 41のときは412 + 41 + 41であり明らかに41で割り切れる.
計算機を用いて, 二次式 n2 - 79n + 1601という式が発見できた. これはn = 0 から 79 の連続する整数で素数を生成する. 係数の積は, -79 × 1601 で -126479である.
さて, |a| < 1000, |b| < 1000 として以下の二次式を考える (ここで|a|は絶対値):
n2 + an + b
n=0から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数a, bの積を答えよ.
-999から999までの a, bについてのほぼ400万回のループは現実的ではないので、「枝刈り」が必要です。
n = 0 のときを考えると、bが素数であることは必須だし、n = 1, 2のときを考えると、aは2で割り切れない数であり、b は2以外の素数であることがわかります。
a の範囲はまだ狭まるそうですが、このぐらい刈っただけでも、なんとか答えはでました。
