A pure functional Primality Test in Scala

A good algorithm to determine if a number is prime is one that tests only a subset of all numbers to enhance its performance. On the contrary, a non-optimized algorithm performs the test on each number, like the Sieve of Eratosthenes.

One particular optimization descends from the fact that all primes greater than 3 are of the form 6k ± 1, where k is any integer greater than 0. There is a famous Python algorithm that implements this optimization.

def is_prime(n: int) -> bool:
    """ Primality test using 6k+-1 optimization. """
    if n <= 3:
        return n > 1
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i ** 2 <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

In this post, I would like to translate this algorithm using a pure functional approach in Scala language.

Using Functional Programming we achieve some notable results:

• No side effects - if the code compiles, then it works
• Thread-safe and concurrency-safe
• Easier to reason about, because the function is algebraic
• Results can be combined - using pipelines

... and many others. (See this post if you want to learn more)

The algorithm above is not functional because the function is_prime is not pure. The reason is that it uses a variable (i) in a while loop.

To express the same algorithm as a pure function we need to eliminate all variables and use just constants. To do that, we use recursion.

This way, instead of storing the loop index (i) into the function, we pass it as a parameter to the function itself.

This is a first attempt.

def isPrime(n: Int, i: Int = 5): Boolean = {
    if (n <= 3)
        return n > 1
    if (n % 2 == 0 || n % 3 == 0)
        return false
    while (i * i <= n) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false
        return isPrime(n, i + 6)
    }
    true
}

As you can see, (i) is now an optional parameter of the function, and inside the while loop, the value of (i) is updated at every call.

To underline that (i) is an internal parameter and that the user should never supply it, we could use the implicit parameter group feature of Scala. In this way, we isolate the (i) parameter and make it clear that it is a parameter used only for recursion.

def isPrime(n: Int)(implicit i: Int = 5): Boolean = {
    if (n <= 3)
        return n > 1
    if (n % 2 == 0 || n % 3 == 0)
        return false
    while (i * i <= n) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false
        return isPrime(n)(i + 6)
    }
    true
}

This algorithm performs quite well, especially in multithreaded contexts.

The function above can be easily called like this:

println("Is 7669 prime? " + isPrime(7669))

You may find full source code in my GIT repo https://github.com/guildenstern70/PurePrimality