project euler 50

오일러 프로젝트 50 번

41은 소수이면서 다음과 같은 6개의 연속된 소수의 합으로도 나타낼 수 있습니다.

    41 = 2 + 3 + 5 + 7 + 11 + 13

이것은 100 이하에서는 가장 길게 연속된 소수의 합으로 이루어진 소수입니다.

1000 이하에서는 953이 연속된 소수 21개의 합으로 가장 깁니다.

1백만 이하에서는 어떤 소수가 가장 길게 연속되는 소수의 합으로 표현될 수 있습니까?

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

최적화가 매우 중요한 문제이다. 1분 이내에 푸는 방법을 찾기도 꽤 벅찼다.

소수의 채를 만들고 다시 소수의 누적합 리스트를 만든다. 이 리스트를 S라 할 때 S[j] - S[i]는 i+1 번째 소수부터 j 번째 소수까지의 합이 된다.

즉 이 간격이 가장 길면서 그 차가 소수가 되는 오프셋들을 찾으면 된다. 소수는 200만까지 범위에서 찾고 (그 이상까지 가는 경우에 아이고 의미없다) 요 사이에서 오프셋값을 이용하여 찾아보도록 한다.

소수 채 알고리듬은 Robert William Hanks가 개발한 것으로 아래 페이지에 소개되어 있다. (순수 파이썬 알고리듬중에서는 가장 빠른 것으로 알려져있다.)

http://stackoverflow.com/questions/17773352/python-sieve-prime-numbers

def prime_sieve(bound):
    sieve = [True] * (bound//2)
    for i in range(3, int(bound**.5)+1, 2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((bound-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in range(1, bound//2) if sieve[i]]


limit = 1000000

def e50():
    primes = prime_sieve(limit)
    pset = set(primes)
    l = len(primes)
    sum_of_primes = [0] + [0] * l
    for i in range(1, l+1):
        sum_of_primes[i] = sum_of_primes[i-1] + primes[i-1]

    sum_of_primes = [x for x in sum_of_primes if x <= limit * 2]



    for i in range(len(sum_of_primes)):
        for j in range(i):
            k = sum_of_primes[- i + j - 1] - sum_of_primes[j]
            if k <= limit and k in pset:
                print(k, i, j)
                return


%time e50()
# 997651 210 3
# Wall time: 307 ms