问题标签 [sieve-of-eratosthenes]

我正在尝试在python中实现eratosthenes的筛子，但是当试图找到所有素数直到例如779695003923747564589111193840021的平方根时，我收到一个错误，说range（）的结果有太多项目。我的问题是，我该如何避免这个问题，如果我用 while 循环实例化列表，我会收到一个错误，说我使用了太多内存（甚至在它开始使用页面文件之前），下面列出了这两个：

使用范围（）

使用同时：

来自维基百科：

该算法的复杂性是 O(n(logn)(loglogn))位运算。

你是怎么做到的？

复杂性包括这个loglogn词告诉我有一个sqrt(n)地方。

假设我在前 100 个数字（n = 100）上运行筛子，假设将数字标记为复合数字需要恒定时间（数组实现），我们使用的次数mark_composite()类似于

并且要找到下一个素数（例如，7在删除所有 的倍数的数字后跳转到5），操作数将是O(n)。

因此，复杂性将是O(n^3)。你同意？

我使用埃拉托色尼筛法和 Python 3.1编写了一个素数生成器。该代码在ideone.com上以 0.32 秒的时间正确而优雅地运行，以生成高达 1,000,000 的素数。

问题是，当我尝试生成高达 1,000,000,000 的数字时，内存不足。

可以想象，分配 10 亿个布尔值（ Python 中每个1 字节4 或 8 字节（见注释））确实不可行，所以我研究了bitstring。我想，为每个标志使用 1 位会更节省内存。然而，该程序的性能急剧下降 - 运行时间为 24 秒，质数高达 1,000,000。这可能是由于位串的内部实现。

您可以注释/取消注释这三行，以查看我更改为使用 BitString 的内容，如上面的代码片段。

我的问题是，有没有办法加快我的程序，有或没有位串？

编辑：请在发布之前自己测试代码。自然，我不能接受运行速度比我现有代码慢的答案。

再次编辑：

我已经在我的机器上编译了一个基准测试列表。

我在 Clojure 中有这个 Eratosthenes 筛子的实现：

对于更大的n（如 20000）它以堆栈溢出结束。为什么尾部呼叫消除在这里不起作用？如何解决？

这是我在 Clojure 中对 Erathosthene 筛的实现（基于关于流的 SICP 课程）：

现在，当我取前 100 个素数时，一切正常：

但是，如果我尝试取前 1000 个素数，程序会因为堆栈溢出而中断。我想知道是否有可能以某种方式将函数筛更改为尾递归，并且仍然保留算法的“流”？

有什么帮助？？？

首先 - 我在这个论坛上查了很多，但我没有找到足够快的东西。我尝试创建一个函数来返回指定范围内的素数。例如，我使用 Eratosthenes 的筛子做了这个函数（在 C# 中）。我也尝试了 Atkin 的筛子，但 Eratosthenes 的筛子跑得更快（在我的实现中）：

它的运行速度比我发现的代码和算法快两倍……应该有一种更快的方法来找到素数，你能帮我吗？

我正在解决 Haskell 中的一些经典问题以发展我的功能技能，并且在实施此“Programming Praxis”站点上建议的优化时遇到问题：

对于这个问题，我有三种解决方案，与第二种解决方案相比，第三种方法太慢了。有人可以建议对我的代码进行一些改进吗？

我的实现是：

我已经实施了埃拉托色尼筛法来解决SPOJ问题PRIME1。虽然输出很好，但我的提交超过了时间限制。如何减少运行时间？

澄清一下，这不是作业问题:)

我想为我正在构建的数学应用程序找到素数，并遇到了埃拉托色尼筛法。

我已经用 Python 编写了它的实现。但这非常慢。例如，如果我想找到所有小于 200 万的素数。它需要> 20分钟。（我在这一点上停止了它）。我怎样才能加快速度？

更新： 我最终对这段代码进行了分析，发现从列表中删除一个元素花了很多时间。考虑到它必须遍历整个列表（最坏情况）才能找到元素，然后将其删除，然后重新调整列表（也许还有一些副本？），这是可以理解的。无论如何，我把字典列表扔掉了。我的新实现-

我用 Java 快速实现了 SoE 算法（代码在最后）。我的双核 AMD 处理器上的输出是：

• 正如预期的那样，“肉类”部分消耗了最长时间。

• 我的一个观察结果是 usingMath.pow(variable, 2)比(variable * variable). 我认为除了函数跳转之外，可能还有其他开销。

• Math.pow(x, 2) 是否对 2、3 等的幂进行了优化？我问是因为那里有一些用户贡献的 Java 库，它们的乘法算法比 Java 的本机算法快得多。

以下是我的问题：

• 您可以向“肉类”部分建议哪些算术优化？有什么办法可以完全避免模运算符？

• 当 start == end 时该功能不起作用。如果我做 sieve(4, 4)，返回的数组长度为 1: [4]。我究竟做错了什么？它应该返回 []（基本上是 new int(0)）。

• 您知道哪些与快速数字/数学相关的 Java 库？

谢谢阅读。最后这是我写的代码：不是 GangOfFour/TopCoder 质量，但也不是太可悲（我希望！而且 SO 的代码格式有点……奇怪？）：

感谢所有的反馈。这是下面的固定版本（直到有人设法再次打破它:)