问题标签 [sieve-of-eratosthenes]

我正在尝试使用Sieve of Eratosthenes算法实现素数生成器。我这样做只是为了尝试使用递归迭代器合并来实现 sifter。

我要做的是：

输出是：

第一个被筛选出来的数字是4。但接下来是12，不是6应该的。这是为什么？我用以下代码检查了它：

因此，正如我们所见，在测试条件下， sifter 会产生正确的结果。

我在哪里犯错？我认为这一定是我看不到的微不足道的事情。

我的目标是关闭或设置为假，所有不是素数的阵列点。数组作为参数提供。

代码工作正常，我只是想知道是否有比使用更有效的方法：

将这些数组项重置为真。

提前致谢！

我试图找出高达 200 万的所有素数的总和。

所以我为它写了以下代码：

答案应该是142913828922，但我得到了142889228620。

你能告诉我出了什么问题吗？我想不通。

在浏览了一些SO 帖子后，我发现埃拉托色尼筛法是生成素数的最佳和最快的方法。

我想生成两个数字之间的质数，比如a和b。

AFAIK，在 Sieve 的方法中，空间复杂度为O(b)。

PS：我写的是Big-O而不是Theta，因为不知道能不能减少空间需求。

我们可以降低埃拉托色尼筛中的空间复杂度吗？

我尝试了几次，但仍然给了我 ArrayOutOfIndex。但我想节省内存，所以我使用

代替

这给了我第 23 行和第 47 行的 ArrayOutOfIndex

第 23 行：

第 47 行：

这是我为实现Eratosthenes 的 Sieve编写的一些代码：

奇怪的是，无论何时num在系列 6、10、14、18、22... 中，代码都会在释放内存时随以下堆栈中止（对于 other 运行正常n）：

但我没有看到错误，也看不到这些数字背后的逻辑，它们之间的间隔为 4。这里的错误是什么？

这是我为在上限可以大到 1000000000 的范围之间查找素数而编写的代码。我使用了 Hashmap，除了 2 之外没有存储任何偶数，也没有存储 sero 和 1。但仍然当我使用输入 lb = 1 和 ub = 1000000000 运行此代码时，它会给出运行时错误，（内存不足）。请帮助

这是我的代码：-

好的，在收到答案后，我编码了这个：但它仍然在给 TLE

当我运行我的程序时，出现以下异常：

这段代码有什么问题？

我们被指派制作一个与 Eratosthenes 算法的 Sieve 并行的 java 程序。我用我知道的每一种方式都尝试了好几次，但一直没能把它弄好。我应该使用质数小于估算的数字的填充数组。这是我的代码，有人可以帮我仔细检查程序和/或找出我收到此错误的原因吗？任何帮助表示赞赏。

按照M. O'Neill 的精彩论文，我尝试在 Python 中实现一些惰性的、无限版本的 Eratosthenes 筛。我惊讶地发现，论文声称应该运行得更快的基于堆的版本实际上对我来说慢了两倍多。

该论文包含两个示例，一个基于 dict，我已将其翻译（来自 Haskell），因此：

论文中的第二个示例演示了优先级队列作为数据结构的使用。它还使用惰性列表，而不是简单的增量，为了公平测试，我没有这样做。（此外，我在惰性列表中使用了实例，itertools.count但我发现它的运行速度稍慢）。

我对这两个进行了计时，以及一个“渴望”的版本，这里没有复制，它产生了一个低于限制的所有素数的列表：

'eager' 版本更快并不奇怪——它基本上是在内存使用、必须指定上限的不便和 CPU 时间之间进行权衡。然而，当论文声称它更高效时，我确实发现版本慢得多，这让我感到惊讶。heapq我的实施有问题吗？或者仅仅是因为我们都知道，dicts 是超快的（而且heapq相对较慢）？