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 function prime_sieve(N)
, introduced in Project Euler Problem 7, to find prime numbers less than N, we can solve this problem in less than 100ms using a couple lines of Python:
from Euler import prime_sieve
print (sum(prime_sieve(2000000)))
A more extensible solution
HackerRank poses a more demanding problem by having us find the sum of primes not greater than N (same as less than or equal to), where 1 ≤ N ≤ 106 for up to 10,000 queries.
A reasonable way to approach solving this problem is to set up a list, primeSum[]
, with the intention of building a one-to-one relationship with the query's value as the index and the sum of primes as the element. For example, primeSum[10]
= 17, the sum of all prime numbers not greater than 10.
The list would have to be big enough to handle all possible queries within the specified range. In this case we will increase it from one million to two million to accommodate the original problem's limit.
Basically, this is done using the principles of the sieve of Eratosthenes: find the next zero value in primeSum[]
, set the prime sum, s
, at that index and the next, and mark all the primes's multiples as composites (i.e., set to -1).
Marking multiples is achieved by using list slicing in the form primeSum[start:stop:step]
. Specifically, the Python statement primeSum[i::i] = [−1]*(N//i)
fills every step
index of the list, starting from start
to the end of the list1 with −1; our value to indicate composite numbers. The choice for −1 was arbitrary and was selected because it stands out.
1When stop
is omitted, as it is in this case, it fills to the end of the list.
A step–by–step breakdown of this algorithm
There’s a lot going on with the few lines of code in this algorithm. The table below illustrates the method for N=10 and s=2.
primeSum[] i primeSum[i]==0? s [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
3 Y 5 [0, 0, 2, −1, 0, 0, −1, 0, 0, −1, 0] primeSum[3],[4] = s [0, 0, 2, 5, 5, 0, −1, 0, 0, −1, 0] 5 Y 10 [0, 0, 2, 5, 5, −1, −1, 0, 0, −1, −1] primeSum[5],[6] = s [0, 0, 2, 5, 5, 10, 10, 0, 0, −1, −1] 7 Y 17 [0, 0, 2, 5, 5, 10, 10, −1, 0, −1, −1] primeSum[7],[8] = s [0, 0, 2, 5, 5, 10, 10, 17, 17, −1, −1] 9 N 17 [ all multiples of 9 already set by multiples of 3 ] primeSum[9],[10]= s [0, 0, 2, 5, 5, 10, 10, 17, 17, 17, 17]
At the end of the main loop the list is ready to accept as many queries as required.
HackerRank version
HackerRank asks us to run up to 10,000 test cases and sum prime numbers not greater than N, where 1 ≤ N ≤ 106.
Python Source Code
s = 2; N = 2000000; primeSum = [0]*(N+1)
primeSum[2] = s
for i in range(3, N, 2):
if primeSum[i]==0:
s+= i
primeSum[i::i] = [-1]*(N//i)
primeSum[i] = s; primeSum[i+1] = s #each odd index and the following even index
L = int(input("Sum of primes not greater than? "))
print ("is", primeSum[L])
Last Word
Have a look at the prime_sieve()
function listed in Common Functions and Routines for Project Euler.