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

A simple approach

Using the function prime_sieve(N), introduced in Project Euler Problem 7, to find prime numbers less than N, we can solve this problem in less than 100ms using a couple lines of Python:

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

A more extensible solution

HackerRank poses a more demanding problem by having us find the sum of primes not greater than N (same as less than or equal to), where 1 ≤ N ≤ 10⁶ for up to 10,000 queries.

A reasonable way to approach solving this problem is to set up a list, primeSum[], with the intention of building a one-to-one relationship with the query's value as the index and the sum of primes as the element. For example, primeSum[10] = 17, the sum of all prime numbers not greater than 10.

The list would have to be big enough to handle all possible queries within the specified range. In this case we will increase it from one million to two million to accommodate the original problem's limit.

Basically, this is done using the principles of the sieve of Eratosthenes: find the next zero value in primeSum[], set the prime sum, s, at that index and the following even index, and mark all the prime's multiples as composites (i.e., set to -1).

Marking multiples is achieved by using list slicing in the form primeSum[start:stop:step]. Specifically, the Python statement primeSum[i::i] = [−1]*(N//i) fills every step index of the list, starting from start to the end of the list¹ with −1; our value to indicate composite numbers. The choice for −1 was arbitrary and was selected because it stands out.

¹When stop is omitted, as it is in this case, it fills to the end of the list.

A step–by–step breakdown of this algorithm

There’s a lot going on with the few lines of code in this algorithm. The table below illustrates the method for N=10 and s=2.

                                                primeSum[]
i   primeSum[i]==0?    s   [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]  [10]
----------------------------------------------------------------------------------
Initial list               [0,   0,   2,   0,   0,   0,   0,   0,   0,   0,    0]
3        Y             5   [0,   0,   2,  −1,   0,   0,  −1,   0,   0,  −1,    0]
primeSum[3],[4] = s        [0,   0,   2,   5,   5,   0,  −1,   0,   0,  −1,    0]
5        Y            10   [0,   0,   2,   5,   5,  −1,  −1,   0,   0,  −1,   −1]
primeSum[5],[6] = s        [0,   0,   2,   5,   5,  10,  10,   0,   0,  −1,   −1]
7        Y            17   [0,   0,   2,   5,   5,  10,  10,  −1,   0,  −1,   −1]
primeSum[7],[8] = s        [0,   0,   2,   5,   5,  10,  10,  17,  17,  −1,   −1]
9        N            17   [  all multiples of 9 already set by multiples of 3  ]
primeSum[9],[10] = s       [0,   0,   2,   5,   5,  10,  10,  17,  17,  17,   17]

At the end of the main loop the list is ready to accept as many queries as required.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 10

HackerRank Project Euler 10 asks us to run up to 10,000 test cases and sum prime numbers not greater than N, where 1 ≤ N ≤ 10⁶.

Last Word

• The sum, s, and the list, primeSum[], have been preset with the first prime number 2 so we could just loop through odd numbers.
• Have a look at the prime_sieve() function listed in Common Functions and Routines for Project Euler.