haskell - Haskell 中的素数

Question

我正在学习 Haskell，我试图生成一个无限的素数列表，但我不明白我的函数做错了什么。

功能:

prime = 2:3:filter (\x -> all (\y -> (mod x y) > 0) (init prime)) [5..]

我认为是 init prime ，但奇怪的是，即使我为范围设置了上限(例如 5..10)，该函数也会永远循环并且永远不会得到 prime !! 2 的任何结果。

你能告诉我我做错了什么吗？

Answer 1

好吧，让我们看看什么是init为有限列表做:

init [1] == []
init [1,2] == [1]
init [1,2,3] == [1,2]

好的，所以它给了我们除了列表的最后一个元素之外的所有元素。

那是什么 init primes ?那么， prime没有最后一个元素。希望如果我们实现 prime正确它不应该有最后一个元素(因为有无限多个素数!)，但更重要的是我们还不需要关心，因为我们现在还没有完整的列表——我们只关心第一个毕竟是几个元素，所以对我们来说，它与 prime 几乎相同本身。

现在，看着 all : 这有什么作用？好吧，它接受一个列表和一个谓词，并告诉我们列表中的所有元素是否都满足谓词:

all (<5) [1..4] == True
all even [1..4] == False

它甚至适用于无限列表!

all (<5) [1..] == False

那么这里发生了什么？嗯，事情是这样的:它确实适用于无限列表……但前提是我们可以实际评估列表直到列表中第一个违反谓词的元素!让我们看看这里是否适用:

all (\y -> (mod 5 y) > 0) (init prime)

以便了解是否 5是素数，我们必须检查素数中是否有一个数减去将它相除的素数的最后一个元素。让我们看看我们是否可以做到这一点。

现在让我们看看素数的定义，我们得到

all (\y -> (mod 5 y) > 0) (2:3:filter (\x -> all (\y -> (mod x y) > 0) (init prime)) [5..])

所以要确定 5 是否是素数，我们只需要检查它是否是:

可被 2 整除 - 不是，让我们继续

可以被 3 整除 - 仍然没有

可以被……整除？好吧，我们正在检查第三个素数是什么，所以我们还不知道...

这就是问题的关键。按照这个逻辑，要确定第三个质数，您需要知道第三个质数!当然，从逻辑上讲，我们实际上根本不想检查这个，而只需要检查是否有任何较小的素数是当前候选者的除数。

那么我们该怎么做呢？好吧，不幸的是，我们将不得不改变我们的逻辑。我们可以做的一件事是尝试记住我们已经有多少素数，并且只取我们需要的数量来进行比较:

prime = 2 : 3 : morePrimes 2 [5..]
  morePrimes n (x:xs)
    | all (\y -> mod x y > 0) (take n prime) = x : morePrimes (n+1) xs
    | otherwise                              = morePrimes n xs

那么这是如何工作的呢？嗯，它基本上做了我们刚才所说的:我们记得我们已经有多少个素数(从 2 开始，因为我们知道我们至少有 [2,3] in n。然后我们检查我们的下一个素数是否可整除通过使用 n 我们已经知道的 take n 素数中的任何一个，如果是，我们知道它是我们的下一个素数，我们需要增加 n - 否则我们就继续。

还有一种更广为人知的形式，其灵感来自(虽然不完全相同)埃拉托色尼筛法:

prime = sieve [2..] where
  sieve (p:xs) = p : sieve (filter (\x -> mod x p > 0) xs)

那么这是如何工作的呢？好吧，又是一个类似的想法:我们知道下一个质数必须不能被任何先前的质数整除。那么我们该怎么办？嗯，从 2 开始我们知道列表中的第一个元素是素数。然后我们使用 filter 丢弃所有可以被该质数整除的数。 .之后，列表中的下一项将再次成为质数(因为我们没有扔掉它)，所以我们可以重复这个过程。

这些都不是您希望的那种衬垫。