Not having a computer science background, I was curious about how to write a Scala function that would find a list of all prime numbers up until some maximum value I supply. I was aware of the Sieve of Eratosthenes, but I didn’t want to implement that, at least not today.
A Scala 3 (Dotty) function
What I ended up doing looks like other Scala prime number solutions you can find on the internet. To make things look a little different, I wrote the code using the current Scala 3 (Dotty) syntax, and the result looks like this:
def isPrime(i: Int): Boolean =
if (i <= 1)
false
else if (i == 2)
true
else
!(2 until i).exists(n => i % n == 0)
You can also write that code with a match
expression, if you prefer.
When you run that code in the Scala REPL with the number 3
, you get the result false
, as expected. Here’s what it looks like with a few other numbers:
scala> isPrime(1102) val res0: Boolean = false scala> isPrime(1103) val res1: Boolean = true
Now to have a little fun with it, here’s what isPrime
looks like when you run it with a series of numbers from 1
to 20
, using the filter
method:
scala> (1 to 20).filter(isPrime) val res0: IndexedSeq[Int] = Vector(2, 3, 5, 7, 11, 13, 17, 19)
How that code works
To understand how isPrime
works, it helps to break it down into smaller pieces and add in some debug output.
A modulus function
To do that I first create a function I named modIsZero
, standing for “modulus is zero”:
// with debug output
def modIsZero(num: Int, den: Int): Boolean =
val mod = num % den == 0
println(f"i: ${num}%2d, n: ${den}%2d, modIsZero: $mod")
mod
In that function, num
stands for numerator and den
stands for denominator. The function calculates the modulus using those two values, prints the debug output shown, and then returns the modulus value. Its results look like this:
modIsZero(2, 2) // true
modIsZero(3, 2) // false
The isPrime function with debug code
Next, I modified the isPrime
function to add in some debug code, and use the modIsZero
function:
def isPrime(i: Int): Boolean =
if (i <= 1)
false
else if (i == 2)
true
else
println(s"\ncalling function for $i")
val foundADivisor = (2 until i).exists(n => modIsZero(i, n))
println(s"foundADivisor = $foundADivisor")
!foundADivisor
As shown, all of the changes are in the else
clause. The best way to explain that code is to show what the output looks like when I call it again with a list of integers, this time from 1
to 10
:
scala> (1 to 10).filter(isPrime) calling function for 3 i: 3, n: 2, modIsZero: false foundADivisor = false calling function for 4 i: 4, n: 2, modIsZero: true foundADivisor = true calling function for 5 i: 5, n: 2, modIsZero: false i: 5, n: 3, modIsZero: false i: 5, n: 4, modIsZero: false foundADivisor = false calling function for 6 i: 6, n: 2, modIsZero: true foundADivisor = true calling function for 7 i: 7, n: 2, modIsZero: false i: 7, n: 3, modIsZero: false i: 7, n: 4, modIsZero: false i: 7, n: 5, modIsZero: false i: 7, n: 6, modIsZero: false foundADivisor = false calling function for 8 i: 8, n: 2, modIsZero: true foundADivisor = true calling function for 9 i: 9, n: 2, modIsZero: false i: 9, n: 3, modIsZero: true foundADivisor = true calling function for 10 i: 10, n: 2, modIsZero: true foundADivisor = true val res11: IndexedSeq[Int] = Vector(2, 3, 5, 7)
Understanding the output
That output shows how isPrime
works. For instance, just looking at the instance where i
is 7
, you see this output:
calling function for 7
num: 7, n: 2, modIsZero: false
num: 7, n: 3, modIsZero: false
num: 7, n: 4, modIsZero: false
num: 7, n: 5, modIsZero: false
num: 7, n: 6, modIsZero: false
foundADivisor = false
This shows that in this piece of code:
val foundADivisor = (2 until i).exists(n => modIsZero(i, n))
the exists
function is looking at the number 7
. First it divides 7
by 2
, finds the modulus is non-zero, and modIsZero
returns false
to exists
. Next, exists
tests the 7
against the number 3
, again finds the modulus is non-zero, and modIsZero
returns false
to exists
. This keeps happening until n
is 6
. Because all of these tests within exists
end up being false
, foundADivisor
ends up being false
, and the number is then considered to be a prime number.
Having seen that output for a prime number, you can also see how exists
works for a non-prime number, such as 6
:
calling function for 6
num: 6, n: 2, modIsZero: true
foundADivisor = true
In this case, 6
can be divided by 2
without a modulus remainder, so exists
immediately stops at that point. Since 6/2
causes modIsZero
to return true
, there’s no reason for exists
to look at the rest of the range.
this post is sponsored by my books: | |||
#1 New Release |
FP Best Seller |
Learn Scala 3 |
Learn FP Fast |
Summary
As a little summary, if you wanted to see one possible Scala algorithm to determine if a number if a prime number, I hope this example is helpful. As I mentioned early on, this is not a Sieve of Eratosthenes algorithm, but it’s one possible algorithm that can be used. Please look at the Wikipedia “Sieve of Eratosthenes” page for more details about that algorithm, and other related algorithms.