The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
It’s two million primes being added. What I thought initially was that oh well, I will just check each number and if it’s prime I will add it to a variable until the primes is within 2 million. The following was my attempt;
def isPrime(number): for n in xrange (2,number): if number%n == 0: return False return True result = 2 for k in xrange (3,2000000,2): if isPrime(k): result += k print result," ",k print "The total is %d" % result
As a noob in programming, this code took FOREVER to finish execution; “Ain’t nobody got time for dat!” I didn’t understand about code efficiency and elegancy of codes. So, I turned to codereview.stackexchange.com for help!
200_success suggested that using Sieve of Eratosthenes could actually do this problem in a fraction of second.
from math import sqrt import time start = time.time() def sum_primes(limit): sieve = range(limit+1); sieve = 0 for n in xrange(2, int(sqrt(limit))+1): if sieve[n] > 0: for i in xrange(n*n, limit+1, n): sieve[i] = 0 return sum(sieve) print sum_primes(2000000) end = time.time() print end - start
This code only took 0.473822116852 second. The code created a list which contained two million numbers starting from zero. Then, it loops until square root of the limit because the code will be squared in the subsequent loop as a starting point.
This is what Sieve of Eratosthenes does.
Source : http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
So, yea, the code basically takes off all of the multiples of prime numbers. The gif explains much better.