[Haskell-cafe] Re: Simple FAST lazy functional primes

[Will Ness]

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.

:)