"Rafael Almeida"
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.
What you have here, is not a sieve (in my opinion) as any implementation that uses `mod`. The characteristics of a sieve is, that it uses the already found primes to generate a list of non-primes that is then removed from a list of candiates for primeness. The salient point is, that there should be no test divisions, but rather only comparisons. In the imperative version the comparisons are implicit (in the process of marking the array positions), but there are no test divisions. A real sieve should look like this (IMHO) http://www.etc-network.de/blog/mel/programming/how-to-spend-midnight.html#ho... This is my implementation, please, forgive my shameless self-advertisment :-). Regards -- Markus