在用Haskell实现Eratosthenes的筛子中，为什么3，5，7的倍数是？没有从列表中删除？
在用Haskell实现Eratosthenes的筛子中，为什么3，5，7的倍数是？没有从列表中删除？
提问于 2018-07-30 02:48:04
我目前正在自学Doets和Eijck的书the Haskell Road to Logic，Math and Programming，我在第三章。
在本章中，作者为Eratosthenes算法的Sieve的实现提供了一个Haskell代码，我不喜欢他们的实现，所以我尝试给出我自己的实现；然而，我的版本的代码只删除了2的倍数，并且我找不出.Here是代码的原因：
sieve :: [Int] -> [Int]
sieve (0:xs) = sieve xs
sieve (x:xs) = x : sieve (mark x 2 xs)
where
mark :: Int -> Int -> [Int] -> [Int]
mark n k (y:ys)
| y == n*k = 0 : (mark n (k+1) ys)
| otherwise = y : (mark n (k) ys) 输出结果是
*Ch3> sieve [2..]
[2,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,...那么，为什么代码不对其他数字的倍数做相同的去掉操作，比如3,5,7.?
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-07-30 02:58:53
简短回答：
mark中的计数器k对于n> 2不会递增。
mark x 2 [2..]正确地从列表中剥离了evens，因此下一步是调用sieve [3,5..]，这相当于3:sieve (mark 3 2 [5,7..])，所以让我们看看这里发生了什么。
mark 3 2 [5,7..] (可能)尝试从列表中删除3的所有倍数，但它是循序渐进的，首先尝试从列表中删除6。但是，由于列表中只包含奇数，6永远不会从列表中删除，并且第一种情况总是失败。代码继续检查6，从不向上移动到删除9。
类似地，25永远不会被删除，因为代码只尝试从列表中删除2*5。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51583473
复制相关文章
相似问题