## DEV Community is a community of 894,881 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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
``````

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
• 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

## Discussion (6)

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.

Alessio Saltarin

Done, thank you!

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.

Roberto Leibman

Plus an implicit int is a really bad idea!

Alessio Saltarin

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

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.