Finding primes using a primes map with Haskell and Hugs98

Simon Peyton-Jones [email protected]
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