Project Euler #3 in Haskell

Question

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.

• Will Ness: cf. this answer with a pseudocode which should be easy enough to turn into a valid Haskell.

Answer 1

You don't need to terminate the list of candidate factors. Haskell, being a lazy language, deals with infinite lists just fine.

In Haskell, it is common to use pattern matching instead of if ... then ... else.

There is not much advantage to having your go helper take an Integer (Integer, Integer) rather than three Integers.

You are repeating the isDiv test in fullyDiv and go. Instead of a fullyDiv function, you can just fold the retry logic into go itself.

The names x, y, and o are hard to follow. I suggest maxPrime instead of x, and w instead of y (the mnemonic being the first character of wheel).

isDiv :: Integer -> Integer -> Bool
n `isDiv` k = n `mod` k == 0
maxPrimeFact :: Integer -> Integer
maxPrimeFact n = go n 1 (2 : [3, 5..])
 where
 go 1 maxPrime _ = maxPrime
 go n maxPrime wheel@(w:ws)
 | n `isDiv` w = go (n `div` w) w wheel
 | otherwise = go n maxPrime ws

But you should be able to rewrite it further by taking advantage of divMod.

maxPrimeFact :: Integer -> Integer
maxPrimeFact n
 | n < 2 = error ("Invalid n=" ++ (show n))
 | otherwise = go n 1 wheel
 where
 wheel = 2 : [3, 5..]
 go 1 largestPrimeFactor _ = largestPrimeFactor
 go n largestPrimeFactor (w:ws)
 | n `isDiv` w = go (n `div` w) w (w:ws)
 | otherwise = go n largestPrimeFactor ws

• wei2912: It appears that the go function you wrote would iterate all the way till the maximum prime. The reason why I wrote the function as such was to reduce the search space (refer to my answer which I referred above). Otherwise, thanks for the excellent suggestions!
• 200_success: The program completes in 0.02 sec. I wouldn't bother with premature optimization.
• wei2912: I'm actually using this program in hackerrank.com/contests/projecteuler/challenges where it errors out in the last case: hackerrank.com/contests/projecteuler/challenges/euler003/….
• wei2912: I made the change and it passes all tests: hackerrank.com/contests/projecteuler/challenges/euler003/…. Anyways, thanks for the new maxPrimeFact function; I'll mark your answer as accepted.