On Nov 2, 2009, at 5:11 PM, Will Ness wrote:
Sjoerd Visscher
writes: Excuse me, 2 doesn't have to be in the list of smaller primes, as we're only generating odd numbers:
primes = 2 : 3 : 5 : 7 : sieve [3] (drop 2 primes) sieve qs@(q:_) (p:ps) = [x | x<-[q*q+2,q*q+4..p*p-2], and [(x`rem`p)/=0 | p<-qs]] ++ sieve (p:qs) ps
Sjoerd
Hi,
I've run it now. In producing 100,000 primes, your above code takes x3.5 more time than the one I posted.
Too bad. The order of the primes when filtering matters quite a lot!
The code modified as I suggested with (qs++[p]) takes exactly the same time as mine. :)
Yes, append and take are both O(n). Here's another variation which I rather like: primes = 2 : 3 : sieve (tail primes) (notDivides 3) 5 sieve (p:ps) test from = [x | x <- [from, from + 2 .. p * p - 2], test x] ++ sieve ps (\x -> test x && notDivides p x) (p * p + 2) notDivides d x = (x `rem` d) /= 0 I'm curious if GHC can compile this to the same speed as your code. -- Sjoerd Visscher sjoerd@w3future.com