Haskell代碼排除號碼埃拉托色尼的篩預期

我用下面的Sieve of Eratosthenes實施來到不工作：Haskell代碼排除號碼埃拉托色尼的篩預期

sieve :: (Integral a) => [a] -> [a] 
sieve [] = [] 
sieve (p:ps) = p:[x | x <- sieve ps, (rem x p) /= 0] 

primes :: (Integral a) => [a] 
primes = sieve [2..100]

調用primes從gchi打印：

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

添加出發的optimization step標記號碼p，我結束了以下代碼：

sieve :: (Integral a) => [a] -> [a] 
sieve [] = [] 
sieve (p:ps) = p:[x | x <- sieve ps, x > p^2, (rem x p) /= 0] 

primes :: (Integral a) => [a] 
primes = sieve [2..100]

但它產生以下輸出：

[2]

我是新來的Haskell所以我有問題要理解爲什麼加入x > p^2正在產生這樣的結果。

您可以通過解釋Haskell如何評估表達式來發現我的錯誤嗎？

來源

2015-04-22 higuaro

這不是Eratosthenes的篩子。這是一種[試驗分區]形式（http://en.wikipedia.org/wiki/Trial_division），速度很慢。要獲得更好的功能篩網，請參閱緊密基於Eratosthenes的[O'Neill篩網]（https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf）。 – dfeuer

我很擔心這種實現的緩慢，這就是爲什麼我要跳過第一個「p^2」數字，但是當我通過答案學習時，它並不是那種方式。感謝您的論文鏈接。 – higuaro

奧尼爾的實際實施比文中的實施要複雜一點（也好多了）。它在'NumberSieves'包中的[Math.Sieve.ONeill]（https://hackage.haskell.org/package/NumberSieves-0.1.1/docs/Math-Sieve-ONeill.html）中。 – dfeuer

你有

sieve [2..10]

它擴展到

2 : [x1 | x1 <- sieve [3..10], x1 > 4, rem x1 2 /= 0] 
    = 2 : [x1 | x1 <- 3 : [x2 | x2 <- sieve [4..10], 
           x2 > 9, 
           x2 `rem` 3 /= 0], 
       x1 > 4, 
       x1 `rem` 2 /= 0]

所以第一x1是3，但3 > 4是False，所以我們移動到下一個：

= 2 : [x1 | x1 <- [x2 | x2 <- sieve [4..10], 
          x2 > 9, 
          x2 `rem` 3 /= 0], 
       x1 > 4, 
       x1 `rem` 2 /= 0] 

    = 2 : [x1 | x1 <- [x2 | x2 <- 4 : [x3 | x3 <- sieve [5..10], 
              x3 > 16, 
              x3 `rem` 4 /= 0], 
          x2 > 9, 
          x2 `rem` 3 /= 0], 
       x1 > 4, 
       x1 `rem` 2 /= 0]

所以，如果x2是4，x2 > 9是假的，所以我們移動到下一個元素：

= 2 : [x1 | x1 <- [x2 | x2 <- [x3 | x3 <- sieve [5..10], 
             x3 > 16, 
             x3 `rem` 4 /= 0], 
          x2 > 9, 
          x2 `rem` 3 /= 0], 
       x1 > 4, 
       x1 `rem` 2 /= 0]

所以我們已經可以看到，我們所知道的唯一的實際值被返回是2，3被跳過，因爲3 > 4是False。 4被跳過，但出於錯誤的原因，並且5將被跳過，因爲5 > 16是False，依此類推。這裏的問題是你的條件x > p^2過濾整個列表，但你真的想在列表中跳躍前進。這意味着您實際感興趣的值將從輸出中過濾出來。

來源

2015-04-22 20:22:07 bheklilr

謝謝，真的很好的答案！有沒有辦法使用這種方法在列表中向前跳躍，還是應該以其他方式來做這件事？ – higuaro

@higuaro在上面dfeuer的評論中提到，你實際上並沒有用這種風格實現eratosthenes的篩選，最好嘗試一種不同的途徑來尋找素數。列表理解不允許你跳到前面，它們按順序處理每個項目。 – bheklilr

@higuaro，就我所知，唯一的（相當簡單的）向前跳的方法是使用[輪]（http://en.wikipedia.org/wiki/Wheel_factorization），這是奧尼爾解釋得很多的一種技巧在她的論文中更好。輪子問題似乎是，他們很快就會變大。其他方法的重點是儘可能快地咀嚼複合材料。 – dfeuer

這行代碼：

p:[x | x <- sieve ps, x > p^2, (rem x p) /= 0]

說：「採取一切從x sieve ps這樣x > p^2和x是不是p整除」。這意味着所有小於或等於p^2的數字都將被丟棄。這顯然是不正確的（最小的計數器例子：[2..3]）。

來源

2015-04-22 20:21:55 kraskevich

Haskell代碼排除號碼埃拉托色尼的篩預期

回答

相關問題