Computation for finding the largest prime factor of 600851475143 is slow

Question

I implemented the following for Project 3 in Project Euler:

--Problem 3. The prime factors of 13195 are 5, 7, 13 and 29. What is the
--largest prime factor of the number 600851475143?

prime :: Integer -> Bool
prime x = prime' x (x `div` 2) where
          prime' _ 1 = True
          prime' x y = if x `mod` y == 0 then False
                       else prime' x (y - 1)

largestPrimeFactor :: Integer => Maybe Integer
largestPrimeFactor x = largestPrimeFactor' x (x `div` 2)                       
             where largestPrimeFactor' _ 1 = Nothing
                   largestPrimeFactor' x y = if x `mod` y == 0 && prime y then Just y
                                             else largestPrimeFactor' x (y - 1)

I was able to get Just 29 per the introduction to this problem from Project Euler:

*Main> largestPrimeFactor 13195
Just 29
*Main> largestPrimeFactor 600851475143 -- running for (as of now) 15 hours!

My implementation succeeded for getting 29 from 13195, but the computation for 600851475143 has been running for 15 hours so far.

Please review my implementation for correctness and idiomatic Haskell.

Answer 1

Your algorithm doesn't scale. In this answer, I've outlined the three common strategies for finding the largest prime factor of a number, only one of which is reasonably efficient. You've chosen Option 2 (testing largest candidates first, then check for primality). However, you start at \$\lfloor\frac{n}{2}\rfloor\$ rather than \$\lceil\sqrt{n}\rceil\$, which is even less efficient, and furthermore it incorrectly produces Nothing whenever n is already prime.

Here's a Haskell implementation of Option 3 (testing smallest candidates first):

largestPrimeFactor :: Integer -> Maybe Integer
largestPrimeFactor n
  | n <= 1    = Nothing
  | otherwise = Just $ largestPrimeFactor' n (2 : [3, 5..])
  where
    largestPrimeFactor' n pseudoprimeCandidates@(c:cs)
      | c * c >= n = n
      | m == 0     = largestPrimeFactor' d pseudoprimeCandidates
      | otherwise  = largestPrimeFactor' n cs
      where
        (d, m) = divMod n c

Personally, I'd avoid contaminating the output with Maybe, since Nothing will only result from obviously illegal input anyway.

largestPrimeFactor :: Integer -> Integer
largestPrimeFactor n
  | n <= 1    = error "largestPrimeFactor n where n <= 1"
  | otherwise = largestPrimeFactor' n (2 : [3, 5..])
  where
    largestPrimeFactor' n pseudoprimeCandidates@(c:cs)
      | c * c >= n = n
      | m == 0     = largestPrimeFactor' d pseudoprimeCandidates
      | otherwise  = largestPrimeFactor' n cs
      where
        (d, m) = divMod n c