# Finding primes using a primes map with Haskell and Hugs98

**Simon Peyton-Jones
**
simonpj@microsoft.com

*Tue, 19 Dec 2000 06:58:41 -0800*

|* Another way to do this is to compute the final array directly,
*|* instead of computing successive versions of the array:
*|*
*|* import Array
*|* primes n = [ i | i <- [2 ..n], not (primesMap ! i)] where
*|* primesMap = accumArray (||) False (2,n) multList
*|* multList = [(m,True) | j <- [2 .. n `div` 2], m <-
*|* multiples j]
*|* multiples j = takeWhile (n>=) [k*j | k <- [2..]]
*
This style is definitely the way to go. Haskell does badly
if you update an array one index at a time.
Remember that arrays can be recursive. Here's a definition
of Fibonacci for example; you can probably adapt it for primes
fibs :: Int -> Array Int Int
-- If a = fibs n, then a!i is fib(i), for i<=n.
fibs n = a
where
a = array (1,n) ([(1,1),(2,1)] ++ [(i,a!(i-1) + a!(i-2) | i <-
[3..n]])
-- Notice that a is recursive
Simon