Summation of Primes – Project Euler

Project Euler Problem 10 says

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.

Sieve of Eratosthenes animation

Sieve of Eratosthenes animation

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.

You may also like...

1 Response

  1. Prototype says:

    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.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>