10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다. 이백만(2,000,000) 이하 소수의 합은 얼마입니까? (http://euler.synap.co.kr/prob_detail.php?id=10)
이전에 만든 소수 판별 함수를 사용하면 간단히 풀 수 있는 문제이다.
sum(x for x in range(200_0000) if isprime(x))소수 판별 함수의 성능 자체는 나쁘지 않지만, 루프를 200만번 돌아야 하기 때문에 시간이 제법 오래 걸리는 것은 어쩔 수 없다. 사실 2를 제외한 모든 짝수는 소수가 아니므로, 다음과 같이 홀수만 검사하도록하면 검사 횟수를 절반으로 줄일 수 있다.
2 + sum(x for x in range(3, 200_0000, 2) if isprime(x))이론상으로는 그렇지만 성능상으로는 그다지 향상이 체감되지 않을 것이다. 어차피 짝수들은 isprime() 함수의 초반부에서 소수가 아니라고 빠르게 판정되기 때문이다.
대신에 이렇게 범위가 정해진 영역 내에서 소수를 찾을 때에는 에라토스테네스의 체를 사용하면 빠르게 소수만 만들 수 있다. 에라토스테네스의 체는 교과서에서도 소개하겠지만 대충 다음과 같은 방식으로 만든다.
- 0부터 1,999,999 까지를 리스트 같은 곳에 기록해둔다.
- 0, 1 은 소수가 아니므로 지운다.
- 2는 소수이다. 2만 남겨놓고 4, 6, 8, …, 1999998까지 2의 배수들을 모두 지워버린다.
- 다음 지워지지 않은 칸(3)의 숫자는 소수이다. 6부터 3씩 건너뛰면서 3의 배수들을 모두 지워버린다.
- 4로 되돌아간다. 이번에는 5를 발견하게 된다.
이 과정을 반복하면 소수가 아닌 소수의 배수들을 모두 지우게 되어 리스트에는 소수가 남는다. 실제 파이썬 구현에서는 리스트의 원소 자체를 제거하는 것이 아니라, True, False 로 이루어진 리스트를 조작한다. 예를 들어 2의 배수를 지울 때에는 xs[4:200_0000:2] 의 구간을 전부 False로 채우는 방식으로 지웠다는 것을 표시한다. 또한 소수 검사때와 마찬가지로 범위 상한선의 제곱근 아래에서만 소수를 찾아서 배수를 지우면 자연스럽게 제곱근 위에는 소수만 남게 될 것이다.
limit = 200_0000
s = [True] * (limit + 1)
s[0:2] = [False, False]
for i in range(2, int(limit ** .5 + 1.5)):
if s[i]:
s[i*2::i] = [False] * ((limit - i) // i)
primes = [i for i, x in enumerate(s) if x]
print(sum(primes))이 코드에서 불필요한 동작을 빼고 최적화한 코드가 윌리엄 행크스가 공개한 아래의 코드이다. (원래는 파이썬2 버전의 코드라서 파이썬3 문법에 맞게 약간 수정함)
def prime_seive(bound: int):
"""Return a list of prime numbers from 2 to n.
Very fast, (n < 10,000,000) in 0.4 sec. """
sieve = [True] * (bound // 2)
for i in range(3, int(bound**.5 + 1.5), 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]]