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

Question

我最近学习了一个haskell，并且一直有相当不错的时间。我一直在通过一些Project Euler问题来掌握语法，并一直在回顾这里发布的解决方案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自己。

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

现在我们需要找出??是。我们看到上面说的filter ING让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] 

所以，因子分解数字时，素数的名单需要尽可能，每个新总理将在它的要求来决定建立起来的，在那个时候，所有的已经找到确定下一个素数所需的素数。