오일러 프로젝트 27

오일러 프로젝트 27 번은 0부터 연속된 자연수(요즘 대수학에서는 0도 자연수에 포함시킨다하던데…)를 넣었을 때 소수를 계속만들 수 있는 이차식에 대한 문제이다. 바로 가장 긴 소수 수열을 만들 수 있는 계수의 조합을 구한다.

오일러는 다음과 같은 멋진 2차식을 제시했습니다.
 

이 식의 n에다 0부터 39 사이의 숫자를 넣으면, 그 결과는 모두 소수가 됩니다. 하지만 n = 40일 때의 값 은 40×(40 + 1) + 41 이므로 41로 나누어지고, n = 41일 때 역시 412 + 41 + 41 이므로 소수가 아닙니다.
 
컴퓨터의 발전에 힘입어 이라는 엄청난 2차식이 발견되었는데, 이것은 n이 0에서 79 사이일 때 모두 80개의 소수를 만들어냅니다. 이 식의 계수의 곱은 -79 × 1601 = -126479가 됩니다. 아래와 같은 모양의 2차식이 있다고 가정했을 때, 이 0부터 시작하는 연속된 n에 대해 가장 많은 소수를 만들어내는 2차식을 찾아서, 그 계수 a와 b의 곱을 구하세요.
 
http://euler.synap.co.kr/prob_detail.php?id=27

접근

이차식의 그래프는 포물선의 모양이다. 이 때 x가 0에서 부터 출발해서 증가할 때 -500식의 결과값이 0보다 크게, 소수를 포함하도록 하고 싶다면 포물선이 좌우 대칭인 점을 이용해서, 가능하면 포물선의 꼭지점이 1사분면에 있는 것이 유리하다. 그러면 0~n 까지가 모두 소수를 만든다고 하면 자동적으로 n~2n까지도 소수가 되기 때문이다.

따라서 포물선의 중심이 1사분면에 오기 위해서는 a는 음수, b는 -2a 보다 큰 조건 만족해야 하고 (여기서 다시 b는 1000보다 작거나 같으므로 a의 범위는 (-500…0) 이된다.), 이를 검사하면 계산량을 비약적으로 줄일 수 있다.

def is_prime(n):
    if n < 2: return False
    if n in (2, 3): return True
    if n % 2 is 0 or n % 3 is 0:
        return False
    if n < 10: return False
    k, l = 5, n ** 0.5
    while k <= l:
        if n % k == 0 or n % (k+2) == 0:
            return False
        k += 6
    return True
def make_eqation(a, b):
    return lambda x: x*x + a*x + b
def test(a:int, b:int) -> int:
    fx = make_eqation(a, b)
    c = 0
    while True:
      if fx(c):
        c += 1
      else:
        return c
def main():
    mc, result = 0, 0
    for a in range(-500, 0):
        for b in range(-2*a, 1001):
            c = test(a, b)
            if mc < c:
               mc = c
               result = a * b
    print(result)
%time main()
# Wall time: 530ms

보너스 Swift 풀이

동일한 로직의 Swift 풀이