Project Euler #37 - 잘라도 소수인 소수

프로젝트 오일러 37번
3797은 왼쪽에서 잘라도, 오른쪽에서 잘라도 계속 소수이다. 3, 37, 379, 3797 / 7, 97, 797, 3797
이런 수가 11개 있는데, 이들을 다 더하면?

1번 방법 - 0.2초
2번 방법 - 0.05초

우선 1번 방법

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

pn = rwh_primes1(1000000)
pns = set(pn)

rs = []
for p in pn:
    ps = str(p)
    chk = 1
    for i in range(1,len(ps)):
        if int(ps[:i]) not in pns or int(ps[i:]) not in pns:
            chk = 0
            break
    if chk == 1 and p > 10:
        rs.append(p)
        if len(rs) == 11:
            print sum(rs)
            break

100만까지의 모든 소수를 만들고, 작은 것부터 하나씩 위의 조건을 만족하는지 체크한다. 11개를 다 찾으면 답을 출력하고 끝낸다. 11개를 다 못 찾았으면 아무 것도 출력하지 않는다. 아마 1000만까지 소수를 찾은 다음에 다시 시도해야겠지.


2번 방법
1자리 소수 - 2, 3, 5, 7의 왼쪽/오른쪽에 숫자를 하나씩 붙여보면서 소수가 되는지 체크한다. 그런 식으로 왼쪽에서부터 하나씩 잘라가도 계속 소수가 되는 2자리수, 3자리수, ... 오른쪽에서부터... 2자리수, 3자리수.. 를 모두 찾는다. 둘의 교집합을 찾는다.

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

pn = rwh_primes1(1000)

def chk_pn(n,pn):
    if n == 1: return False
    for p in pn:
        if n % p == 0: return False
        if p**2 > n: return True

rpn = []
stage = [3,7]
found = []
d = 1
while stage:
    for b in stage:
        for x in range(1,10):
            if chk_pn(x*10**d+b,pn): found.append(x*10**d+b)
    rpn += stage
    d += 1
    stage, found = found, []

lpn = []
stage = [2,3,5,7]
found = []
d = 1
while stage:
    for b in stage:
        for x in [1,3,7,9]:
            if chk_pn(b*10+x,pn): found.append(b*10+x)
    lpn += stage
    d += 1
    stage, found = found, []

print sum([x for x in lpn if x in rpn and x > 10])