Finding primes using a primes map with Haskell and Hugs98

[Hannah Schroeter]

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.