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

Question

我最近开始学习一个haskell并且度过了非常愉快的时光.我一直在解决一些项目Euler问题,以掌握语法,并一直在审查http://www.haskell.org/haskellwiki/Euler_problems/1_to_10作为学习工具发布的解决方案.虽然我发现自己无法绕过针对问题#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 自己减少.

Answer 2

这是懒惰的行动:)素数列表开始非空,

primes = 2 : don't_know_yet_let's_see

并primeFactors使用素数列表计算数字的素因子.但是要找到任何数字'n'的素数因子,我们只需要知道素数sqrt(n).所以尾巴primes,

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

可以使用已知的东西primes.为了检查3,我们

factor 3 (2:don't_kow_yet_let's_see)
    | 2*2 > 3 = [3]
    | don't_care_above_was_true

如果我们从任何开始n,比如n = 35保持简短,

factor 35 (2:??)
    | 2*2 > 35  -- False, next clause
    | 35 `mod` 2 == 0 -- False, next clause
    | otherwise = factor 35 ??

现在我们需要找出它是什么??.上面我们看到的是,filterING让3遍,所以它的3:???,因此

factor 35 (3:???)
    | -- first two guards are False
    | otherwise = factor 35 ???

现在是什么???？那么,filter ((== 1) . length . primeFactors) [5, 7 .. ]让我们看看是否5通过过滤器

factor 5 (2:3:???)  -- note, we already know the first two elements of primes
    | 2*2 > 5 -- False
    | 5 `mod` 2 == 0 -- False
    | otherwise = factor 5 (3:???)
                     | 3*3 > 5 = [5]

因此,5通过和我们所知道的前三个元素primes.在35的因子分解中,我们继续

factor 35 (5:????)
    | 5*5 > 35 -- False
    | 35 `mod` 5 == 0 = 5 : factor (35 `div` 5) (5:????)
                            factor 7 (5:????)
                               | 5*5 > 7 = [7]

因此,在对数字进行分解时,根据需要建立素数列表,每个新素数将在需要时确定,并且在那时,已经找到了确定下一个素数所需的所有素数.