Project Euler 27

考えたこと

Project Eulerの規約(*1)に反さない範囲で考察する.

問題の２次式は

n+an^2+b

で、これを0とその後に連続する自然数の入力nに対して素数しか返さないような関数にしたい。

今回思いついた解法は,

< 解 >

current = 0
y = 0
l = [u for u in range(100)]   
lforb = [2, 3, 5, 7] + [b for b in range(11, 1000, 2)]

def prime(l):
    for u in range(2, int(l**0.5) + 2):
        if l%u == 0:
            return 0
    else:
        return 1

for a in range(-999, 1000):
    for b in lforb:
        q = 0
        for x in l:
            p = x*x + a*x + b
            if p < 2:
                break
            elif prime(p) == 1:
                q += 1
            else:
                break
        if q > current:
            current = q
            y = a*b
print(y)

煩雑であるがある程度の工夫を施してあり1.5秒以下で答えを出せる。それらは,

1. n=0の場合を考えるたとき, bは素数でなければいけないことがわかる
   →bに対するfor文で使うlforbは素数だけを要素に持つ

2. オイラーの二次式で40, 最新の二次式で係数の絶対値を問題設定より大きくしても80個の連続する素数しか出力できない
   →考えるnは最大100で充分

3. 任意のn∈[0,100]で出力が素数にならないのならそれ以上計算しなくていい
   →2未満の数が出力されたらlに対するfor文を出る

4. 素数判定はその数の平方根以下で考えれば良い

振り返り

• 変数currentを使う方法はthreadで他の方から学習させてもらった。最初はdictを作りそこに連続して素数となった自然数の数と係数を登録する仕組みにしていたが, こちらのほうが賢く早いので.
• 下に凸である今回の関数の判別式や軸の位置で、もう少しfor文の試行回数を減らせるかと思ったが, 結局bが正であることに帰着した.

*1

...sharing solutions outside of Project Euler does not apply to the first one-hundred problems, as long as any discussion clearly aims to instruct methods, not just provide answers,...