我对欧拉#3的Haskell解决方案效率低下

Question

我试图解决Haskell中的Euler问题3,它涉及找到数字的最大素数因子.我的代码运行了很长时间,似乎挂了.是什么导致我的代码如此低效？

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)

Answer 1

你的主要问题是你正在检查巨大的素数 - 一直到最后600851475143.你可以通过观察两件事来改进很多事情:

1. 每当你找到素数时,你可以通过除去那个因子来减少你看到的最大素数.
2. 您只需要找到素数,直到达到目标的平方根.如果你的素数大于那个,并且你知道没有更小的因素,你就完成了.

将这两个改进结合在一起,即使没有使用仅仅检查素数以实现可分性的精确性,也可以使程序快速运行:

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

在ghci:

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

你可以看到我们只需要检查数字6857- 比你的方法要小8个数量级.

独立地,你的筛子是狗慢.您可以查看维基以获取有关如何快速找到素数的想法.