project euler 46

오일러 프로젝트 46 번

크리스티안 골드바흐는 모든 홀수인 합성수를 (소수 + 2×제곱수)로 나타낼 수 있다고 주장했습니다.

    9 = 7 + 2×12
    15 = 7 + 2×22
    21 = 3 + 2×32
    25 = 7 + 2×32
    27 = 19 + 2×22
    33 = 31 + 2×12

이 추측은 잘못되었음이 밝혀졌습니다.

위와 같은 방법으로 나타낼 수 없는 가장 작은 홀수 합성수는 얼마입니까?

http://euler.synap.co.kr/prob_detail.php?id=46

어떤 자연수 n이 골드바흐의 추측을 만족하지 않는다면, n보다 작은 소수들의 집합 Pn 과 n보다 작은 거듭제곱수의 집합 Sn의 각 원소를 이용해서 위 식을 적용. 이를 만족하는 원소의 쌍이 존재하지 않음을 보면 된다. 물론 이는 만만한 작업은 아니지만, 답은 생각보다 작은 수이다.

def memoize(f):
    cache = {}
    def inner(a):
        if a in cache:
            return cache[a]
        result = f(a)
        cache[a] = result
        return result
    return inner

@memoize
def is_prime(n):
    if n < 2:
        return False
    if n is 2 or n is 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    if n < 9:
        return True
    k = 5
    l = n **0.5 
    while k <= l:
        if n % k == 0 or n % (k+2) == 0:
            return False
        k += 6
    return True


def primes_up_to(n):
    return [2] + [x for x in range(3, n, 2) if is_prime(x)]


def squared_up_to(n):
    return [2*x*x for x in range(1, int(n**0.5) + 2)]


def test(n):
    for p in primes_up_to(n)[::-1]:
        for s in squared_up_to(n):
            if p + s == n:
                return True

    return False


def e46():
    k = 5
    while True:
        if not is_prime(k) and not test(k):
            print(k)
            break
        k += 2

%time e46()

# 5777
# Wall time: 1.93 s