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

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?