问题标签 [sieve-of-eratosthenes]

我正在寻找一个 J 代码来执行以下操作。

假设我有一个随机整数列表（已排序）， 2 3 4 5 7 21 45 49 61 我想从第一个元素开始并删除列表中元素的任何倍数，然后移动到下一个元素取消它的倍数， 等等等等。

因此，我正在查看的输出是 2 3 5 7 61。基本上是 Eratosthenes 的筛子。如果有人也可以解释代码将不胜感激，因为我正在学习 J 并且发现很难获得大多数代码:(

问候， babsdoc

可能重复：
在python中列出N以下所有素数的最快方法

很久没做编程了，做这个纯粹是为了好玩，对高级Python也不是很了解，但是……我写了这个，想知道是不是真的是Eratosthenes Sieve程序，如果是，我怎样才能让它更快。我真的不希望有人发布一个解决方案，但更多告诉我如何调整我的。

谢谢你的帮助。

顺便说一句 - 它在 Python 2.7 中

I'm new to Haskell and I'm trying to implement Euler's Sieve in stream processing style.

When I checked the Haskell Wiki page about prime numbers, I found some mysterious optimization technique for streams. In 3.8 Linear merging of that wiki:

And it says

“<strong>The double primes feed is introduced here to prevent unneeded memoization and thus prevent memory leak, as per Melissa O'Neill's code.”</p>

How could this be? I can't figure out how it works.

我编写了以下程序来显示最多 150 的所有素数。它根本没有执行。它有什么问题？

我尝试使用 Sieve Eratosthenes 方法列出最多 20 亿个素数。这是我用的！

我面临的问题是，我无法超过 1000 万个数字。当我尝试时，它显示“分段错误”。我在网上找了找原因。有些网站说，这是编译器本身的内存分配限制。有人说，这是硬件限制。我正在使用安装了 4GB RAM 的 64 位处理器。请建议我列出它们的方法。

我使用 Sieve 的方法编写了以下代码来列出所有最多 20 亿个素数。我使用位掩码进行标记。虽然我能够正确获得素数，但每次都会丢失开头的几个素数。请帮我找出程序中的错误。

我有一个编程任务，用 C++ 编写一个程序，该程序找到所有小于n的素数（用户输入）。一半的任务涉及埃拉托色尼筛。我的代码正在运行（阅读：分配完成），但在我编辑输出之前，它无条件地将n-3、n-2和n-1打印为素数，即使它们不是素数。我不确定为什么会这样。对于程序为何如此运作，我将不胜感激一些反馈和想法。这是未更改的代码：

请注意，我使用的是 ListNode 类和 LinkedList 类，它们都是功能齐全的。编辑：部分主要添加；注意for循环中的第二项是size-3。如果它保留在size，程序会输出 3 个额外的非素数。

在 Haskell 中，我在Rosetta Code 页面上找到了三个简单的 Eratosthenes 筛子实现。

现在我的问题是，在什么情况下应该使用哪一个？

纠正我最初的推理也会有帮助：

我假设 List one 对于 Haskeller 来说是最惯用和最容易阅读的。但是，它正确吗？我想知道它是否遇到与我后来学到的另一个基于列表的筛子相同的问题，但实际上并没有实现算法：（
编辑：这里显示的是我知道有问题的基于列表的筛子，而不是来自 RosettaCode 的那个，我粘贴在底部）

在性能方面，不可变数组似乎是赢家。上限m为 时2000000，时间约为：

• 列表 1.3s
• 阵列 0.6s
• 可变数组 1.8s

所以我会选择 Array 来提高性能。

当然，可变数组也很容易推理，因为我有更命令式的语言背景。不过，如果我在 Haskell 中编码，我不确定为什么我会选择这个，因为它比其他的慢而且不习惯。

此处复制代码以供参考：

列表：

不可变数组：

可变数组：

编辑

• 我在顶部展示了特纳的筛子，但这不是我要与其他两个比较的基于列表的示例。我只是想知道基于列表的示例是否存在与特纳相同的“不是正确的埃拉托色尼筛法”问题。
• 看来性能比较是不公平的，因为可变数组示例也经历了偶数并使用Integer而不是Int......

我已经编辑了程序，以便它可以工作（使用小数字）但是我不明白如何按照建议实现累加器。原因是因为P在整个过程中都在变化，所以我不知道我应该以哪个粒度来分解母列表。Erastosthenes 的筛子只对生成较小的素数有效，所以也许我应该选择一个不同的算法来使用。有人可以推荐一个体面的算法来计算 600851475143 的最高素数吗？请不要给我代码我更喜欢这种性质的维基百科文章。

我发现写这个非常困难，而且我知道它有一些不是很优雅的东西，比如我将 2 硬编码为质数的方式。因此，我将不胜感激任何 C&C 以及有关如何解决此类问题的建议。我查看了其他实现，我完全不知道作者如何以这种方式思考，但它是我想掌握的东西。

我已经弄清楚我可以忘记这个列表，直到找到最近的素数，但是我不知道我应该如何产生一个结束界限（微妙的幽默）。我认为可能有一些我可以使用的东西，比如 lists:seq(P,something) 并且当我使用模数而不是每次都将其重置为 0 时，计数器将能够处理它。我只做过AS级别的数学，所以我不知道这是什么。

我什至不能这样做，我可以吗？因为我将不得不从整个列表中删除 2 的倍数。我认为除非我将数据缓存到硬盘驱动器，否则该算法将不起作用，所以我重新寻找更好的算法。

我现在正在考虑编写一个算法，它只使用一个计数器并保留一个素数列表，这些素数是不与先前生成的素数均分的数字，这是一个好方法吗？

这是我写的新算法，我认为它应该可以工作，但我收到以下错误“sieve2.erl:7: call to local/imported function is_prime/2 is legal in guard”我认为这只是 erlang 的一个方面我不明白。但是，我不知道如何找到有关它的材料。[我故意不使用高阶函数等，因为我只在 learnyousomeerlang.org 中阅读了关于递归的部分内容]

第二个算法不会崩溃但运行得太慢，我想我应该重新实现第一个但这次忘记了直到最近发现的素数的数字，有人知道我可以用什么作为结束界限吗？在查看其他解决方案之后，似乎人们有时只是设置了一个任意限制，即 200 万（这是我真的不想做的事情。其他人使用“懒惰”的实现，这就是我认为我正在做的事情。

我正在从 Robert Sedgewick 的 C++ 算法中学习 C++。现在，我正在研究 Eratosthenes 筛，用户指定了最大素数的上限。当我以最大 46349 运行代码时，它会运行并打印出最多 46349 的所有素数，但是当我以最大 46350 运行代码时，会发生分段错误。有人可以帮忙解释为什么吗？

代码：