smallPrimeFactors.hs

-- Adapted from
-- https://www.haskell.org/haskellwiki/Generic_number_type#squareRoot
floorSqrt :: Integer -> Integer
floorSqrt 0 = 0
floorSqrt 1 = 1
floorSqrt n =
    let powers = iterate (^2) 2
        (lowerRoot, lowerN) =
            last $ takeWhile ((n>=) . snd) $ zip (1:powers) powers
        newtonStep x = (x + (n `div` x)) `div` 2
        iters = iterate newtonStep (floorSqrt (n `div` lowerN) * lowerRoot)
        isRoot r = r^2 <= n && n < (r+1)^2
    in head $ filter isRoot iters

-- This only finds prime factors that are smaller than floorSqrt n, but that's
-- good enough for this problem.
smallPrimeFactors :: Integer -> [Integer]
smallPrimeFactors n = snd $ foldl aggregate (n, []) (2 : [3, 5 .. floorSqrt n])
    where aggregate (n', fs) f | n' `mod` f == 0 = (n' `div` f, f : fs)
                               | otherwise = (n', fs)