오일러 프로젝트 10번
10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다. 이백만(2,000,000) 이하 소수의 합은 얼마입니까? (http://euler.synap.co.kr/prob_detail.php?id=10)
지난 번에 만든 isPrime() 함수를 이용해서 다음과 같이 풀면 되는데…
print(sum((x for x in range(2000000+1) if isPrime(x))))
조금 200만번 루프를 도는 것 보다는 다음과 같이 백만번으로 루프를 줄여보자.
print(2 + sum(x for x in range(3, 200_0000, 2) if isPrime(x)))그런데 이렇게해도 백만번의 루프는 만만한게 아니라서 제법 시간이 걸린다. 이 문제의 핵심은 구해야하는 소수의 상한이 정해져 있다는 것이다. 이런 경우 루프를 돌면서 일일이 소수검사를 하기보다는 에라토스테네스의 체를 이용하면 훨씬 빠르게 구할 수 있다.
에라토스테네스의 체는 숫자를 좌르륵 써 놓고 소수가 발견되면 그 소수의 배수들을 모두 지우는 것이다. 이런식으로 합성수들을 지워나가면 소수만 남게되는 원리를 이용한다.
참고로 여기 사용된 로버트 윌리엄 행크스의 체 알고리듬은 현재까지 바견된 순수 파이썬 코드 중에서는 가장 빠른 것으로 알려져 있다.
원래 코드는 Python 2 기준이라서 이 글에서는 Python 3 형식으로 수정했다.
def prime_sieve(bound):
"""
Return a list of prime numbers from 2 to n.
Very fast, (n < 10,000,000) in 0.4 sec.
----
Algorithm & Python source: Robert William Hanks
https://stackoverflow.com/questions/17773352/python-sieve-prime-numbers
"""
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]]
print(sum(prime_sieve(2000000)))이 알고리듬을 사용하면 0.1초 이내에 답을 구할 수 있다. (ㄷㄷㄷ)
다음은 같은 알고리듬은 Swift에서 구현한 것이다. (Swift 1.0)
func primeSieve(bound:Int) -> [Int] {
/*
Return a list of prime numbers from 2 to bound
*/
var sieve:[Bool] = Array(count:bound/2, repeatedValue:true)
var i = 3
let l = Int(sqrt(Float(bound)))
while i <= l {
if sieve[i/2] {
for(var k = i*i/2; k < sieve.count; k += i) {
sieve[k] = false
}
}
i += 2
}
return [2] + Array(1..<bound/2).filter{sieve[$0]}.map{return 2*$0+1}
}
print(primeSieve(2000000).reduce(0, +))
// 142913828922