On Mon, Nov 2, 2009 at 1:59 PM, Will Ness
Will Ness
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!
:) :)
If you are okay with Int, then maybe you're also happy with Int32 or Word32. If so, why don't you use template haskell to build the list at compile time? If you do that, then getting the kth prime at run-time is O(k). Take that AKS! :) Jason