Primes

import Data.Map as Map

primes1 = 2 : Prelude.filter isPrime [3..]

isPrime x = check primes1 where
    check (p:ps) | p*p > x        = True
                 | x `mod` p == 0 = False
                 | otherwise      = check ps


primes2 = primes' [2..] Map.empty
    where
      primes' [] table = []
      primes' (x:xs) table =
          case Map.lookup x table of
            Nothing -> x: primes' xs (Map.insert (x*x) [x] table)
            Just facts -> primes' xs (Prelude.foldl reinsert (Map.delete x table) facts)
                where
                  reinsert table prime = Map.insertWith (++) (x+prime) [prime] table