Hello! On Wed, Dec 20, 2000 at 04:02:23PM +0200, Shlomi Fish wrote:
[...]
primes :: Int -> [Int] primes how_much = sieve [2..how_much] where sieve (p:x) = p : (if p <= mybound then sieve (remove (p*p) x) else x) where remove what (a:as) | what > how_much = (a:as) | a < what = a:(remove what as) | a == what = (remove (what+step) as) | a > what = a:(remove (what+step) as) remove what [] = [] step = (if (p == 2) then p else (2*p)) sieve [] = [] mybound = ceiling(sqrt(fromIntegral how_much))
[...]
How about this: Yet another infinite list version, however only sieving numbers to the square of the current maximum: primes :: [Int] primes = 2:fil' 4 primes [3..] where fil' cutoff fl@(f:fs) rl@(r:rs) = if r < cutoff then r:fil' cutoff fl rs else fil' (square (head fs)) fs [y|y<-rl, (y `mod` f) /= 0] square x = x*x Comparison: my version (with a small main around it): hannah@mamba:~/src/haskell $ time ./primes 1000000 >/tmp/p1 real 0m31.928s user 0m31.690s sys 0m0.317s your version (with adapted small main around it): hannah@mamba:~/src/haskell $ time ./primes2 1000000 >/tmp/p2 real 0m42.993s user 0m42.023s sys 0m0.236s (measurements with ghc 4.08, -O2 -O2-for-C, Pentium I 200 MHz 64 MB RAM) The outputs (primes list + number of found primes) are the same. In contrast, take the simple two-liner primes :: [Int] primes = p' [2..] where p' (p:ps) = p:p' [y|y<-ps, (y `mod` p) /= 0] with the same small main: hannah@mamba:~/src/haskell $ time ./primes0 100000 >/tmp/p0 real 2m17.460s user 2m15.773s sys 0m1.170s (mine with 100000 limit) hannah@mamba:~/src/haskell $ time ./primes 100000 >/tmp/p1 real 0m1.666s user 0m1.607s sys 0m0.048s (yours with 100000 limit) hannah@mamba:~/src/haskell $ time ./primes2 100000 >/tmp/p2 real 0m1.903s user 0m1.827s sys 0m0.064s Kind regards, Hannah.