Project Euler Problem 7

The 10001st Prime

Project Euler presents the following Problem #7:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

The Sieve of Eratosthenes algorithm has already been introduced to implement a prime number generator in Project Euler Problem 3. For this problem, since we don't know the upper limit necessary to generate the prime number in question (or do we?), we'll iterate over increasing numbers and perform a primality test on each until a counter determines that the $n^{th}$ prime has been found.

Primality Test

There are quite a few possible approaches to writing a primality test, either deterministic or probabilistic. Future problems will require probabilistic algorithms like the Rabin-Miller test, but we don't have to worry about checking extremely large numbers in this problem. For now, we can safely use the simplest trial division method, along with some optimizations based on what we know about prime numbers.

Fact 1: The smallest prime is 2

The most naive way to check whether a number, $n$, is prime is to divide it by every number between 2 and $n-1$. The function only returns true if none of the numbers evenly divide $n$.

1fun Int.isPrime(): Boolean {
2    if (this < 2) return false
3    for (num in 2 until this) {
4        if (this % num == 0) return false
5    }
6    return true
7}

Fact 2: A prime can only have 1 factor (itself) greater than its square root

As already explained in Problem 3, iterating over numbers greater than $\lfloor\sqrt{n}\rfloor$ will cause unnecessary checks, as the cofactors of any larger factors will have already been tested. The only distinct factor greater than this upper limit would be the prime number itself.

1import kotlin.math.sqrt
2
3fun Int.isPrime(): Boolean {
4    if (this < 2) return false
5    for (num in 2..sqrt(1.0 * this).toInt()) {
6        if (this % num == 0) return false
7    }
8    return true
9}

Fact 3: All primes are odd except 2

We can tighten our loop even further by removing the only even prime from the iteration and stepping through odd numbers only. This means a conditional branch has to be added to ensure that all even numbers are caught and properly processed, to avoid them either incorrectly entering or bypassing the loop.

1import kotlin.math.sqrt
2
3fun Int.isPrime(): Boolean {
4    if (this < 2) return false
5    if (this % 2 == 0) return this == 2
6    for (num in 3..sqrt(1.0 * this).toInt() step 2) {
7        if (this % num == 0) return false
8    }
9    return true
10}

Fact 4: As 3 is a prime, no multiple of 3 can be a prime

Let's rewrite the function to use a when block and incorporate new conditional branches to catch prime numbers 2 and 3, as well as any composites that are multiples of them. The for loop's lower limit is also increased to 5, as it is the lowest prime that is not assessed by previous conditional branches.

1import kotlin.math.sqrt
2
3fun Int.isPrime(): Boolean {
4    return when {
5        this < 2 -> false
6        this < 4 -> true
7        this % 2 == 0 || this % 3 == 0 -> false
8        else -> {
9            for (num in 5..sqrt(1.0 * this).toInt() step 2) {
10                if (this % num == 0) return false
11            }
12            true
13        }
14    }
15}

1fun doCalc() = 2 * 3
2
3fun main() {
4    val num = 6
5
6    when (num) {
7        0, 3, 9 -> println("Wrong value")
8        6 -> println("Value is equivalent")
9        in 0..10 -> println("Value in range")
10        6.0.toInt() -> println("Value matches Double")
11        doCalc() -> println("Value matches function")
12    }
13}

Value is equivalent

1fun sumOfDigits(digits: String) = digits.sumOf { it.digitToInt() }
2
3fun main() {
4    val number = "1234"
5    val n = number.length
6    val k = 2
7
8    val result = when (n) {
9        1 -> number.toInt()
10        k -> sumOfDigits(number)
11        else -> {
12            var largest = 0
13            for (i in 0..n - k) {
14                largest = maxOf(largest, sumOfDigits(number.substring(i, i + k)))
15            }
16            largest
17        }
18    }
19
20    println(result)  // 7
21}

Fact 5: All primes greater than 3 are of the form $6k\pm1$

This is technically linked to fact #4, as any integer of the form $6k\pm1$, with $k>0$, cannot be a multiple of 3. So, rather than iterating over odd numbers, the final form of our helper function steps through only numbers of the form $6k-1$ and performs an extra modulo operation to check the value of $6k+1$.

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            for (num in 5..sqrt(1.0 * this).toInt() step 6) {
12                if (this % num == 0 || this % (num + 2) == 0) return false
13            }
14            true
15        }
16    }
17}

Line 8: This conditional branch catches prime numbers 5 and 7, but isn't strictly necessary as they would both correctly bypass the for loop on line 11 and return true.

Line 11: The trial division loop still only iterates through odd numbers (remember that an odd number plus an even number can only produce an odd number) and skips all multiples of 3, so both original conditionals (line 7 and line 9) must remain. Note that the primes 11, 13, 17, 19, and 23 will correctly bypass this loop due to their square roots being less than 5. This means that the first integer to enter this loop will be 25.

This final version is the top-level helper function that I use whenever invoking Int values are not expected to exceed Int.MAX_VALUE. Personally, I prefer to wrap the sole purpose of the function into a single return statement with a sequential chain of conditional branches, but the conditionals could, of course, be grouped together by output (or removed from the when block entirely and replaced with two if statements and a for loop):

1import kotlin.math.sqrt
2
3fun Int.isPrime(): Boolean {
4    return when {
5        this == 2 || this == 3 -> true
6        this < 2 || this % 2 == 0 || this % 3 == 0 -> false
7        else -> {
8            for (num in 5..sqrt(1.0 * this).toInt() step 6) {
9                if (this % num == 0 || this % (num + 2) == 0) return false
10            }
11            true
12        }
13    }
14}

Speed Comparison

I ran a benchmark test on the 5 versions of Int.isPrime() over 1000 iterations using Int.MAX_VALUE as the calling value. Here's the average time each version took to determine that 2_147_483_647 is a prime number:

The Nth Prime

Now that we've created a helper function, it's just a matter of using it to find the $n^{th}$ prime:

1fun getNthPrime(n: Int): Int {
2    var count = n
3    var number = 1
4    while (count > 0) {
5        if ((++number).isPrime()) count--
6    }
7    return number
8}

We could, of course, include some optimizations in this function, for example, by only invoking the helper function with odd values. On my system, leaving the optimization to the helper function actually made getNthPrime() execute at an average of 7.80ms (for $n=10001$) compared to 8.21ms when the function was re-written to increment number by 2 instead of 1.

1fun Int.isEven() = this % 2 == 0
2
3fun main() {
4    var number = 0
5    while (number < 5) {
6        if (!(++number).isEven()) println("${number++} is odd")
7        if (number++.isEven()) println("${--number} is even")
8    }
9}

1 is odd
2 is even
3 is odd
4 is even
5 is odd
6 is even

1import kotlin.math.absoluteValue
2
3var number = 100
4val ans = number++.minus(150).absoluteValue
5println(ans)  // 50
6println(number)  // 101

Alternative Solution

At the beginning of this post I stated that we didn't know the upper limit for our prime number generator. However, if you are also using the sieve algorithm, it's honestly fast enough that you could have played around with a few numbers to get an approximate idea of the size of the generated lists. A prime counting function also exists, as do online calculators that would quickly determine an appropriate upper limit for this problem.

In fact, if the aim was to create a list of primes for quick-draw access to the $(n-1)^{th}$ prime, and you didn't want to either guess or brute force the upper limit, there is an alternative. This list could have been simultaneously generated and used as a primality test based on prime factorization. For every odd number checked, that number would be a prime if none of the previously found primes were able to evenly divide it or if a prime was reached that exceeded the number's square root. If found to be a prime, the number would be added to the list and the loop continued until the size of the generated list reached the desired maximum.

1/**
2 * @return list of [count] primes with the nth prime at index n-1
3 */
4fun getAllPrimes(count: Int): List<Int> {
5    val primes = mutableListOf(2)
6    var number = 1
7    nextNum@while (primes.size < count) {
8        number += 2
9        for (p in primes) {
10            if (p * p > number) break
11            if (number % p == 0) continue@nextNum
12        }
13        primes.add(number)
14    }
15    return primes
16}

Here's the full source code for this problem (and its corresponding test suite).

This solution set is also available in Python and in C++ on my GitHub.

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!🏝️🔎🍥