[Haskell-cafe] Re: Simple FAST lazy functional primes
will_n48 at yahoo.com
Mon Nov 2 15:59:07 EST 2009
Will Ness <will_n48 <at> yahoo.com> writes:
> 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.
More information about the Haskell-Cafe