Project Euler Problem 10 Solution

Project Euler Problem 10 Solution

Summation of primes

by {BetaProjects} | 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

Foxtrot cartoon

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 following even index, and mark all the prime'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]
----------------------------------------------------------------------------------
Initial list               [0,   0,   2,   0,   0,   0,   0,   0,   0,   0,    0]
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 logo

Solves all test cases for Hackerrank Project Euler Problem 10

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