这个素数函数实际上是如何工作的？

Question

这个素数函数实际上是如何工作的？

5

以下内容摘自Haskell的主页https://www.haskell.org/

primes = filterPrime [2..] 
  where filterPrime (p:xs) = 
          p : filterPrime [x | x <- xs, x `mod` p /= 0]

在看了这个函数几分钟后，我意识到我并不真正理解这个函数实际上是在做什么，我想知道正在发生什么。

但首先，这是我认为正在发生的事情：

由于惰性求值，每次迭代只会取列表推导中的一个成员...就像这样：

第一次迭代

2 : filterPrime [x | x <- [3..], x `mod` p /= 0]

第二次迭代

2 : 3 : filterPrime [x | x <- [4..], x `mod` p /= 0]

第三次迭代

。

??? :(

- yeyo

我认为它是通过检查列表推导中的数字是否可被当前找到的质数整除来生成质数列表。 - m0meni

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Random Dev · Accepted Answer

第一个直接从模式匹配p：xs中的[2..]中获取-所以p = 2，而xs是一些阻塞操作。

下一个需要评估xs，因此需要评估。

[ x | x <- [3..], x `mod` 2 /= 0 ]

这将以x = 3开始（这符合筛选条件）- 所以现在你有了p:xs（请记住使用filterPrime的递归定义），其中p=3，但是这一次xs已经被过滤为`mod` 2 /= 0，现在还将被过滤为3 - 对于每个找到的质数都会进行这样的操作 - 每次只查看不是所有找到的质数的倍数的剩余数字。

你可以看到它有点像埃拉托斯特尼筛法，我想它也叫这个名字（但有一些反对意见）。