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. :) _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
