gistfile1.hs

import Data.Map
import Prelude hiding (lookup)

primes :: [Integer]
primes = sieve [2..]

sieve :: [Integer] -> [Integer]
sieve xs = sieve' xs empty

sieve' :: [Integer] -> Map Integer [Integer] -> [Integer]
sieve' (x:xs) table = case lookup x table of
    Nothing    -> x : sieve' xs (insert (x*x) [x] table)
    Just facts -> sieve' xs (foldl reinsert (delete x table) facts)
  where
    reinsert tbl prime = insertWith (++) (x+prime) [prime] tbl
sieve' _ _ = error "sieve'"