Haskell，了解 euler #3 的解决方案

Question

我最近开始学习 Haskell，并且度过了一段愉快的时光。我一直在解决一些欧拉项目问题以掌握语法，并一直在审查此处发布的解决方案 http://www.haskell.org/haskellwiki/Euler_problems/1_to_10作为学习工具。尽管我发现自己无法理解为 problem #3 发布的解决方案:

-- Find the largest prime factor of 317584931803. 

primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

primeFactors n = factor n primes
  where
    factor n (p:ps) 
        | p*p > n        = [n]
        | n `mod` p == 0 = p : factor (n `div` p) (p:ps)
        | otherwise      = factor n ps

problem_3 = last (primeFactors 317584931803)

我一生都无法弄清楚它是如何工作的。 primes 和 primeFactors 似乎在互相调用来构建自己的列表，并试图遵循它，这让我的大脑感到困惑。有人知道关于此解决方案的一篇不错的博客文章或者想在这里写一篇解释吗？

Answer 1

乍一看确实令人费解。但如果你不“势在必行”地思考，这就不是什么魔法。 Haskell 定义就是这样:告诉你什么东西是什么，而不是计算机应该执行什么较低级别的操作。

因此，素数列表是包含 2 和所有大于 2 且只有一个素因数(即其自身)的奇自然数的列表。

另一方面，某个整数 n 的质因数列表是整除 n 的质数列表。

在继续阅读之前，请确保您理解这些定义。

尽管 Haskell 很抽象，但它仍然是一种编程语言，因此我们需要不时地给出一些建议如何来计算某些东西。具体来说，在上面的示例中，我们不测试所有素数来查找 n 的素因数。 ，因为足以测试2..k哪里k*k <= n 。这也确保我们只使用已经计算出的质数部分。

一开始，primes看起来像这样:

2 : filter ((==1) . length . primeFactors) [3,5..]

如果我们要求 2 之后的下一个元素，我们会强制评估冒号右侧的表达式。这反过来又导致过滤器评估 3 的谓词。然后是:

primeFactors 3
  factor 3 (2 : ...)
    2*2 > 3
  [3]
[3]

因此，primeFactors 3是 [3]我们不需要考虑超过 2 的素数。 (这就是它起作用的关键点!)显然，[3]的长度是 1 并且

2 : filter ((==1) . length . primeFactors) [3,5..]

评估为

2 : 3 : filter ((==1) . length . primeFactors) [5, 7..]

您现在可能想要减少primeFactors 5为你自己。