Project Euler Problem #10:

Problem #10 is an example of how some common functions that are used in certain problems can also be used for other problems down the line. In my post for Problem #7, I discussed the Sieve of Eratosthenes, and I presented an implementation of it in Python 2.7. Perhaps unsurprisingly, this function can be used to solve many other problems such as Problem #10. The problem reads:

Project Euler Problem 10: Summation of primes 
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

It should be obvious to anyone familiar with the Sieve of Eratosthenes that it is exactly what we need to solve this problem. Here is the solution I found:

Solution #1: Sieve Approach

We just use the sieve to find all of the primes less than 2,000,000 and then add all of them up. Here is an implementation of this method in Python 2.7 using a copy-pasted version of the Sieve function I implemented in Problem #7:

'''
Author: Walker Kroubalkian
Sieve Approach to Project Euler Problem #10
'''

import time

def sieveEratosthenes(n):
    myPrimes = []
    
    primePossible = [True]*(n+1)
    primePossible[0] = False
    primePossible[1] = False

    for (i,possible) in enumerate(primePossible):
        if(possible):
            for x in range(i*i, (n+1), i):
                primePossible[x] = False
            myPrimes.append(i)

    return myPrimes

def projectEulerProblemTen(n):
    allPrimes = sieveEratosthenes(n)
    total = 0
    for p in allPrimes:
        total+=p
    return total

start = time.time()
print projectEulerProblemTen(2000000)
print ("--- %s seconds ---" % (time.time() - start))

'''
Prints

142913828922
--- 0.402328968048 seconds ---
for input of n=2000000
'''

As shown above, the Sieve of Eratosthenes is even efficient at listing all primes up to crazy large numbers such as 2,000,000. And with that, we have officially entered the double-digits of problems solved. I got the achievement “Decathlon” for solving this problem as it meant that I had solved 10 problems in a row.

Thanks for reading!