primefactorisation.hs

divides k n = rem n k == 0

sieve :: [Integer] -> [Integer]
sieve [] = []
sieve (0:xs) = sieve xs
sieve (1:xs) = sieve xs
sieve (x:xs) = x : sieve (removeMultiplesOf x xs)
               where
                 removeMultiplesOf x xs = filter (not . divides x) xs

primes = sieve [1..]

factorise :: Integer -> [Integer]
factorise 0 = []
factorise 1 = [1]
factorise n = factorise' primes n
              where
                factorise' ps@(p:xs) n
                    | p `divides` n = p : factorise' ps (n `div` p)
                    | n == 1 = []
                    | otherwise = factorise' xs n