Project Euler Problem 10

Summation of Primes

Project Euler presents the following Problem #10:

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

Find the sum of all the primes below two million.

The Naive Brute

First things first, that heading's not meant as an insult 🌼. It's my personal belief that the most logical solution to start with is often the roughest and most thorough one, particularly to establish a control against which we can compare our future refactored solutions.

If we iterate over all positive integers below our desired limit and add every number that we determine to be a prime, we'll have achieved the basic goal of this problem.

The deterministic primality test that I use to solve Project Euler problems has already been covered in Problem #7, so check that out to be guided through the thought process behind the function below:

1import kotlin.math.sqrt
2
3fun Int.isPrime(): Boolean {
4    return when {
5        this < 2 -> false
6        this < 4 -> true
7        this % 2 == 0 -> false
8        this < 9 -> true
9        this % 3 == 0 -> false
10        else -> {
11            val max = sqrt(1.0 * this).toInt()
12            var step = 5
13            while (step <= max) {
14                if (this % step == 0 || this % (step + 2) == 0) return false
15                step += 6
16            }
17            true
18        }
19    }
20}

Using this helper function (or one of your choosing 🤗), we can write a simple loop that finds the sum of all prime numbers $\leq n$:

1fun sumOfPrimesBrute(n: Int): Long {
2    if (n < 2) return 0L
3
4    var total = 2L
5    for (num in 3..n step 2) {
6        if (num.isPrime()) total += num
7    }
8
9    return total
10}

Line 5: Iteration is halved by taking advantage of the fact that 2 is the smallest and only even prime number.

This is not an efficient solution, particularly for very large values of $n$, but it gets the job done. Also, if you've already rigorously tested your primality test, you'll be assured that you're getting the correct result every time, so you can use this to build test cases for the solutions that follow.

The Simple Sieve

Problem #3 gave us our first introduction to the Sieve of Eratosthenes, so check out that post if you want a reminder of how the following algorithm works:

1import kotlin.math.sqrt
2
3/**
4 * Sieve of Eratosthenes algorithm returns all prime numbers less than or equal to n,
5 * with processing time cut in half by only allocating mask memory to odd numbers and by only
6 * looping through multiples of odd numbers.
7 */
8fun primeNumbers(n: Int): List<Int> {
9    if (n < 2) return emptyList()
10    
11    val oddSieve = (n - 1) / 2
12    val boolMask = BooleanArray(oddSieve + 1) { true }
13    for (i in 1..(sqrt(1.0 * n).toInt() / 2)) {
14        if (boolMask[i]) {
15            var j = 2 * i * (i + 1)
16            while (j <= oddSieve) {
17                boolMask[j] = false
18                j += 2 * i + 1
19            }
20        }
21    }
22    
23    return boolMask.mapIndexed { i, isPrime ->
24        if (i == 0) 2 else if (isPrime) 2 * i + 1 else null
25    }.filterNotNull()
26}

Problem #3 might have been a premature introduction to this algorithm, but hopefully by now it's a breeze to follow because we're going to take its essence and tailor it to fit our goal in two different ways.

For this solution, only the last 3 lines of primeNumbers() are altered to return the sum of elements of the BooleanArray instead of a List:

1import kotlin.math.sqrt
2
3fun sumOfPrimesSieve(n: Int): Long {
4    if (n < 2) return 0L
5
6    val oddSieve = (n - 1) / 2
7    val boolMask = BooleanArray(oddSieve + 1) { true }
8    for (i in 1..(sqrt(1.0 * n).toInt() / 2)) {
9        if (boolMask[i]) {
10            var j = 2 * i * (i + 1)
11            while (j <= oddSieve) {
12                boolMask[j] = false
13                j += 2 * i + 1
14            }
15        }
16    }
17
18    return boolMask.withIndex().sumOf { (i, isPrime) ->
19        if (i == 0) 2L else if (isPrime) 2L * i + 1 else 0
20    }
21}

When n = 2_000_000, this solution performs significantly better, with an average execution speed over 100 iterations of 11.24ms compared to the brute solution's 254.50ms.

Let's adapt the algorithm even further to solve the more challenging problem of returning sums for multiple values of $n$.

The Custom Job

If we only needed to find the sum for a handful of $n$ values, it would be no trouble to invoke sumOfPrimesSieve() repeatedly. But, as the amount of expensive calls increases, the efficiency significantly drops as the overlap of repeatedly generated primes increases.

To avoid this, we can swap the BooleanArray for a LongArray that will serve simultaneously as a mask and a cache of cumulative sums, which will then be returned for quick-draw O(1) access.

Note that this implementation uses a full mask instead of a half odds-only mask, as in the original primeNumbers(), so that the results for all positive integers below the limit can be cached.

1fun getAllSumsOfPrimes(limit: Int): LongArray {
2    val sums = LongArray(limit + 1) { 0L }.apply { this[2] = 2L }
3    
4    var total = 2L
5    for (i in 3..limit step 2) {
6        if (sums[i] == 0L) {
7            total += i
8            // mark all multiples of this prime
9            if (1L * i * i < limit.toLong()) {
10                for (j in (i * i)..limit step 2 * i) {
11                    sums[j] = -1L
12                }
13            }
14        }
15        // change current odd number
16        sums[i] = total
17        if (i + 1 <= limit) {
18            // change next even number
19            sums[i + 1] = total
20        }
21    }
22    
23    return sums
24}

Line 9: This avoids any overflow error when calculating the square of i. This check could be replaced by using a LongProgression in the inner loop and casting j to Int for every index access.

Line 10: Observe that the outer for loop is only stepping through odd numbers. This inner loop could be started at i but sums[i] will be altered again on line 16, so the next best start is the square of i, which will also be an odd number. Any earlier multiples will either be even or already handled by smaller primes. The step has a value of 2 * i, which will always be an even number, so that the loop only steps through odd multiples of the prime number (an odd plus an even number produces an odd number).

Line 17: This avoids any IndexOutOfBoundsException if the provided limit is not an even number.

Calling getAllSumsOfPrimes(2_000_000) on my system generated a result cache in 59.69ms, from which any $n$ could be queried using cache[n] to get the sum of all primes less than or equal to $n$.

The Crafty Python

My Python solution is a duplicate of my Kotlin solution, except for a lovely little trick that I was very happy to learn existed: slice assignment.

As long as you have a basic grasp of Python's slice notation, understanding slice assignment should also follow, particularly since the more basic cases do not require that the sequence sizes match:

1cache = [0]*10  # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
2
3cache[1:3] = [1]*2  # [0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
4cache[5:] = [2, 3]  # [0, 1, 1, 0, 0, 2, 3]
5cache[:1] = []  # [1, 1, 0, 0, 2, 3]

Slice assignment is used to change the current odd number and the following even number for every iteration via sums[i:i+2] = [total]*2.

To replace the inner for loop that marks all odd multiples of a prime number, the slice assignment has to take a step argument, which means that the sequence size being inserted must match the size of the slice exactly. To avoid a ValueError exception, this just requires an extra calculation on the right-hand side to ensure that we're producing a sequence with the correct amount of -1 elements:

1def get_all_sums_of_primes(limit: int) -> list[int]:
2    sums = [0]*(limit + 1)
3    sums[2] = 2
4    
5    total = 2
6    for i in range(3, limit + 1, 2):
7        if sums[i] == 0:
8            total += i
9            sums[i*i::2*i] = [-1]*((limit-i*i)//(2*i)+1)
10        sums[i:i+2] = [total]*2
11        
12    return sums

Unlike with Kotlin, there's no risk of overflow when calculating the square of i, nor is there an extra ValueError risk because any square greater than limit would create an empty sequence on the right-hand side to match the empty slice on the left.

There is also no need to ensure that the provided limit is an even number. Thanks to slice assignment, when the last index i for an odd number limit is reached, the following (and previously non-existent) even number will be accessed and the list will simply increase in size accordingly without throwing an exception.

🪄 Python 🪄

Visit the following links to see the Kotlin and Python source code and test suites in their respective repositories:

• Kotlin source: solution tests
• Python source: solution tests

Problem content on the Project Euler site is licensed under a Creative Commons (CC) License: CC BY-NC-SA 4.0. Solutions to only the first hundred problems are encouraged to be distributed publicly.

Thanks for reading!🏝️🎭🔪🐍