问题标签 [sieve-of-eratosthenes]

我正在学习Erlang。作为练习，我学习了生成素数的埃拉托色尼筛法。这是我的代码：

这段代码实际上有效:)。问题是我觉得这不是最好的实现。

我的问题是实施“埃拉托色尼筛”的“erlangish”方式是什么

编辑：好的，安德烈亚斯解决方案非常好，但速度很慢。有什么想法可以改善吗？

我不想从网上刮掉这个算法的 Ruby 版本，而是想根据这里的描述创建自己的。但是我无法弄清楚两件事

1. 为什么它不迭代到数组的末尾？
2. 根据上面链接中的描述，当数组中最后一个元素的平方根大于当前素数时，循环应该被打破——我之前做过这个。

我相当确定它与修改数组长度的删除操作有关。例如，当我输入 n=10 时，我的函数当前会产生 2,3,5,7,9,10，这显然是不正确的。关于如何改变它以使其按预期工作的任何建议？

注意：下面的版本 2 使用 Eratosthenes 筛。有几个答案对我最初提出的问题有所帮助。我选择了埃拉托色尼筛法，实施了它，并适当地改变了问题的标题和标签。感谢所有帮助过的人！

介绍

我写了这个花哨的小方法，它生成一个包含小于指定上限的素数的 int 数组。它工作得很好，但我有一个担心。

方法

我的顾虑

我担心的是我创建的数组对于该方法将返回的最终元素数量来说太大了。问题是我不知道正确猜测小于指定数字的素数数量的好方法。

重点

这就是程序使用数组的方式。这是我想要改进的地方。

1. 我创建了一个足够大的临时数组，可以容纳每个小于限制的数字。
2. 我生成质数，同时计算我生成了多少。
3. 我制作了一个新的数组，它的维数正确，可以只保存素数。
4. 我将每个素数从巨大的数组复制到正确维度的数组中。
5. 我返回仅包含我生成的素数的正确维度的数组。

问题

1. temp[]我可以将具有非零元素的整个块（一次）复制 到primes[] 而不必遍历两个数组并一个一个地复制元素吗？
2. 是否有任何数据结构的行为类似于可以随着元素的添加而增长的基元数组，而不是在实例化时需要维度？与使用基元数组相比，性能损失是多少？

版本 2（感谢Jon Skeet）：

版本 3（感谢Paul Tomblin）使用Erastosthenes 筛法：

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

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

我正在使用 Eratosthenes 筛解决 Sphere 的 Online Judge Prime Generator 。

我的代码适用于提供的测试用例。但是..正如问题明确指出的那样：

输入以单行中的测试用例数量 t (t<=10) 开始。在接下来的 t 行中的每一行中，都有两个数字 m 和 n ( 1 <= m <= n <= 1000000000, nm<=100000)，由空格分隔。

我知道该方法Integer.parseInt()在处理非常大的数字时会引发异常，并且在线法官指示正在引发异常，因此我将代码中的每个案例都更改parseInt为parseLong。

嗯，这件事在 Netbeans 6.5 上运行良好，m 和 n 的值很小。

输入+输出：

但是 JCreator LE 是这样说的：

这里我没有整数溢出，但是为什么 jcreator 会抱怨呢？

考虑到边界测试用例，该程序也在 Netbeans 上内爆：

我该如何处理问题陈述中那些巨大的整数？

编辑：根据建议，我已经更改了 BitSet 的布尔数组，但我仍然得到OutOFMemoryError：

输入输出：

当上述程序的 n=100000 时，我得到了 0.015 秒的运行时间。我还在 C 中实现了埃拉托色尼筛算法，并在 n=100000 时获得了 0.046 的运行时间。

我的上述算法如何比我已经实现的 Sieve 算法快。

我上述程序的时间复杂度是多少？

我的筛子的实施

我想找到 0 和 long 变量之间的质数，但我无法获得任何输出。

该程序是

谁能帮我找出程序中可能出现的错误？

这很无聊，我知道，但我需要一点帮助来理解 Eratosthenes 筛的实现。这是这个编程实践问题的解决方案。

我遇到问题的部分是startj. 现在，我可以看到p将从 3 开始的奇数循环，定义为(+ i i 3)。但我不明白 and 之间的关系p，startj即(+ (* 2 i i) (* 6 i) 3).

编辑：我知道这个想法是跳过以前筛选过的数字。谜题定义指出，在筛选一个数字时x，筛选应该从 的平方开始x。因此，在筛选 3 时，从消除 9 开始，依此类推。

但是，我不明白的是作者是如何想出这个表达的startj（从代数上讲）。

来自拼图评论：

通常，当按 n 筛选时，筛选从 n 平方开始，因为所有先前的 n 倍数都已被筛选。

表达式的其余部分与数字和筛分索引之间的交叉引用有关。表达式中有 2，因为我们在开始之前消除了所有偶数。表达式中有 3，因为 Scheme 向量是从零开始的，而数字 0、1 和 2 不是筛子的一部分。我认为6实际上是2和3的组合，但是我看代码已经有一段时间了，所以我把它留给你去弄清楚。

如果有人能帮我解决这个问题，那就太好了。谢谢！

我进行了一些搜索，但与我见过的所有其他实现相比，我找不到任何关于此实现的信息。

是的，我知道它只是打印出来，但这不是重要的部分。无论是时间还是其他，主要的陷阱是什么？

编辑：除了可扩展性之外还有其他问题吗？还要再次感谢关于推进主要发现的评论。

问题是：求所有小于 200 万的素数之和。

我几乎做了 Erastothenes 筛子的事情，下面的程序似乎适用于少数人，即将 LIMIT 定义为 10L 产生 17 作为答案。

我提交了 1179908154 作为答案，由以下程序生成，它是不正确的。

请帮忙指出问题。谢谢。