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] 

所以，因子分解數字時，素數的名單需要儘可能，每個新總理將在它的要求來決定建立起來的，在那個時候，所有的已經找到確定下一個素數所需的素數。