프로젝트 오일러 050

문제

50번 문제

1백만 이하의 소수 중 가장 길게 연속되는 소수의 합으로 표현되는 수는?

사이냅소프트

백만 이하의 소수의 리스트에서 연속된 소수의 합이 소수가 되는 가장 긴 부분열을 찾는 문제입니다. 백만 이하의 소수는 소수체를 통해 빠르게 얻을 수 있으며, 그 합 역시 백만 이하의 소수라는 단서가 있으므로, 소수 판별 함수를 사용하는 대신에 만들어진 소수체를 집합(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()

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

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

이것은 100 이하에서는 가장 길게 연속된 소수의 합으로 이루어진 소수입니다. 1000 이하에서는 953이 연속된 소수 21개의 합으로 가장 깁니다. 1백만 이하에서는 어떤 소수가 가장 길게 연속되는 소수의 합으로 표현될 수 있습니까?

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

접근

백만 이하의 소수 리스트 A가 있다면 A[start:end]의 합계가 백만 이하의 소수인지 검사하고, 그러한 것들 중에서 (end – start)가 최대인 것을 찾으면 된다. 간단히 리스트 축약으로 풀 수 있다고 생각할지 모르지만, 백만 이하의 소수는 78,000개가 넘으므로 전체를 체크하는 것은 시간이 오래 걸린다. 따라서 루프 중간에 합계가 백만을 초과하면 다음번 start로 넘어가도록 하여 시간을 단축해주면 된다.

합계가 소수인지 여부는 이미 소수체를 만들었으니, 소수체를 set로 만들어서 멤버십 테스트를 통해 대체하면 된다.

%%time

def sieve(n: int) -> list[int]:
  s = [False] * 2 + [True] * (n - 1)
  for i in range(int(n ** .5 + 1.5)):
    if s[i]:
      s[i+i::i] = [False] * ((n - i) // i)
  return [i for i, x in enumerate(s) if x]

ps = sieve(100_0000)
ts = set(ps)
res = (0, 0)
for start in range(0, len(ps) - 2):
  for end in range(start + 2, len(ps)):
    x = sum(ps[start:end])
    if x > 999_999:
      break
    if x in ts and (end - start) > res[1]:
      res = (x, end - start)
print(res)