DEV Community

Cover image for A pure functional Primality Test in Scala
Alessio Saltarin
Alessio Saltarin

Posted on • Updated on

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
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

This algorithm performs quite well, especially in multithreaded contexts.

The function above can be easily called like this:

println("Is 7669 prime? " + isPrime(7669))
Enter fullscreen mode Exit fullscreen mode

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

Discussion (6)

Collapse
markclewis profile image
Mark Lewis

I would suggest that you not use math.pow to square things. Just do i*i instead of math.pow(i, 2). I expect that you will find it is much faster to run in addition to being shorter to type. As a general rule, using math.pow is inefficient for any small integer power. In this case, it is particularly bad because i is an integer and math.pow is working with doubles and the conversion from Int to Double also has a cost.

Collapse
guildenstern70 profile image
Alessio Saltarin Author

Done, thank you!

Collapse
rleibman profile image
Roberto Leibman

I think a better practice would be to have an inner function (traditionally called loop), that way your caller doesn't need to know the dirty details of you using recursion. Also.... you probably want to add @tailrec, to make sure your function can be optimized by the compiler.

Collapse
rleibman profile image
Roberto Leibman

Plus an implicit int is a really bad idea!

Collapse
guildenstern70 profile image
Alessio Saltarin Author

I am not sure the function is tail recursive...

Collapse
sshark profile image
TH Lim

The function is pure if it,

  1. always return the same value for the same input
  2. always accepts values and returns values
  3. only uses the values from its parameters i.e. the function not use values or variables outside of the function. So, if the mutation happens inside the function and the variable localized within the function, the function is considered pure.