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

에라토스테네스의 체를 이용하면 더 빠르게 구할 수 있다. 참고로 여기 사용된 로버트 윌리엄 행크스의 체 알고리듬은 현재까지 바견된 순수 파이썬 코드 중에서는 가장 빠른 것으로 알려져 있다.

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
    http://stackoverflow.com/questions/17773352/python-sieve-prime-numbers
    """
    sieve = [True] * (bound/2)
    for i in xrange(3, int(bound**.5)+1, 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))

동일 알고리듬으로 Swift에서 구현하면 다음과 같은 코드가 나온다.

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