[Project Euler] Problem 27

원문: Problem 27

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² + 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.

오일러는 놀랄 만한 2차 방정식을 발표했다:

n² + n + 41

그 식이 n = 0부터 39까지 연속적인 40개의 소수를 만든다는 것을 밝혀냈다. 그러나 n = 40일 때는, 402 + 40 + 41 = 40(40 + 1) + 41이 41로 나누어질 수 있고, 확실히 n = 41일 때는, 41² + 41 + 41이 명확하게 41로 나누어질 수 있다.

컴퓨터를 사용해서, 놀라운 식 n² − 79n + 1601이 발견 되었는데, 이것은 n = 0부터 79까지 연속적인 80개의 소수를 만들 수 있다. 그 계수들인 -79와 1601의 곱은 -126479이다.

다음 형태의 2차 방정식을 고려할 때:

n² + an + b, 단, |a| < 1000 와 |b| < 1000 일 때

여기에서 |n| 은 n의 절대값이다.
예를 들어, |11| = 11 그리고 |−4| = 4 이다.

n = 0부터 시작하여 n의 연속적인 값에 대해서, 가장 많은 소수의 개수를 생산하는 2차 방정식의 계수인 a와 b의 곱을 찾아라.

Python

import factor # 인수 분해 모듈. 이전에 구현해둔 것임. 리턴값은 인수를 키로 하고 개수를 값으로 하는 사전

max_a = 0 
max_b = 0 
max_n = 0 
for a in range(-999, 1000):
    for b in range(-999, 1000):
        n = 0 
        while True:
            prime = n**2 + a * n + b 
            if prime in factor.factor(prime):
                n += 1
            else:
                break
        if n > max_n:
            max_n = n 
            max_a = a 
            max_b = b 

print(max_a * max_b)

접기