## 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 the prime number sieve, introduced in Project Euler Problem 7, this is easy to solve in less than 100ms with only 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 the 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 concurrently sieves the primes and precomputes a running total to a list, `primes`

. 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 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 omitted).

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 Common Functions and Routines for Project Euler.