# Finding primes using a primes map with Haskell and Hugs98

**Adrian Hey
**
ahey@iee.org

*Sun, 17 Dec 2000 11:59:43 +0000 (GMT)*

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