Project Euler #10 - 이백만 이하 모든 소수의 합

2,000,000보다 작은 모든 소수를 더하면?

앞서 썼던 prime sieve를 이용하면 된다. 실행시간은 0.1초 이내

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

print sum(rwh_primes1(2000000))

'체'로 걸러내지 않고, 3 이상의 모든 홀수를 소수인지 체크하는 식으로 해 봤더니 6초 정도가 걸린다. 소수 찾는 데는 '에라스토테네스의 체'가 진리!