埃拉托斯特尼筛法非最优实现内部原理及IntPredicate机制问询

整体工作原理 #

这段代码用Java流API结合动态更新的断言逻辑，模拟了筛法“排除已找到质数的倍数”的核心思路，但实现方式比较朴素：

1. 初始状态：定义了一个初始断言p = x -> true，意味着一开始所有整数都被判定为符合条件。
2. 生成整数流：通过IntStream.iterate(2, i -> i + 1)生成从2开始的无限递增整数流。
3. 筛选符合条件的数：filter(x -> p.test(x))用当前的断言p检查每个数，只有通过检查的数才能进入后续流程。
4. 动态收紧筛选规则：peek(i -> p = p.and(k -> k % i != 0))是核心操作——每找到一个通过筛选的数（也就是质数），就把“不能被这个质数整除”的条件追加到断言p中，让后续的筛选规则更严格。
5. 返回前n个质数：limit(n)限制只取前n个通过筛选的数，最后toArray()将结果转为数组返回。

举个实际流程例子（假设n=3）：

• 第一个数是2：p.test(2)返回true，通过筛选；随后p被更新为true && k%2 !=0（即“不能被2整除”）；2被加入结果数组。
• 第二个数是3：当前p检查3，3%2≠0，通过筛选；p更新为(k%2≠0) && (k%3≠0)；3被加入结果数组。
• 第三个数是4：p检查4，4%2=0，不通过，被过滤。
• 第四个数是5：p检查5，5%2≠0且5%3≠0，通过筛选；p更新为包含“不能被5整除”的条件；5被加入结果数组，此时已取够3个质数，流终止，返回[2,3,5]。

IntPredicate的内部运行机制 #

IntPredicate是Java的函数式接口，仅定义了一个test(int value)方法，用于判断整数是否符合指定条件。这里重点用到了它的默认方法and(IntPredicate other)：

• and方法会返回一个新的复合IntPredicate，逻辑上是“短路与”：先执行当前断言的test方法，如果返回true，再执行传入的other断言的test方法；如果当前断言返回false，直接返回false，避免不必要的计算。
• 每次执行p = p.and(k -> k % i != 0)时，都是把原有断言p和新的“不能被当前质数i整除”的断言组合，生成更严格的新断言并覆盖原p变量。后续所有filter操作，都会用这个不断叠加的复合断言来检查每个数。

比如经过两次更新后，p的test逻辑变为：先判断数是否不能被2整除，若满足，再判断是否不能被3整除，只有两个条件都满足才返回true。

为什么这是非最优实现？ #

标准埃拉托斯特尼筛法通过直接标记质数的倍数来高效排除非质数，而这个实现存在明显效率问题：

• 每个数都要依次经过所有已找到质数的取模判断，随着质数数量增加，单个数值的判断成本会越来越高。
• 流是逐个遍历整数，即使是已被排除的数（比如4、6），也要走到filter步骤才会被过滤，没有提前标记跳过这些数的机制，效率远低于标准筛法。

内容的提问来源于stack exchange，提问作者Brando Jeanpier