프로젝트 오일러 010

10,0001번째 소수를 구하는 문제에서 효율적인 소수 판별 함수를 작성해본 바 있습니다. 이를 사용해서 200만 이하의 정수들을 필터링하여 합을 구하면 됩니다. 간단해 보이는 문제 같습니다.

print(sum(filter(isprime, range(200_0000))))

사실 최근의 PC는 10년 전보다는 성능이 좋고, 그리고 파이썬도 점점 더 빨라지고 있기 때문에 이제는 이 방법을 사용해도 몇 초만에 답을 구할 수가 있습니다. 그렇지만 더 나은 방법이 있지 않을까요?

에라토스테네스의 체

이 문제가 10,001번째 소수를 구하는 문제와 다른 점은 범위가 정해져있다는 것입니다. 특정 범위 내의 모든 소수는 에라토스테네스의 체라고도 알려진 소수체를 만들면 빠르고 쉽게 구할 수 있습니다. 원리는 이렇습니다. 0~N까지의 범위의 숫자의 목록이 있고, 각 숫자에 스위치가 있다고 가정합니다. 0, 1은 소수가 아니니 스위치를 끕니다. 그런 다음, 스위치가 켜진 각 숫자를 발견하면 그 수의 배수들에 대해서 모두 스위치를 끕니다. 이런 방식으로 N의 제곱근까지 진행하면 배열에는 소수만 스위치가 켜진채로 남게 됩니다.

어떤 수의 배수들은 동일한 간격으로 떨어져있으므로, 슬라이스 문법을 사용하면 빠르게 접근할 수 있고 파이썬 내에서도 이는 루프의 오버헤드가 없기 때문에 앞선 방법들과 비교해도 수십 배 빠르게 작동합니다.

def sieve(n: int) -> list[int]:
  s = [1] * (n + 1)
  s[:2] = [0, 0]   # 0, 1은 소수아님
  for i in range(2, int(n ** 0.5 + 1.5)):
    if s[i]:
      s[2*i::i] = [0] * ((n - i) // i)
  return [i for (i, x) in enumerate(s) if x]

print(sum(seive(200_0000)))