scala - 在Scala中计算素数: how does this code work?

Question

所以我花了几个小时试图弄清楚这段代码是如何产生素数的。

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i =>
   ps.takeWhile{j => j * j <= i}.forall{ k => i % k > 0});

我使用了许多 println 等，但没有什么能让它更清楚。

这就是我认为代码的作用:

/**
 * [2,3] 
 * 
 * takeWhile 2*2 <= 3 
 * takeWhile 2*2 <= 4 found match
 *      (4 % [2,3] > 1) return false.
 * takeWhile 2*2 <= 5 found match
 *      (5 % [2,3] > 1) return true 
 *          Add 5 to the list
 * takeWhile 2*2 <= 6 found match
 *      (6 % [2,3,5] > 1) return false
 * takeWhile 2*2 <= 7
 *      (7 % [2,3,5] > 1) return true
 *          Add 7 to the list
 */

但是，如果我将列表中的 j*j 更改为 2*2(我假设会完全一样地工作)，则会导致 stackoverflow 错误。

我显然在这里遗漏了一些基本的东西，并且真的需要有人向我解释这一点，就像我是一个五岁的 child 一样。

任何帮助将不胜感激。

Answer 1

我不确定寻求程序/命令性解释是获得理解的最佳方式。流来自函数式编程，从这个角度可以最好地理解它们。您给出的定义的关键方面是:

1. 这是懒。除了流中的第一个元素之外，在您请求之前不会计算任何内容。如果您从不要求第 5 个素数，则永远不会计算它。

2. 它是递归的。素数列表是根据其自身定义的。

3. 无限。流具有有趣的属性(因为它们是惰性的)，它们可以表示具有无限数量元素的序列。 Stream.from(3)就是一个例子:它表示列表 [3, 4, 5, ...]。

让我们看看是否可以理解为什么您的定义要计算素数序列。

定义以 2 #:: ... 开头。这只是说明序列中的第一个数字是 2 - 到目前为止足够简单。

下一部分定义其余的素数。我们可以从从 3 开始的所有计数( Stream.from(3) )开始，但我们显然需要过滤掉一堆这些数字(即所有组合)。因此，让我们考虑每个数字 i 。如果i不是较小质数的倍数，则 i是素数。即i是素数，如果对于所有素数 k小于i , i % k > 0 。在 Scala 中，我们可以将其表示为

nums.filter(i => ps.takeWhile(k => k < i).forall(k => i % k > 0))

然而，实际上并不需要检查所有较小的素数——我们实际上只需要检查平方小于或等于 i 的素数。 (这是数论的事实*)。所以我们可以这样写

nums.filter(i => ps.takeWhile(k => k * k <= i).forall(k => i % k > 0))

所以我们已经得出了您的定义。

现在，如果您碰巧尝试第一个定义(使用 k < i )，您会发现它不起作用。为什么不？这与这是一个递归定义这一事实有关。

假设我们试图确定序列中 2 之后的内容。定义告诉我们首先判断3是否属于。为此，我们考虑素数列表，直到第一个大于或等于 3 ( takeWhile(k => k < i) ) 的素数。第一个素数是 2，小于 3——到目前为止还不错。但我们还不知道第二个素数，所以我们需要计算它。好吧，所以我们首先需要看看 3 是否属于... BOOM!

* 很容易看出，如果一个数字 n是合数，那么它的一个因子的平方必须小于或等于 n 。如果n是复合的，那么根据定义 n == a * b ，其中1 < a <= b < n (我们可以通过适本地标记这两个因素来保证a <= b)。来自 a <= b由此可见a^2 <= a * b ，因此 a^2 <= n .