Python
ProjectEuler

Project Euler 27「二次式素数」

問題の意味がなかなか理解できずパニックになったのは内緒。

Problem 27 「二次式素数」

オイラーは以下の二次式を考案している:
n^2 + n + 41.
この式は, n を0から39までの連続する整数としたときに40個の素数を生成する. しかし, n = 40 のとき 402 + 40 + 41 = 40(40 + 1) + 41 となり41で割り切れる. また, n = 41 のときは 412 + 41 + 41 であり明らかに41で割り切れる.
計算機を用いて, 二次式 n^2 - 79n + 1601 という式が発見できた. これは n = 0 から 79 の連続する整数で80個の素数を生成する. 係数の積は, -79 × 1601 で -126479である.
さて, |a| < 1000, |b| ≤ 1000 として以下の二次式を考える (ここで |a| は絶対値): 例えば |11| = 11, |-4| = 4である.
n^2 + an + b
n = 0 から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数 a, b の積を答えよ.

def hoge(num_a, num_b):
    f = lambda n, a, b : n ** 2 + a * n + b
    lst_prime = set() # 判定済みの素数格納用
    ans, max_cnt = 0, 0
    for a in range(-num_a + 1, num_a):
        for b in range(-num_b + 1, num_b):
            n = 0
            while True:
                x = f(n, a, b)
                if x in lst_prime or check_prime(x):
                    lst_prime.add(x)
                    n += 1
                else:
                    break
            if max_cnt < n:
                max_cnt = n
                ans = a * b
    return ans

def check_prime(n): #素数判定用関数
    if n < 1:
        return False
    else:
        for i in range(2, (n//2)):
            if n % i == 0:
                return False
        return True

print(hoge(1000,1001))

特に捻りもなく問題通りに愚直スタイル。ちょっと遅い。