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
Top comments (6)
I would suggest that you not use math.pow to square things. Just do
i*i
instead ofmath.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 andmath.pow
is working with doubles and the conversion from Int to Double also has a cost.Done, thank you!
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.Plus an implicit int is a really bad idea!
I am not sure the function is tail recursive...
The function is pure if it,