# Computation for finding the largest prime factor of 600851475143 is slow

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.

• You sure this isn't an issue with large number? Like an overflow or something like that? Did you try some other primes? – Carlos Jul 27 '14 at 21:14
• According to hoogle, Integer is an arbitrary precision length. – Kevin Meredith Jul 27 '14 at 21:20

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

• The largest prime factor can be as large as n/2. For example 19 * 2 = 38. Note that 19 > sqrt(38). This would need to be taken into account if working down from sqrt(n). – trichoplax Jul 28 '14 at 12:58
• @githubphagocyte But it works. The function factors out the 2 and produces 19. – 200_success Jul 29 '14 at 2:27
• Ah I see. So in that particular case it is slightly slower to start at sqrt(n) than to start at n/2, but in cases where the largest prime factor isn't n/2 it would be much faster to start at sqrt(n) because the range between sqrt(n) and n/2 is much bigger than the range less than sqrt(n)? I think I get it now. – trichoplax Jul 29 '14 at 8:54
• @githubphagocyte As specified by (2 : [3, 5..]), it is testing factors in this sequence: 2, 3, 5, 7, 9, 11, 13, …. – 200_success Jul 29 '14 at 12:23
• @trichoplax: The number here is around 600 billion. It is not even, so n/2 (about 300 billion) is not a factor. Then all the numbers between n/3 and n/2, that's about 100 billion, cannot possibly be factors of n! And after that, none of the numbers between n/4 and n/3 (that is 50 billion numbers between 150 and 200 billion) cannot be factors of n. – gnasher729 Nov 4 '15 at 22:54