Project Euler #3 asks:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
I've written a general solution for any number:
module Main where isDiv :: Integer -> Integer -> Bool n `isDiv` k = n `mod` k == 0 fullyDiv :: Integer -> Integer -> Integer fullyDiv n k | n `isDiv` k = fullyDiv (n `div` k) k | otherwise = n intSqrt :: Integer -> Integer intSqrt = floor . sqrt . fromIntegral maxPrimeFact :: Integer -> Integer maxPrimeFact n = go n (1, wheel) where wheel = 2 : [3,5..intSqrt n] go n (x, ) = if n == 1 then x else n go n (x, (y:ys)) | n `isDiv` y = let o = fullyDiv n y in go o (y, takeWhile (<= intSqrt o) ys) | otherwise = go n (x, ys) problem3 :: Integer -> Integer problem3 = maxPrimeFact main :: IO () main = do _ <- getLine contents <- getContents let cases = map read $ lines contents let results = map problem3 cases mapM_ print results
An explanation of this algorithm can be found at my answer.
I'd appreciate any comments on rewriting
maxPrimeFact as it seems unwieldy to me.