The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
def prime_list(num):
primes = range(2, num)
while primes:
x = primes.pop(0)
yield x
primes = [i for i in primes if i%x != 0]
[ i for i in prime_list(10)]
[2, 3, 5, 7]
sum([ i for i in prime_list(10)])
17
sum([ i for i in prime_list(2000000)])
--------------------------------------------------------------------------- KeyboardInterrupt Traceback (most recent call last) <ipython-input-6-fadd300fafe0> in <module>() ----> 1 sum([ i for i in prime_list(2000000)]) <ipython-input-1-6ba0cc81b5eb> in prime_list(num) 5 x = primes.pop(0) 6 yield x ----> 7 primes = [i for i in primes if i%x != 0] KeyboardInterrupt:
The above method is too slow. A faster sieve is needed.
def prime_list(num):
numbers = set(range(num, 1, -1))
primes = []
while numbers:
p = numbers.pop()
primes.append(p)
numbers.difference_update(set(range(p*2, num+1, p)))
return primes
prime_list(10)
[2, 3, 5, 7]
sum(prime_list(2000000))
142913828922L