Sieve of Eratosthenes

This is my response to the Scala slide in the "JavaOne Talk: Performance Comparisons of Dynamic Languages on the Java Virtual Machine" presentation. In particular, the Scala example seemed quite verbose and "unscalalike", so I thought I would see what I could quickly knock up. It's the Sieve of Eratosthenes (sort of - it's recursive and it doesn't bother with Step 5 of the algorithm on the Wikipedia page, so it does more work than is needed).

It's quick and dirty and could stand to be improved - my main motivation was to show that it could be done quickly and in a lot fewer lines in Scala than was shown on the presentation slide so it's not the greatest example of code ever written. I've put it up here because blogger's commenting system nukes source code layout.

def primes(n: Int): List[Int] = {
        def nomults(s: Int, xs: Seq[Int]): List[Int] = (for (x <- xs if x % s != 0) yield x).toList
        def sieve(xs: List[Int]): List[Int] = {
                if (xs.isEmpty) xs
                else {
                        val p = xs.first
                        val nxs = nomults(p, xs drop 1)
                        p :: sieve(nxs)
                }
        }

        val odds = nomults(2, 2 to n)
        2 :: sieve(odds)
}

println( primes(100) )