Project Euler # 3 in Haskell: largest prime factor of some number

Question

The program works, but is extremely slow.

Project Euler problem 3

Problem: What is the largest prime factor of the number 600851475143?

module Problem_3 where
-- find largest prime factor:
findLargestPrimeFactor :: [Int] -> Int
findLargestPrimeFactor [] = 1
findLargestPrimeFactor (n:ns) = 
 if (isPrime n)
 then n
 else findLargestPrimeFactor ns
-- Supplementary function definitions:
-- function: listOfFactors n
listOfFactors :: Int -> [Int]
listOfFactors n = [x | x <- [1..n], isFactor x]
 where
 isFactor x = (n `mod` x == 0)
-- function: isPrime p
isPrime :: Int -> Bool
isPrime p = (p >= 2 && listOfFactors p == [1,p]) 
main = do 
 let myGivenNumber = 600851475143
 let largestPrimeFactor = findLargestPrimeFactor (reverse (listOfFactors myGivenNumber))
 print largestPrimeFactor

• Zeta: I'm afraid this question does not match what this site is about. Code Review is about improving existing, working code. Code Review is not the site to ask for help in fixing or changing what your code does. Once the code does what you want, we would love to help you do the same thing in a cleaner way! Please see our help center for more information.
• UGPhysics: Where do I get that sort of help then?
• Zeta: Your code does not work? StackOverflow. Your code does work and you want to know what you can do better? Here. But at the moment, your code does not even type check, therefore it's off-topic at the moment. Also, add more information. Just the problem statement and code isn't really a well written description.
• UGPhysics: - Ask Moderator/s to send to SO?
• πάντα ῥεῖ: @UGPhysics No need for moderators, you can just delete your question here and reask it at SO.

Answer 1

Naming

findLargestPrimeFactor isn't true to its name. It just returns the first prime number in the given list or 1 otherwise. So firstPrime :: [Int] -> Int might be more apt.

Efficency

At the moment, you check \$ n \$ candidates in listOfFactors. But that's not necessary. First of all, if we found a divisor x, then we also found a second divisor, n `div` x. We also only need to check x up to \$ \sqrt{n}\$:

listOfFactors :: Int -> [Int]
listOfFactors n = concat [[x,d] | x <- [1..nsqrt], let (d,m) = n `divMod` x, m == 0]
 where
 nsqrt = ceiling (sqrt (fromIntegral n))

Now we only need to check \$\left\lceil \sqrt{600851475143}\right\rceil = 775147\$ numbers, which is much, much less. This variant will actually finish in under one second, whereas I didn't run my program till the end.

However, you now have to sort your list, or use filter isPrime followed by maximum in findLargestPrimeFactor, whose name would be then mostly (beside the Factor) apt.

If you rewrite findLargestPrime so that it returns the largest prime from a given list, we would end up with the following main:

main :: IO ()
main = print (findLargestPrime (listOfFactors 600851475143))

Which seems reasonable.

Another approach

While one can solve this problem in this way, one can also just generate the prime factors of the number:

primeFactors :: Int -> [Int]
primeFactors n = go 2 n
 where
 go _ 1 = []
 go k n = case n `quotRem` k of
 (n', 0) -> k : go k n'
 _ -> go (k + 1) n'

If k is going to be put in the list, it will always be prime. Note that one can improve this function further, but that's left as an exercise.

Exercises

• In the section "efficency", we were able to reduce the runtime by narrowing the search space. However, why is it enough to run up to $\ \sqrt{n} \$ only?
• In the section "another approach", one can cut the amount of checked numbers almost by half. How?

• UGPhysics: what is the answer for the question then?
• Zeta: @UGPhysics for what question? The one given by Project Euler?
• UGPhysics: ceil in nsqrt = ceil (sqrt (fromIntegral n)) returns error: Variable not in scope: ceil :: Double -> t
• Zeta: @UGPhysics typo, meant ceiling (which is called ceil in the other languages I usually use), sorry.
• Gurkenglas: listOfFactors n = foldr (.) id [((d:) .) . (. (x:)) | x <- [1..nsqrt], let (d,m) = n `divMod` x, m == 0] id [] puts the factors in descending order immediately.