My Haskell Solution to Euler #3 is Inefficient

Question

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)

Schafer

This question is better suited for codereview.stackexchange.com – Dashiell

@Dashiell What is the distinction between the requests for help that should be posted on StackOverflow and the similar questions on StackExchange? – Schafer

Answer 1

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.

Queridas

#1 was the most significant part of the problem. Thank you! – Schafer

Note that when run with --ghc-options="-Werror", this code will fail to compile because of incomplete pattern matching. To make it work, insert go [] n = [n] – Sagittal