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.

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