project euler 3

pe3.hs

-- http://projecteuler.net/index.php?section=problems&id=3
--
-- The prime factors of 13195 are 5, 7, 13 and 29.
--
-- What is the largest prime factor of the number 600851475143?

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

main :: IO ()
main =
    print (answer n)
  where
    n = 600851475143

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

answer :: Integer -> Integer
answer = fst . head . primeFactors

primes :: [Integer]
primes =
    seive [2..]
  where
    seive ns =
        let p   = head ns
            ns' = cull (p `divides`) (tail ns)
        in p : seive ns'
    cull = filter . (not .)

primeFactors :: Integer -> [(Integer,Integer)]
primeFactors n =
    factor n [] primes
  where
    factor 1 fs _  = fs
    factor x fs ps =
        let (p:ps') = ps
        in if p `divides` x
             then let (x',e) = x `castOut` p
                      fs'    = (p,e):fs
                  in factor x' fs' ps'
             else factor x fs ps'

castOut :: Integer -> Integer -> (Integer,Integer)
castOut i f =
    calc i 0
  where
    calc j n =
        let (q,r) = j `divMod` f
        in if r == 0
             then calc q (succ n)
             else (j, n)

divides :: Integral a => a -> a -> Bool
divides d n = mod n d == 0