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

Project Euler 10Using 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.

Python 2.7 Source

Last Word