Scala, example finding prime numbers

Firstly, Happy New Year! Happy 2009!

Continuing on with Scala, here is a further example, a simple test for prime numbers, also showing re-factoring from Scheme to Scala.

This simple example tests for primality, based on the simple algorithm taken from SICP in the following example given in the programming language Scheme:

package test

object FindPrimes {

  def main(args : Array[String]) {

    for (n <- 1 to 500) {

      val d = smallestDivisor(n)
      println(n + ": lcd = " + d + (if (n == d) " prime!" else " not prime") )
    }
  }

  def isPrime(n : Int) : Boolean = {

    n == smallestDivisor(n)
  }

  def smallestDivisor(n : Int) : Int = {

    findDivisor(n, 2)
  }

  def findDivisor(n : Int, testDivisor : Int) : Int = {

    if (square(testDivisor) > n)
      n
    else if (divides(testDivisor, n))
      testDivisor
    else
      findDivisor(n, testDivisor + 1)
  }

  def square(n : Int) : Int = {

    n * n
  }

  def divides(d : Int, n : Int) : Boolean = {

    (n % d) == 0
  }
}

The above example has a main that can be run. The code tests the first 500 integers for primality using the simple, unoptimised prime test algorithm which looks for the least divisor of n (below root(n)).

It's worth pointing out that the findDivisor function is recursive, but if you look at the way it's constructed, the recursion appears at the end of the construction - and is thus amenable to tail recursion (optimisation).

Note: When testing for Primes in this way, if no divisor d of n is found less than root(n) then the number is prime, thus the search for divisors can end at root(n). This is because for any divisor d of n, there is a corresponding divisor n/d. So the maximum value for either/both occurs at root(n), beyond this, as d increases above root(n), n/d decreases below root(n) symmetrically.

"If d is a divisor of n, then so is n/d. But d and n/d cannot both be greater than n."


In the statement:

println(n + ": lcd = " + d + (if (n == d) " prime!" else " not prime") )

We can see the use of an if expression. In this situation is looks rather like Java's ternary if construct, but Scala's if expressions along with other expressions like for etc are fundamentally different, in that the construct equates to a value, in this example a value of type implicitly determined as String.

However, it's worth noting that the following alteration to the println statement does not output "prime!" text:

println(n + ": lcd = " + d + (if (n == d) " prime!") )

My presumption (will confirm this) is that in the first case, all paths return String, so type inference determines type String. In the second case, the implicit else statement is missing, so not all paths return a String, so type inference probably determines a type of Nothing and the result is lost.

Update: As Jorge Ortiz has kindly pointed out in his comment, this is because the type inference of the Least Upper Bound (LUB). If not all paths return a type, the overall inference is Unit (like void) because this is the only safe inference that covers all cases.


.