Will Ness
primes = 2: 3: sieve 0 primes' 5 primes' = tail primes sieve k (p:ps) x = [x | x <- [x,x+2..p*p-2], and [(x`rem`p)/=0 | p <- take k primes']] ++ sieve (k+1) ps (p*p+2)
(thanks to Leon P.Smith for his brilliant idea of directly generating the spans of odds instead of calling 'span' on the infinite odds list).
The relative performance vs the PQ-version is:
100,000 300,000 1,000,000 primes produced 0.6 0.75 0.97
One _crucial_ tidbit I've left out: _type_signature_. Adding (:: [Int]) speeds this code up more than TWICE! :) :) 'sieve' can also be used in e.g. primesFrom m = sieve (length h) ps m where (h,(_:ps)) = span (<= (floor.sqrt.fromIntegral) m) primes to get few big primes even faster. :)