[Haskell-cafe] Re: Optimization fun

Rafael Almeida almeidaraf at gmail.com
Sat Feb 10 21:01:07 EST 2007


I've always found the following definition of the sieve of eratosthenes
the clearest definition one could write:

sieve [] = []
sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0]

It doesn't perform better than Augustsson's solution. It does fairly
worse, actually, but it performs way better than Hogg's 13s algorithm.
It took around 0.1s on my machine.

You should call the function like this

sieve [2..n]

where n is to what number you want to calculate the sieve. I could also
have used filter instead of the list comprehension.


More information about the Haskell-Cafe mailing list