我对Euler Project#3的解决方案太慢了

Question

我是Haskell的新手并且在修改欧拉项目问题.我对问题#3的解决方案太慢了.起初我试过这个:

-- 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

然后我改变它以返回所有x而不仅仅是最大的一个.

problem3 = [ x | x <- [1..n], (mod n x) == 0, n /= x]
        where n = 600851475143

30分钟后,列表仍在处理中,输出如下所示

[1,71,839,1471,6857,59569,104441,486847,1234169,5753023,10086647,87625999,408464633,716151937

为什么这么慢？我做了一件非常错误的事情,或者这种任务是否正常？

Answer 1

使用您的解决方案,可能有大约6000亿个数字.正如德尔南所指出的那样,每次检查数字都不会产生太大影响,我们必须限制候选人的数量.

您的解决方案似乎也不正确.59569 = 71 * 839不是吗？这个问题只询问主要因素.请注意,71并且839在您的列表中,以便您正在做正确的事情.事实上,你正试图找到所有因素.

我认为通过在继续之前将因素分开来获得最显着的效果.

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

这似乎是一个明显的优化,但它依赖于一个事实,即如果两个a和b分歧c,并a是互质b然后a分c/b.

如果你想做更多,这里提到了常见的"只检查直到平方根"的技巧.同样的技巧可以应用于这个问题,但不幸的是,在这个实例上没有显示性能提升:

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

这里,当候选者大于剩余数字(num)的平方根时,我们知道num必须是素数,因此是原始数字(600851475143)的素数因子.

仅通过考虑素数就可以删除更多的候选者,但这稍微提高一点,因为你需要制定一种合理的生成素数的方法.有关执行此操作的方法,请参阅此页面.