问题标签 [sieve-of-eratosthenes]

我正在从事 C 编程任务以在不使用 C 的平方根函数的情况下实现 Eratosthenes 的 Sieve。下面是我的输出和我的教授输出，我不确定我的代码中是什么导致它出错。有任何想法吗？

这是预期的输出

这是我的输出：

这是我的代码：

我一直在网上搜索埃拉托色尼筛法的实施方案，虽然我想出了很多内容，但似乎没有一个能像我需要的那样完成。

问题是大多数算法要么使用静态结束，要么使用迭代。这与我缺乏语言知识相结合，导致我向你们所有人寻求帮助。

我需要一个 Sieve 的实现，它接受一个参数（直到 Sieve 的数字），只使用递归，并且有一个带有#t（真）或#f（假）的数字的“缺点”列表。

所以基本上算法会这样：

1. 从 2 个输入的数字创建列表，每个数字都以 true 开头
2. 递归遍历并标记每个可被 2 整除的数字 false
3. 然后继续到列表中的下一个“真”数字，直到只有素数被标记为真
4. 输出列表

示例输出：

> (erat-sieve 20)

((2 . #t) (3 . #t) (4 . #f) (5 . #t) (6 . #f) (7 . #t) (8 . #f) (9 . #f) ( 10 . #f) (11 . #t) (12 . #f) (13 . #t) (14 . #f) (15 . #f) (16 . #f) (17 . #t) (18 . #f) (19 . #t) (20 . #f))

如果您还可以有评论彻底解释代码，那将非常感激。

谢谢！

已修改 :::所以我学到了一些方案来进一步解释我的问题......

这使得列表。

这将返回一个列表，其中每个除数的倍数都标记为 false。

现在这是我遇到问题的功能，它似乎应该可以工作，我已经手动完成了 3 次，但我无法弄清楚为什么它没有返回我需要的东西。

正如函数名称所暗示的那样，我要做的是，为列表中仍然标记为真的每个数字调用 mark-off-multiples。所以你传入，((3.#t)(4.#t)(5.#t))然后它调用mark-off-multiples2 并返回(3.#t)(4.#f)(5.#t)并附(2.#t)加到它。然后它再次调用自己传入(3.#t)(4.#f)(5.#t)并调用 mark-off-multiples 并返回列表的cdr(4.#f)(5.#t)并继续沿着列表向下...

然后我返回的输出是一个包含所有真值的列表。

这一点，希望能帮助你更好地理解我的困境。

我的 Eratosthenes 筛遇到了问题。我想写一个筛子，它不需要所有数字的数组，直到你想要的最大素数，而只是在筛子到达它时跟踪每个素数倍数。这意味着您不必预先完成所有工作，而可以在需要时确定下一个素数。添加诸如“从 N 开始查找 K 个素数”之类的界面功能也很容易。这是伪代码：

所以问题来了：我正确计算了前 31 个素数（最多 127 个），但之后它认为每个数字都是素数。我已经把我的代码放在了 Ideone 上——我希望它是一些 Java 集合行为，或者一个微不足道的错误，而不是算法本身。我想不出算法应该在一定数量的素数后中断的原因。我已经手动确认在 127 之后，如果堆的排序正确，我的算法应该将 128 识别为不是素数，但这不是代码向我显示的。

有什么建议么？

http://ideone.com/E07Te

（当然，一旦我得到基本算法的工作，我会增加 2（以跳过所有非素数偶数）。我可能还会使 Sieve 成为可迭代的。）

制作一个简单的筛子很容易：

但是当 N 非常大并且我不能在内存中保存那种数组时呢？我查找了分段筛方法，它们似乎涉及在 sqrt(N) 之前找到素数，但我不明白它是如何工作的。如果 N 非常大（比如 10^18）怎么办？

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

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

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

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

我在一个编程网站上遇到了以下问题：彼得想为他的密码系统生成一些素数。帮助他！你的任务是生成两个给定数字之间的所有素数！

输入

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

我想出了以下解决方案：

在阅读了一些建议后，我编辑了我的解决方案。我仍然收到超出时间限制的错误。关于如何进一步优化这一点的更多建议？我正在计算直到 32000 的所有素数，然后使用这些来找到 n 到 m 之间的素数。

谢谢，罗希特

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

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

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

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

这是代码：

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

一种方法可能是：

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

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

谢谢！！

这段代码取自《Haskell Road to Logic, Math and Programming》一书。它实现了埃拉托色尼筛算法并解决了 Project Euler 问题 10。

实际上，它的运行速度甚至比天真的素数测试还要慢。有人可以解释这种行为吗？

我怀疑这与在标记函数中迭代列表中的每个元素有关。

谢谢。

我对 Haskell 很陌生，我只是想找到前 200 万个素数的总和。我正在尝试使用筛子生成素数（我认为是 Eratosthenes 的筛子？），但它真的很慢，我不知道为什么。这是我的代码。

提前致谢。

我尝试为此[问题]实现分段筛算法：http://www.spoj.pl/problems/PRIME1/，如下所示：

尽管如此，我还是得到了 TLE .. 我不明白还需要什么其他优化。请帮助..

编辑1：只是试图在恒定时间内实现 fd_p() ... [失败] .. plz 如果你能帮助我解决这个错误..

编辑 2：问题已解决。