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 整除 - 还是不能
能被...整除？好吧，我们正在检查第三个素数是多少，所以我们还不知道...

这就是问题的症结所在。按照这个逻辑，要确定第三个素数就需要知道第三个素数！当然从逻辑上讲，我们实际上根本不想检查这个，而我们只需要检查smaller素数中的任何一个是否是当前候选人的除数。

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

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 开始，因为我们知道我们在 n 中至少有 [2,3] 个。然后我们检查如果我们的下一个素数可以被我们已经知道的 n 个素数中的任何一个整除，如果是，我们知道它是我们的下一个素数，我们需要递增 n - 否则我们继续。

还有一种更广为人知的形式，其灵感来自（尽管不完全相同）埃拉托色尼筛法：

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

那么这是如何工作的呢？好吧，再次提出类似的想法：我们知道下一个素数需要 non-divisible 乘以任何先前的素数。那么我们该怎么办？好吧，从 2 开始，我们知道列表中的第一个元素是素数。然后，我们使用 filter 丢弃所有可被该素数整除的数字。之后，列表中的下一项将再次成为素数（因为我们没有丢弃它），所以我们可以重复这个过程。

这些都不是您所希望的那样。

Answer 2

如果中的代码在identity

下重构

[take n primes | n <- [0..]]  ==  inits primes

最终我们得到

import Data.List
              -- [ ([], 2), ([2], 3), ([2,3], 5), ... ]
primes = 2 : [ c | (ps, p) <- zip (inits primes) primes,  
                   c <- take 1 [c | c <- [p+1..], 
                                    and [mod c p > 0 | p <- ps]]]

在算法上进一步改进，就变成了

primes = 2 : [ c | (ps, r:q:_) <- zip (inits primes)                  -- [] [3,4,...]
                                      (tails $ 3 : map (^2) primes),  -- [2] [4,9,...]
                   c <- [r..q-1], and [mod c p > 0 | p <- ps]]        -- [2,3] [9,25,...]

Haskell 中的质数

Primes in Haskell

primes

haskell

lazy-evaluation