project euler 37

오일러 프로젝트 37 번

소수 3797에는 왼쪽부터 자리수를 하나씩 없애거나 (3797, 797, 97, 7) 오른쪽부터 없애도 (3797, 379, 37, 3) 모두 소수가 되는 성질이 있습니다.

이런 성질을 가진 소수는 단 11개만이 존재합니다. 이것을 모두 찾아서 합을 구하세요.

(참고: 2, 3, 5, 7은 제외합니다)

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

조건에 맞는 소수들을 세면서 11개가 될때까지 검사를 수행해야 한다. 왼쪽에서 한자리씩 없애거나 오른쪽에서 한자리씩 없애는 것은 간단한 편인데 (상용로그를 이용하면 쉽다) 시간이 적지 않게 소모된다. 성능을 최적화하는 방법 몇 가지를 살펴보자.

  1. 숫자를 하나씩 제거해나가면 원래 값보다 계속 작아진다. 따라서 소수 판별함수는 메모이제이션한다.
  2. 문제의 조건에 의해 1의 자리는 3, 7 중 하나의 숫자만 올 수 있다. 이걸 미리 검사하면 수행시간이 절반으로 줄어든다.
  3. 마찬가지로 첫자리에는 2가 올 수 있지만, 그외 나머지 자리에는 짝수 숫자가 올 수 없다. 이 부분이 엄청나게 많은 경우를 제거한다.

2, 3의 제약 조건이 없을 때 약 6~7초 가량 걸리던 것이 저 제약 조건만으로 500ms대로 단축됐다.

from math import log10

def rFront(n):
    a = [n]
    while n > 0:
        l = 10**int(log10(n))
        n = n % l
        a.append(n)
    return a[1:-1]

def rRear(n):
    a = [n]
    while n > 0:
        n = n // 10
        a.append(n)
    return a[1:-1]

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

@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 check(n):

    if n % 10 not in (3, 7):
        return False

    s = str(n)[1:]
    for c in "02468":
        if c in s:
            return False

    if is_prime(n):
        for i in rFront(n):
            if not is_prime(i):
                return False
        for i in rRear(n):
            if not is_prime(i):
                return False
    else:
        return False
    return True

def e37():
    res = []
    a = 11
    c = 0
    while len(res) < 11:
        if check(a):
            res.append(a)
        a += [2, 4][c]
        c = (c + 1) % 2
    print(sum(res))

%time e37()
# 748317
# Wall time: 565 ms