프로젝트 오일러 050

백만 이하의 소수의 리스트에서 연속된 소수의 합이 소수가 되는 가장 긴 부분열을 찾는 문제입니다. 백만 이하의 소수는 소수체를 통해 빠르게 얻을 수 있으며, 그 합 역시 백만 이하의 소수라는 단서가 있으므로, 소수 판별 함수를 사용하는 대신에 만들어진 소수체를 집합(set)으로 변환하고 멤버십 테스트를 통해 소수 여부를 판단하여 시간을 단축할 수 있습니다.

소수 리스트에서 startIndex와 endIndex를 변경해가면서 그 사이 소수들의 합이 백만을 넘지 않는 동안 소수인지를 확인하면서 가장 긴 구간을 찾으면 되기 때문에 구현 자체는 어렵지 않습니다.

from utils import seive

def main():
    s = seive(100_0000)
    m = set(s)
    res = (0, 0)
    for startIndex in range(0, len(s)-2):
        for endIndex in range(startIndex + 2, len(s)):
            t = sum(s[startIndex:endIndex])
            if t > 100_0000:
                break
            if t in m and (endIndex - startIndex) > res[0]:
                res = (endIndex - startIndex, t)
    print(res)

if __name__ == '__main__':
    main()

개선

실제로 그 합계가 한계치 이내이면서 연속열이 길게 유지되려면 작은 소수로부터 시작해야하는 경우가 많습니다. 소수 정리를 활용하면 처음 k개 소수의 합은 대략 $\frac{k^2}{2}\cdot \ln k$가량이 됩니다. 이 값이 한계값에 근사하는 k를 구한다면 대략 한계값의 제곱근 근처가됩니다. 다만 이는 대략적인 추정이므로 실제로는 이 두 배 정도의 길이까지는 탐색하는 것이 안전할 것 같습니다.

실제로, 그 합이 소수인지와는 상관없이 처음 n개 소수의 합이 백만을 넘어가는 것을 확인해보면 540개 정도로 확인됩니다. 연속열의 시작값이 2보다 큰 소수라면 이 최대 길이는 더 짧아질 것입니다. 따라서 연속열의 최대길이 k를 1000부터 감소시켜나가고, 시작 인덱스 i를 증가시키면서 검사해나가도록 합니다.

def s050():
    limit = 100_0000
    primes = seive(limit)
    target = set(primes)
    l = len(primes)
    for k in range(1000, 0, -1):
        for i in range(0, l-k-1):
            s = sum(primes[i:i+k])
            if s >= limit: break
            if s in target:
                print(s)
                return

이렇게 범위를 좁힌 경우 효율이 크게 오르기 때문에 수행 시간을 1/10로 단축할 수 있었습니다.