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

#### 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 ≤ 10^{6} 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=2i 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 ≤ 10^{6}.

### Python Source Code

### Last Word

Have a look at the `prime_sieve()`

function listed in my Common Functions and Routines for Project Euler.