A Scala function to determine whether a number is a prime number

By Alvin Alexander. Last updated: May 28, 2020

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.

scala

function