Finding primes using a primes map with Haskell and Hugs98

[Adrian Hey]

On Fri 15 Dec, Shlomi Fish wrote:
> There is a different algorithm which keeps a boolean map which tells whether
> the number at that position is prime or not. At start it is initialized to all
> trues. The algorithm iterates over all the numbers from 2 to the square root
> of the desired bound, and if it encounters a prime number it marks all the
> numbers p*p, p*p+p, p*p+2*p, p*p+3*p, etc. as not prime. It is generally
> considered a better algorithm than the previous one, because it uses less
> costier operations (multiplications and additions instead of modulos.)

Functional programming languages are notoriously ineffecient at array
handling (though I'm not sure exactly what the various Haskell
implementations actually do).

You can use a variation of this algorithm with lazy lists..

primes = 2:(get_primes [3,5..])
get_primes (x:xs) = x:(get_primes (strike (x+x) (x*x) xs))

strike step x_now (x:xs) = 
 case (compare x_now x) of
 LT -> strike step (x_now+step) (x:xs)
 EQ -> strike step (x_now+step) xs
 GT -> x:(strike step x_now xs)

The equivalent program in Clean (on a MAC) gets upto 877783 before giving a
stack overflow error (1000K of stack, 4000K of Heap allocated). (I haven't
actually tried this in Haskell 'cos I don't have a Windoze or 'nix box.)

Regards
-- 
Adrian Hey