It turns out that you can implement the core of Erastothenes’ Sieve in one line of Scala code:
def sieve(stream: Stream[Int]): Stream[Int] = stream.head #:: sieve(stream.tail.filter(k => k%sieve.head != 0))
(btw the #:: sign is for prepending an element to a Stream[T] object)
Now, I cheated a bit and you still have to call the sieve function with a stream of all Int’s > 1. But this is not verbose at all:
def from(n: Int): Stream[Int] = n #:: from(n+1) sieve(from(2))
So after all, it turns out that we need five lines really. But I hope you will agree that this implementation of The Sieve is very elegant.