Problem 10 "sum of prime numbers"
The sum of prime numbers less than or equal to 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all prime numbers less than or equal to 2 million.
Python
n = 2000000
def generate_primes(n):
primes = [2]
for i in range(3, n+1, 2):
for p in primes:
if i % p == 0:
break
else:
primes += [i]
if i % (n // 100) == 1:
print "%d / %d" % (i, n)
return primes
primes = generate_primes(n)
result = sum(primes)
print result
print result == 142913828922
print primes[-5:]
result
142913828922
True
[1999891, 1999957, 1999969, 1999979, 1999993]
It takes too much time, so I want to make it faster.
Recommended Posts