프로젝트 오일러 027

문제

27번 문제

연속되는 <var>n</var>에 대해 가장 많은 소수를 만들어내는 이차식

사이냅소프트

접근

주어진 식은 2차식이며, 1차항의 계수와 상수를 변경하여 2차식을 만들고, n = 0, 1, 2, 3,∙∙∙ 이렇게 증가시켜가면서 연속한 가장 많은 소수를 만들어 내는 식을 찾는 문제입니다.

어떤 2차식에서 꼭지점의 x좌표를 k라고 할 때, f(k + w) = f(k - w) 이므로, 0부터 가장 길게 소수를 만들어내는 2차식은 같은 모양 중에서는 꼭지점이 최대한 오른쪽으로 평행이동한 모양인 경우를 생각하면 됩니다.

문제에서 제시한 식 [n^2 + n + 41]은 39개의 소수를 만들 수 있다고 했는데, 이 식의 포물선을 오른쪽으로 39만큼 평행이동 시킨 [n^2 - 77n + 1523]은 78개의 연속한 소수를 만들 수 있습니다.

자, 그런데 a, b의 절대값이 1,000보다 작다고 했으니, -1000 < a < 1000, -1000 < b < 1000 으로 검사해봐야 하는 a, b의 조합이 4백만이나 되어서 시간이 많이 걸릴 것입니다. '포물선이 평행이동했을 때'의 모양을 생각해보면 꼭지점이 제1사분면에 있어야 합니다. 따라서 다음과 같은 조건을 세울 수 있습니다.

1. a는 음수입니다.
2. b는 [a^2 / 4]보다는 크면서 1,000보다는 작습니다.

이 두 개의 조건으로도 a, b 의 범위를 충분히 줄일 수 있습니다. a가 커지면 커질수록 들여다봐야하는 b의 범위가 크게 줄어들게 됩니다. a * a / 4 > 1000 이되는 시점은 a가 -64가 되는 시점입니다. 실제로는 a의 범위도 극히 좁기 때문에 답은 매우 빠르게 구할 수 있습니다.

from typing import Callable


def isprime(n: int) -> bool:
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    if n < 10:
        return True
    k, l = 5, int(n**0.5 + 1.5)
    while k < l:
        if n % k == 0 or n % (k + 2) == 0:
            return False
        k += 6
    return True


def make_eq(a: int, b: int) -> Callable[[int], int]:
    return lambda n: n * n + a * n + b


def process(f: Callable[[int], int]) -> int:
    result, i = 0, 0
    while True:
        if isprime(f(i)):
            result += 1
            i += 1
            continue
        return i


def main():
    res, m = (0, 0), -1
    for a in range(-999, -1):
        for b in range(int(a * a / 4 + 1.5), 1000):
            f = make_eq(a, b)
            r = process(f)
            if r > m:
                m = r
                res = (a, b)
    print(res[0] * res[1], res)


if __name__ == "__main__":
    main()