i have to say that i find the folklore sieve quite acceptable as a sieve, whereas the faster test-against-primes is obviously different. but the discussion has prompted me to write yet another sieve, perhaps more acceptable to purists. instead of using (mod p) repeatedly and filtering directly, we zero out multiples of p, for all p, then filter out non-zero elements in a second phase: primes = 2 : filter (>2) (foldr sieve id primes [0..]) -- start sieve for p at position p*p, zeroing position off=(p-1)*(p-1) sieve p f xs@(off:_) = 0: tail (applyAt (p*p-off) (f . sieve' p) xs) -- zero positions that are multiples of p sieve' p = applyAt p (\(_:b)->sieve' p (0:b)) -- like splitAt, followed by (++), where only suffix is operated on -- infinite lists, non-negative offset applyAt 0 f xs = f xs applyAt n f (x:xs) = x:applyAt (n-1) f xs it seems to be a lot faster than the folklore sieve, and within a factor of 2 of the faster test-against-primes (given the repeated use of applyAt, I guess it could be sped up further by using a piecewise contiguous list representation, aka polymorphic ByteString). claus