4
\$\begingroup\$

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.

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

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
\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – trichoplax Jul 28 '14 at 12:58
  • \$\begingroup\$ @githubphagocyte But it works. The function factors out the 2 and produces 19. \$\endgroup\$ – 200_success Jul 29 '14 at 2:27
  • \$\begingroup\$ 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. \$\endgroup\$ – trichoplax Jul 29 '14 at 8:54
  • \$\begingroup\$ @githubphagocyte As specified by (2 : [3, 5..]), it is testing factors in this sequence: 2, 3, 5, 7, 9, 11, 13, …. \$\endgroup\$ – 200_success Jul 29 '14 at 12:23
  • \$\begingroup\$ @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. \$\endgroup\$ – gnasher729 Nov 4 '15 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.