计算Scala中的素数:此代码如何工作？

Question

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

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

我已经使用了许多打印笔等,但没有让它更清晰.

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

/**
 * [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(我假设它将完全相同),则会导致堆栈溢出错误.

我显然在这里缺少一些基本的东西,并且真的可以使用某人向我解释这个,就像我五岁.

任何帮助将不胜感激.

Answer 1

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

1. 这很懒惰.除了流中的第一个元素之外,在您要求之前不会计算任何内容.如果你从不要求第五个素数,它将永远无法计算.

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

3. 这是无限的.Streams具有有趣的属性(因为它们很懒惰),它们可以表示具有无限数量元素的序列.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))

所以我们推导出你的定义.

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

假设我们正在尝试决定序列中2之后的内容.该定义告诉我们首先确定3是否属于.为此,我们认为第一个素数列表大于或等于3(takeWhile(k => k < i)).第一个素数是2,小于3 - 到目前为止一直很好.但是我们还不知道第二个素数,所以我们需要计算它.很好,所以我们首先要看看3是否属于......砰!

* 很容易看出,如果一个数n是复合的,那么其中一个因子的平方必须小于或等于n.如果n是复合的,那么按照定义n == a * b,在哪里1 < a <= b < n(我们可以a <= b通过恰当地标记这两个因素来保证).从那以后a <= b,接下来就是a^2 <= a * b如此a^2 <= n.