Perhaps you might want include in your test the following: http://www.haskell.org/pipermail/haskell-cafe/2007-February/022437.html It seems quite close to the genuine Eratosthenes sieve algorithm: it employs the idea of marks, it can cross composite numbers off several times, and it never tries to divide or examine prime numbers. In fact, the algorithm doesn't even use the full division or full comparison (let alone other arithmetic operations).