时间戳

首页 > 解决方案 > 在使用 Haskell 实现 Eratosthenes 筛法中，为什么 3,5,7.. 的倍数没有从列表中删除？

haskell - 在使用 Haskell 实现 Eratosthenes 筛法中，为什么 3,5,7.. 的倍数没有从列表中删除？

问题描述

我目前正在自学 Doets 和 Eijck 的《The Haskell Road to Logic, Maths and Programming 》一书，我在第 3 章。

在本章中，作者提供了一个 Haskell 代码来实现Sieve of Eratosthenes算法，我不喜欢他们的实现，所以我尝试给出自己的实现；但是，我的代码版本确实只删除了 2 的倍数，我无法弄清楚原因。这是代码：

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..）的倍数执行相同的删除操作？

标签： haskellprimessieve-of-eratosthenes

解决方案

k简短的回答：计数器mark不会增加n> 2。

mark x 2 [2..]正确地从列表中删除偶数，因此下一步是调用sieve [3,5..]，相当于3:sieve (mark 3 2 [5,7..])，所以让我们看看这里发生了什么。

mark 3 2 [5,7..]（大概）尝试3从列表中删除所有倍数，但它会一步一步地执行此操作，首先尝试从列表中删除 6。但是，由于列表仅包含奇数，因此永远不会从列表中删除 6，并且第一种情况总是失败。代码继续检查 6，从不向上移动以删除 9。

同样，25 永远不会被删除，因为代码只会尝试2*5从列表中删除。

推荐阅读