Project Euler 27

• 問題

Problem 27：Quadratic primes
Euler discovered the remarkable quadratic formula:
n^2+n+41
It turns out that the formula will produce 40 primes for the consecutive integer values 0≤n≤39. However, when n=40, 40^2+40+41=40(40+1)+41 is divisible by 41, and certainly when n=41, 41^2+41+41 is clearly divisible by 41.

The incredible formula n^2−79n+1601 was discovered, which produces 80 primes for the consecutive values 0≤n≤79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n^2+an+b, where |a|<1000 and |b|≤1000

where |n| is the modulus/absolute value of n
e.g. |11|=11 and |−4|=4
Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n=0.

• 解答例

def sieveEratosthenes(num):
    isPrime = [True] * (num + 1)
    isPrime[0] = False
    isPrime[1] = False
    primes = []
    for i in range(2, (num + 1)):
        if isPrime[i]:
            primes.append(i)
            for j in range(2 * i, (num + 1), i):
                isPrime[j] = False
    return primes
    
def isPrime(num):
    if num <= 1:
        return False
    elif num == 2 or num == 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    if not(num % 6 == 1) and not(num % 6 == 5):
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6
    
    return True

def equation(n, a, b):
    return n ** 2 + a * n + b

b = sieveEratosthenes(1000)
del b[0]

maxA = 0
maxB = 0
maxCount = 0

for y in b:
    for x in range(-y, 1000, 2):
        c = 0
        while isPrime(equation(c, x, y)):
            c += 1
        if maxCount < c:
            maxA = x
            maxB = y
            maxCount = c
            
print(maxA * maxB)