Functional Sieve of Eratosthenes [pdf]

[likpok]

http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

[rawr]

The following page gives implementations in 33 different languages:

http://www.scriptol.com/programming/sieve.php

Of course, many of them (including the Haskell implementation) fall victim to the criticism presented in this paper.