Imperative vs Functional: Finding prime numbers

It's always seemed to me that, while imperative programming means having a more intimate relation with your machine (at the most basic level, the programming language is imperative), functional programming has a certain pure elegance to it that makes it even more appealing than the former. Sadly, languages have usually been separated into imperative vs. functional in such a way that, even though scripting languages like python might offer a bit of a functional flavour, they fail to offer the elegance of functional languages in an imperative context.

Enter Scala. I've only played around for a bit with this new language, but it does seem to have the best of both worlds. Weather Scala will end up being as widespread as Java et al. Only time will tell (although my bet is that it most definitely will).

Anyway, let us take a look at what Scala can do.

Finding a prime number

This is a classic. Write a simple algorithm that computes weather a given number is prime or composite. Note that I won't cover setting up the environment to work with Scala; the Scala webpage does a great job at that.

One way to check if a number is prime is by checking if anything less that itself and larger than 1 divides it:

for i from 2 to (n-1):

    if(i%n == 0) return “is not prime”

return “is prime”

You can easily see this is correct; the second return statement is only reached when all of the values less than n have been checked as divisors of n.

Here's how one would express it in Scala:

val n = args(0).toInt

def imperativeIsPrime(x: Int): Unit =

{

   for(i <- 2 to (n-1))

   {

     if(n%i == 0)

     {

     println(x + " is not prime. It is divisible by " + i)

     return

     }

   }

println(x + " is prime")

}

Add this into a file called imperativePrime.scala. This script can be run by using

scala impertivePrime.scala [your number]

e.g.:

scala imperativePrime.scala 13

at the command prompt. Again, check the tutorials on the Scala website.

Let's go through this code line by line.

val n = args(0).toInt

This simply takes the first argument passed at command line and stores it into n.

def imperativeIsPrime(x: Int): Unit

This defines a new function called imperativeIsPrime which takes one argument of form Int and has return type Unit. Type Unit is very similar to void in Java, so we'll just leave it at that.

Next up, the loop:

for(i <- 2 to (n-1))

2 to (n-1) means the same as 2.to(n-1). 2 is an object and to is a method of this object which returns something called a Range: Range(2,3,4,...,n-1).

i <- 2 to(n-1) means that i takes every value in the range and executes the body of the loop, which checks for divisibility, which is pretty obvious.

So this is the imperative approach. Now onto the functional one, which I shall cover tomorrow.