问题标签 [sieve-of-atkin]

我目前正在做一个项目，我需要一种有效的方法来计算素数。我使用过Eratosthenes 的筛子，但我一直在四处寻找，发现Atkin 的筛子是一种更有效的方法。我发现很难找到这种方法的解释（我已经能够理解！）。它是如何工作的？示例代码（最好是 C 或 python）会很棒。

编辑：感谢您的帮助，我唯一仍然不明白的是伪代码中 x 和 y 变量所指的内容。有人可以为我解释一下吗？

我想知道这里是否有人有他们想要分享的阿特金筛子的良好实现。

我正在尝试实现它，但无法完全理解它。这是我到目前为止所拥有的。

我几乎只是试图“翻译” Wikipedia中列出的伪代码，但它无法正常工作。所以要么我误解了什么，要么只是做错了什么。或者很可能两者都...

有一个我用作测试的前 500 个素数的列表，我的实现在第 40 号（或 41？）处失败。

索引 [40] 处的值不同
预期：179
但原为：175

您是否能够找到我的错误，您是否有可以共享的实现，或两者兼而有之？

我正在使用的确切测试如下所示：

我不知道这是否可能，但我只是想问一下。我的数学和算法技能在这里有点让我失望：P

问题是我现在有这个类可以生成达到一定限制的素数：

现在，我想要摆脱限制，以便序列永远不会停止（理论上）。

我想它可能会是这样的：

1. 从一些微不足道的限制开始
   • 找到所有质数到极限
   • 产生所有新发现的素数
   • 增加限制（通过将旧限制加倍或平方或类似的方法）
   • 转到第 2 步

最佳情况下，第二步只需要在旧限制和新限制之间工作。换句话说，它不应该一次又一次地找到最低的素数。

有没有办法做到这一点？我的主要问题是我不太了解该算法中的内容x，y例如。就像，我可以只使用相同的算法类型，但设置x为（最初y为oldLimit1）并将其运行到newLimit？或者那将如何工作？有什么聪明的头脑可以阐明这一点吗？

这样做的目的是让我不必设置这个限制。这样我就可以使用 Linq 以及Take()我需要的任意数量的素数，而不用担心限制是否足够高等等。

最近我一直在研究一个 C++ 素数生成器，它使用阿特金筛 ( http://en.wikipedia.org/wiki/Sieve_of_atkin ) 来生成它的素数。我的目标是能够生成任何 32 位数字。我将主要用于项目欧拉问题。大多数情况下，这只是一个夏季项目。

该程序使用位板来存储素数：即一系列 1 和 0，例如，第 11 位为 1，第 12 位为 0，第 13 位为 1，等等。为了有效地使用内存，这实际上是和字符数组，每个字符包含 8 位。我使用标志和按位运算符来设置和检索位。该算法的 gyst 很简单：使用一些我不假装理解的方程来定义一个数字是否被认为是“素数”。这将在很大程度上得到正确的答案，但几个非素数将被标记为素数。因此，在遍历列表时，您将刚刚找到的素数的所有倍数设置为“非素数”。这具有方便的优势，即所需的处理器时间越少，素数越大。

我已经完成了 90%，但有一个问题：缺少一些素数。

通过检查位板，我确定在第一遍过程中省略了这些素数，这基本上会为许多方程的每个解切换一个数字（参见维基百科条目）。我一次又一次地检查了这段代码。我什至尝试增加维基百科文章中显示的范围，这效率较低，但我认为可能会遇到一些我以某种方式省略的数字。没有任何效果。这些数字只是评估为非质数。我的大部分测试都针对 128 以下的所有素数。在这个范围内，这些是被省略的素数：

23 和 59。

我毫不怀疑，在更高的范围内，会丢失更多（只是不想计算所有这些）。我不知道为什么这些都不见了，但确实如此。这两个素数有什么特别之处吗？我已经进行了两次和三次检查，发现并修复了错误，但我仍然可能缺少一些愚蠢的东西。

无论如何，这是我的代码：

我尽力清理它并使其可读。我不是专业的程序员，所以请见谅。

这是我得到的输出，当我初始化一个名为 pgen 的 PrimeGen 对象时，使用 pgen.printBoard() 打印其初始位板（请注意，在 next() 迭代之前缺少 23 和 59），然后遍历 next() 和打印所有返回的素数：

我对阿特金筛法的实现要么忽略了接近极限的素数，要么忽略了接近极限的复合物。有些限制有效，有些则无效。我对出了什么问题感到完全困惑。

例如，当我生成一个限制为 1000 的素数时，阿特金筛漏掉了素数 997，但包括了复合 965。但是如果我生成了 5000 的限制，它返回的列表是完全正确的。

我知道可以实施 Eratosthenes 筛，以便它在没有上限的情况下连续找到素数（分段筛）。

我的问题是，阿特金/伯恩斯坦的筛子能否以同样的方式实施？

相关问题：C#：如何使阿特金筛子增量

然而，相关问题只有 1 个答案，上面写着“所有筛子都不可能”，这显然是不正确的。

我在 Wikipedia 上阅读了有关 Atkin 筛子的信息，但目前该 wiki 是有限的。我一直在寻找对阿特金筛子的高级解释和 Java 中的示例。

谢谢。

我正在尝试解决Project Euler 问题 10，其中要求用户计算小于 200 万的所有素数的总和。我通过研究Wikipedia 上的伪代码编写了以下内容，但它生成的答案似乎不正确，至少根据该网站，每当我尝试输入它时：

生成以下输出：

我已经用较小的限制对其进行了测试，我可以手动验证，并且代码对于这些数字确实可以正常运行。我发现其他人的实现表明答案应该是142913828922，但我无法弄清楚他们的代码与我的不同之处。

谁能看到我在这里做错了什么？

我尝试了 Eratosthenes 的筛子：以下是我的代码：

这需要时间：我的系统中真正的 7.340 秒。

我还尝试了阿特金斯筛（比埃拉托色尼筛更快地研究的地方）。

但就我而言，这需要时间：真正的 10.433 秒。

这是代码：

现在，我想知道，没有人能够在 1 秒内输出 100 万个素数。

一种方法可能是：

有人可以建议我用更少的时间获得前 100 万个素数吗

比满足约束的一秒（上面讨论过）？

谢谢！！

所以我做了一个阿特金算法的筛子来生成素数（针对欧拉计划问题）。它返回一个名为 的素数 (int[]) 数组primes。问题是，每当我尝试从某个索引访问该数组时（我在我的main方法中这样做），它都会抛出一个java.lang.ArrayIndexOutOfBounds异常。请帮忙（如果您认为我的逻辑与仙女不符，并且有更简单的方法可以做到这一点，请告诉我）！