오일러 프로젝트 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

접근

백만 이하의 소수 리스트 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)