Project Euler Problem 27

数学的にいくつか工夫をすると、だいぶ探索数が減らせる。

• 二次式にn=0を代入すれば、そもそもb自身が素数でであることはすぐにわかる。
• n=bの時は式全体はbの倍数である。よって、どんなにがんばってもn=b-1までしか連続した素数は得られない。よって、n=bの時は素数判定は必要ない。

という2点が主な工夫。これ以外にもあるかもしれないけど、すぐに思いつかなかった。2.37秒という
Pythonスクリプトとしては速いような遅いような微妙な速度で処理が終わったので、良いことにした。

#!/usr/bin/python
# -*- coding: utf-8 -*-

primes = set() # 素数集合
compos = set() # 合成数集合 0は便宜上合成数

def init_prime(n):
    global primes
    for i in range(3,n,2):
        for p in primes:
            if i % p == 0:
                break
        else:
            primes.add(i)

def is_prime(n):
    global primes,compos

    n = abs(n)

    if n in primes: return True
    if n in compos: return False

    for p in primes:
        if n % p == 0:
            compos.add(n)
            return None

    primes.add(n)
    return True


def get_n_seq(a,b):
    n = 0
    while True:
        if n >= b: break
        m = n**2 + a*n + b
        if is_prime(m):
            n += 1
        else:
            break

    return n

def main():
    init_prime(1000)
    blist  = list(primes) + [-p for p in primes]

    max_len= (0,0,0) # (n, a, b)

    for b in blist:
        for a in range(-999, 1000):
            n = get_n_seq(a,b)
            if n > max_len[0]:
                max_len = (n,a,b)

    print max_len
    print max_len[1] * max_len[2]

main()