Project Euler #50 - 연속된 소수의 합

프로젝트 오일러 50번 - consecutive prime sum

41 = 2+3+5+7+11+13 처럼 연속된 소수의 합으로 표현되는 소수가 있다.

100만 이하 소수 중, 가장 긴 소수 합으로 표현되는 것은?

두가지 방법
첫번째.
A. 소수 n에 대해 n이 최대 몇 개의 연속된 소수의 합으로 표현되는지를 찾는 함수를 정의한다
 A-1. 소수들을 더해가면서 합이 n보다 크면 앞쪽 소수를 하나씩 빼고, 합이 n보다 작으면 뒤쪽에 하나씩 더한다.
 A-2. 소수의 개수가 너무 적어지면 그만 둔다.
B. A에서 정의한 함수를 모든 n에 대해 적용한다.

두번째.
A. 2부터 시작해서 합이 100만 넘기 직전까지 소수들을 더한다. '합'들을 저장해 둔다.
 A-1. 만약, 100만 넘기 직전의 합이 소수이면 그것이 정답
 A-2. 그게 아니라면, 2부터 어디까지 더했을 때 가장 긴 sequence가 되면서 합이 소수가 되는지 찾는다. 그 길이를 maxlen에 저장해 둔다.
B. 3부터 시작해서 합이 100만 넘기 직전까지 소수들을 더한다. '합'들을 저장해 둔다.
 B-1. 만약, 100만 넘기 직전의 합이 소수이고 그것이 maxlen보다 길면 정답
 B-2. 그게 아니라면, 3부터 어디까지 더했을 때 가장 긴 sequence가 되면서 합이 소수가 되는지 찾는다. 그 길이를 maxlen에 저장해 둔다.
C. 5부터 시작해서 합이 100만 넘기 직전까지 소수들을 더한다. '합'들을 저장해 둔다.
 C-1. 만약, 100만 넘기 직전의 합이 소수이고 그것이 maxlen보다 길면 정답
 C-2. 그게 아니라면, 5부터 어디까지 더했을 때 가장 긴 sequence가 되면서 합이 소수가 되는지 찾는다. 그 길이를 maxlen에 저장해 둔다.
D. E. F. ... - 7, 11, 13부터 시작해서...
끝까지 갔으면 maxlen이 정답

첫번째 방법을 해 봤더니 예상보다 긴 sequence에서 예상보다 큰 소수가 나왔다. 그래서 두번째 방법으로 다시 코딩. 두번째 방법은 우연히 D-1에서 끝나서 빨리 답을 찾은 거라.. 정석은 아닌 듯 하다.

첫번째 방법의 코드(6초 남짓)

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]]

def maxcon(n,pn,mx):
    st = ed = 0
    sm = 0
    while True:
        if sm < n:
            sm += pn[ed]
            ed += 1
        elif sm > n:
            sm -= pn[st]
            st += 1
        elif sm == n:
            return ed - st
        if ed > mx and ed - st < mx:
            return 0

pn = rwh_primes1(1000000)
mx, mxp = 1, 1

for p in pn:
    if maxcon(p,pn,mx) > mx:
        mx = maxcon(p,pn,mx)
        mxp = p

print mxp

두번째 방법의 코드(0.05초)

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]]

N = 1000000
pnl = rwh_primes1(N)
pns = set(pnl)

l = len(pnl)

def prob():
    mxlen, mx = 1, 1
    for i in range(l):
        sm, sml = 0, []
        for j in range(i,l):
            sm += pnl[j]
            sml.append(sm)
            if sm > N:
                if sm - pnl[j] in pns and len(sml) >= mxlen:
                    return sm - pnl[j]
                break
        for k,q in enumerate(sml[::-1]):
            if q in pns:
                if len(sml) - k > mxlen:
                    mxlen, mx = len(sml)-k, q
                break
    return mx

print prob()

저장하다 날아가서 다시 쓰려니 의욕이 안 생긴다 --;