# Project Euler #3 in Haskell

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.

• cf. this answer with a pseudocode which should be easy enough to turn into a valid Haskell. – Will Ness Jan 6 '15 at 22:40

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

• 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! – wei2912 Dec 24 '14 at 4:24
• The program completes in 0.02 sec. I wouldn't bother with premature optimization. – 200_success Dec 24 '14 at 4:32
• 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 Dec 24 '14 at 6:45
• 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. – wei2912 Dec 24 '14 at 6:48