오일러 프로젝트 010

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