CODEWITHSUNDEEP
performancehaskellprimesprime-factoring
dylhunn
dylhunn

Reputation: 1434

My Haskell Solution to Euler #3 is Inefficient

I am attempting to solve Euler problem 3 in Haskell, which involves finding the largest prime factor of a number. My code runs for a long time and seems to hang. What is causing my code to be so grossly inefficient?

primes = sieve (2:[3,5..])
 where sieve (x:xs) = x:[y | y <- (sieve xs), mod y x /= 0]
       sieve [] = []
primefactors n = filter (\x -> mod n x == 0) (primesUnder n)
 where primesUnder z = reverse (takeWhile (< z) primes)
solve3 = head (primefactors 600851475143)

Upvotes: 1

Views: 313

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 152817

Your main problem is you're checking for enormous primes -- all the way up to 600851475143. You can improve things a lot by observing two things:

  1. Every time you find a prime, you can decrease the maximum prime you look at by dividing away that factor.
  2. You only have to look for primes until you reach the square root of the target. If your primes are bigger than that, and you know there are no smaller factors, you're done.

Using these two improvements together, even without the nicety that you used of only checking primes for divisibility, makes the program run in a snap:

factor = go (2:[3,5..]) where
    go (p:ps) n
        | p*p > n        = [n]
        | n `mod` p == 0 = p : go (p:ps) (n `div` p)
        | otherwise      = go ps n
main = print . last . factor $ 600851475143

In ghci:

*Main> main
6857
(0.00 secs, 0 bytes)

You can see that we only had to inspect numbers up to 6857 -- eight orders of magnitude smaller than what you would have to do with your approach.

Independently, your sieve is dog slow. You could have a look at the wiki for ideas about how to find primes quickly.

Upvotes: 12

Related Questions