My solution for Euler Project #3 is too slow

haskell, prime-factoring, primes

Solution

With your solution, there are about 600 billion possible numbers. As noted by delnan, making every check of the number quicker is not going to make much difference, we must limit the number of candidates.

Your solution does not seem to be correct either. `59569 = 71 * 839` isn't it? The question only asks for prime factors. Notice that `71` and `839` is in your list so you are doing something right. In fact, you are trying to find all factors.

I think the most dramatic effect you get simply by dividing away the factor before continuing.

euler3 = go 2 600851475143
  where
    go cand num
      | cand == num           = [num]
      | cand `isFactorOf` num = cand : go cand       (num `div` cand)
      | otherwise             =        go (cand + 1) num

isFactorOf a b = b `mod` a == 0

This may seem like an obvious optimization but it relies on the fact that if both `a` and `b` divides `c` and `a` is coprime to `b` then `a` divides `c/b`.

If you want to do more, the common "Only check until the square root" trick has been mentioned here. The same trick can be applied to this problem, but the performance gain does not show, unfortunately, on this instance:

euler3 = go 2 600851475143
  where
    go cand num
      | cand*cand > num       = [num]
      | cand `isFactorOf` num = cand : go cand       (num `div` cand)
      | otherwise             =        go (cand + 1) num

isFactorOf a b = b `mod` a == 0

Here, when a candidate is larger than the square root of the remaining number (`num`), we know that `num` must be a prime and therefore a prime factor of the original number (`600851475143`).

It is possible to remove even more candidates by only considering prime numbers, but this is slightly more advanced because you need to make a reasonably performant way of generating primes. See this page for ways of doing that.

Problem

I'm new to Haskell and tinkering around with the Euler Project problems. My solution for problem #3 is far too slow. At first I tried this: ``` -- Problem 3 -- The prime factors of 13195 are 5, 7, 13 and 29. -- What is the largest prime factor of the number 600851475143 ? problem3 = max [ x | x <- [1..n], (mod n x) == 0, n /= x] where n = 600851475143 ``` Then I changed it to return all `x` and not just the largest one. ``` problem3 = [ x | x <- [1..n], (mod n x) == 0, n /= x] where n = 600851475143 ``` After 30 minutes, the list is still being processed and the output looks like this `[1,71,839,1471,6857,59569,104441,486847,1234169,5753023,10086647,87625999,408464633,716151937` Why is it so slow? Am I doing something terribly wrong or is it normal for this sort of task?

Original source