## Project Euler Problem 10 Solution

Summation of primes

by {BetaProjects} | 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

#### 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 ≤ 106 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 list1 with −1; our value to indicate composite numbers. The choice for −1 was arbitrary and was selected because it stands out.

1When `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]
----------------------------------------------------------------------------------
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

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

### Python Source Code

``````s = 2; N = 2000000; primeSum = [0]*(N+1)
primeSum[2] = s
for i in range(3, N, 2):
if primeSum[i]==0:
s+= i
primeSum[i::i] = [-1]*(N//i)
primeSum[i] = s; primeSum[i+1] = s   #each odd index and the following even index
L = int(input("Sum of primes not greater than? "))
print ("is", primeSum[L])
``````

### 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.