Project Euler Problem 10 Solution

Project Euler & HackerRank Problem 10 Solution

Summation of primes
by {BetaProjects} | MAY 8, 2009 | Project Euler & HackerRank

Project Euler Problem 10 Statement

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Solution

Foxtrot cartoon

A simple approach

Using our prime number sieve introduced in Project Euler Problem 7 this is easy to solve in less than 100ms with a couple lines of Python:

from Euler import prime_sieve
print (sum(prime_sieve(2000000)))

HackerRank asks a much more demanding question by having us find a sum of primes below any 1 ≤ N ≤ 106 for up to 10,000 values of N. Even though the prime number range is halved, it still requires both prime and non–prime queries up to and including N. Having the possibility of non–prime queries means simply mapping prime numbers to sums won’t work for those cases, especially with a time restriction.

This solution sieves the primes and precomputes a running sum concurrently by filling a list, primes, with those sums before accepting any queries. This allows each query to act as an index to the appropriate sum in the list.

A step–by–step breakdown of this algorithm

There’s a lot going on for the few lines of code in this algorithm. We are using the sieve of Eratosthenes to generate prime numbers and then reuse the same space to store their running sum. The table below illustrates the method for an N=11.

N=11; s=2
i   primes[i]==0?     s                primes[]
3        Y             5   [0, 0, 0, −1, 0, 0, −1, 0, 0, −1, 0]
primes[3],[4] = 5          [0, 0, 0, 5, 5, 0, −1, 0, 0, −1, 0]
5        Y            10   [0, 0, 0, 5, 5, −1, −1, 0, 0, −1, −1]
primes[5],[6] = 10         [0, 0, 0, 5, 5, 10, 10, 0, 0, −1, −1]
7        Y            17   [0, 0, 0, 5, 5, 10, 10, −1, 0, −1, −1]
primes[7],[8] = 17         [0, 0, 0, 5, 5, 10, 10, 17, 17, −1, −1]
9        N
primes[9],[10]= 17         [0, 0, 0, 5, 5, 10, 10, 17, 17, 17, 17]

You can see how we mark a prime number with a −1 and then all its multiples with the primes[i::i] = [−1]*(N//i) by using an array slice: a[start:stop:step]. This fills every step index of the array, starting from start to the end of the array (when stop is left empty).

Now, we have a one–to–one list mapping queries to sum of primes. For example, primes[8] = 17, the sum of all primes less than 8.

HackerRank version

HackerRank requires us to run 10,000 test cases and sum prime numbers below an upper bound, N, where 1 ≤ N ≤ 106.

Python Source Code

download Python source code Use this link to download the Project Euler Problem 10: Summation of primes.

Last Word

Have a look at the prime_sieve() function listed in my Common Functions and Routines for Project Euler.