我知道可以实施 Eratosthenes 筛，以便它在没有上限的情况下连续找到素数（分段筛）。
我的问题是，阿特金/伯恩斯坦的筛子能否以同样的方式实施？
相关问题：C#：如何使阿特金筛子增量
然而，相关问题只有 1 个答案，上面写着“所有筛子都不可能”，这显然是不正确的。
问问题
1060 次
2 回答
4
Atkin/Bernstein 在其原始论文的第 5 节中给出了分段版本。据推测，伯恩斯坦的素数程序使用了这种方法。
于 2012-05-03T22:30:33.550 回答
2
事实上，可以像我在 F#中所做的那样，完全不使用分段来实现无界的 Atkin 筛选 (SoA) 。请注意，这是一个纯函数版本，它甚至不使用数组来组合二次方程和无平方滤波器的解，因此比更命令式的方法要慢得多。
Berstein 使用查找表对最佳 32 位范围进行优化会使代码极其复杂，不适合在这里展示，但调整我的 F# 代码会很容易，以便序列从设定的下限开始并且仅使用在一个范围内以实现分段版本，和/或将相同的技术应用于使用数组的更重要的方法。
请注意，即使按照Kim Walisch 的素数筛，即使 Berstein 的 SoA 实现并不比 Eratosthenes 的筛子更快，但仅比根据他的选定数字范围的等效优化的 Eratosthenes 筛子快执行。
EDIT_ADD： 对于那些不想涉足 Berstein 的伪代码和 C 代码的人，我在这个答案中添加了一个伪代码方法，以在从 LOW 到 HIGH 的范围内使用 SoA，其中从 LOW 到 HIGH 的增量+ 1 可能会被限制为偶数模 60，以便使用模数（以及仅对 2、3、5 轮上的条目的潜在位打包）优化。
这是基于使用 (4*x^2 + y^)、(3*x^2 + y^2) 和 (3*x^2 -y^2) 的 SoA 二次方的可能实现作为数字序列，每个序列的 x 值固定为 1 和 SQRT((HIGH - 1) / 4)、SQRT((HIGH - 1) / 3) 之间的值，并求解 2*x^2 + 的二次方2*x - HIGH - 1 = 0 for x = (SQRT(1 + 2 * (HIGH + 1)) - 1) / 2，分别在我的 F# 代码中按照顶部链接表示的序列。对那里的序列进行优化时，仅在筛选奇数组合时，对于“4x”序列，y 值只需为奇数，“3x”序列仅在 x 为偶数时使用 y 的奇数值，反之亦然。
我也不包括众所周知的优化，这些优化可以应用于主要的“无正方形”剔除以使用轮分解和起始段地址的计算，就像我在分段 SoE 的实现中使用的那样。
因此，为了计算“4x”、“3x+”和“3x-”（或像我在 F# 代码中那样将“3x+”和“3x-”组合在一起）的序列起始段地址，并计算了根据上述每个x的范围，伪代码如下：
计算范围 LOW - FIRST_ELEMENT，其中 FIRST_ELEMENT 是每个给定 x 值的 y 的最低适用值，或者对于“3x-”序列的情况，y = x - 1。
对于计算该范围内有多少元素的工作，这归结为以下问题： (y1)^2 + (y2)^2 + (y3)^2... 每个 y 数在哪里由两个分隔，根据需要产生偶数或奇数 'y'。与平方序列分析中的往常一样，我们观察到平方之间的差异具有恒定增加的增量，因为增量（9 - 1）为 8，增量（25 - 9）为 16，增量为 8，增量（49 - 25）为24 进一步增加 8 等等。因此对于本例，对于 n 个元素，最后一个增量是 8 * n。用这个来表达元素的序列，我们得到它是一个（或任何一个选择作为第一个元素）加上八倍的序列（1 + 2 + 3 + ...+ n）。现在，线性序列的标准缩减适用于该总和为 (n + 1) * n / 2 或 n^2/2 + n/2 的情况。
现在，如果 FIRST_ELEMENT + 4 * (n + 1) * n 不等于 LOW 作为起始地址，则将 n 加 1 并使用 FIRST_ELEMENT + 4 * (n + 2) * (n + 1) 作为起始地址。如果使用进一步的优化来将轮因式分解剔除应用于序列模式，则可以使用查找表数组来查找满足条件的已使用 n 的最接近值。
起始元素的模数 12 或 60 可以直接计算，或者可以通过使用基于模数序列的重复性质的查找表来产生。
然后使用每个序列将复合状态切换到上限。如果将附加逻辑添加到序列以仅在每个序列的适用元素之间跳转值，则无需进一步使用模条件。
以上是针对每个“4x”序列后跟“3x+”和“3x-”序列（或将“3x+”和“3x-”组合成一组“3x”序列）直到计算得到的x限制更早或按循环测试。
你有它：给定一种将筛子范围划分为段的适当方法，最好将其用作与 CPU 缓存大小相关的固定大小，以获得最佳内存访问效率，一种分割 SoA 的方法，就像 Bernstein 使用的那样但正如它所提到的，表达方式有点简单，但没有结合模运算和位打包。
于 2013-08-02T15:43:31.000 回答