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[1] = 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.

If processing time for running a program is your issue, obviously the easiest solution is to not simplify the program into a more clever solution but to rent a very expensive super computer cluster and have money do the work for you.

It would be like making 30 people do a really bad job compared to one person do a simpler job.