Select Page

#### Project Euler 10 Problem 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

Using our prime number sieve introduced in 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 solve up to 10,000 test cases for any N≤1,000,000. 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 calculates a running sum concurrently before accepting any queries by filling a list (`prime_sum`) with those sums. This allows each query to act as an index to the appropriate sum in the list.

#### HackerRank version

HackerRank Project Euler 10 has us solve up to 10,000 test cases for any N≤1,000,000 (increased to 2,000,000 in the program below). This solution addresses this problem specifically.