(15 votes, average: 5.00 out of 5)

## Project Euler 10: Calculate the sum of all the primes below two million

#### Project Euler 10 Problem Description

Project Euler 10: The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

#### Analysis

This problem requires us to generate 2 million prime numbers, sum them and report their total. 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 trials 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 N. This can be trickier than first thought and required a more utilitarian solution. Having the possibility of non-prime queries means that simply mapping prime numbers to sums won’t work in those cases, especially with the 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.

This program and method
solves all test cases for
Project Euler 10 on HackerRank

#### Project Euler 10 Solution

Runs < 0.310 seconds in Python 2.7.
Use this link to get the Project Euler 10 Solution Python 2.7 source.

#### Afterthoughts

• Function `prime_sieve` is listed in Common Functions and Routines for Project Euler
• Prime numbers are used often for solving Project Euler problems and the prime sieve provided here is much faster than traditional methods.
• There are better ways to select candidates for being composite or prime, such as checking only odd numbers, but that understanding simply wasn’t implemented.
• This example only solves N≤10,000 because the Trinket is slow.
Project Euler 10 Solution last updated