Sieve of Eratosthenes in Scala

June 19, 2009 8:20 p.m.

Lately, I have been interested in the Scala programming language. It is actually quite nice, and seems to really work with me and not against me. I really like the way the functional aspects are combined with imperative, as it makes it so much easier to think about things when my mind is not in a pure-functional mindset.

Here’s one little snippet that I’ve been working on to learn some Scala, another sieve of eratosthenes. It will work if pasted into the scala interpreter, and then just call the primes function.

def primes_aux(currentList:List[Int], stopNumber:Int) : List[Int] = {
  if(currentList == Nil)
    Nil
  else {
    val H = currentList.head
    if (H <= stopNumber)
       H :: primes_aux(currentList.tail.remove(num => (num % H) == 0), stopNumber)
    else
      currentList
  }
}

def primes(maxNumber:Int) : List[Int] = {
  primes_aux((2 to maxNumber).toList, Math.sqrt(maxNumber))
}

I tried really hard to shrink the code from the erlang version, and I was successful. It is much more succint. I will probably find some better functions that can help me get rid of or at least simplify the logic. I have a feeling this can be done in a few short lines of code.

comments powered by Disqus