It’s the second famous Haskell example to illustrate its elegance and succinctness, only after quicksort. Non-surprisingly, it’s not
implementing the original algorithm just like the quicksort case. Well, in Haskell’s defense, it’s actually implementing the non-refined version
specified in https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
This paper gives a though analysis on this problem, and is fairly readable. The following code
is basically a reprint of the code in that paper.
The benchmark result is a bit different from the one in the paper, that it claims that fast_seive runs faster for practical size n, while trivial
division on my machine is slightly faster. (Using ghc 7.10.3 on ubuntu 14.04.)