On Nov 2, 2009, at 5:11 PM, Will Ness wrote:
Sjoerd Visscher <sjoerd <at> w3future.com> 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
[email protected]
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
