问题标签 [sieve-of-eratosthenes]

大家好！所以我几乎完成了一个我开始为学校处理的涉及埃拉托色尼筛的问题。我设法让程序打印出从 2 到 1000 的平方根的所有素数。但是，我的老师要求我使用 CF Gauss 的素数假设（？）。这就是他所说的：CF Gauss 假设 (N) 当 N 接近无穷大时，小于或等于 N 的素数数定义为 (N) = N/loge(N)。这被称为素数假说。在 for 循环中打印素数、指示其序数（1、2、3 等）的计数器和 (N) 的值。

我尝试制作另一个 for 循环，并打印素数，但它对我不起作用！:( 呃。任何帮助将不胜感激！:)

我在这个网站上找到了 Eratosthenes 筛子的 LINQ 实现。我了解筛子的基本概念，但有一个细节我不明白。第一个 Enumerable.Range(0,168) 的目的是什么？

解决问题时遇到了一点麻烦：“计算低于 200 万的素数之和”。我正在使用“埃拉托色尼筛法”。我的方法可以很好地找到直到 100 的素数，但是当我尝试找到直到 2,000,000 的素数总和时，我得到的答案不正确。

我正在通过项目 euler 学习 clojure，并且正在研究第 10 号问题（找到低于 200 万的所有素数的总和。我为 Eratosthenes 的筛子实现了一个非常字面的算法，但它的工作速度太慢而无法使用高达 200 万。我尝试使用 loop-recur 来实现它，以不创建任何新帧，但这对性能没有太大影响。

这是我为 python3 的 Eratosthenes 筛子找到的算法代码。我想要做的是编辑它，以便我可以输入一个底部和顶部的范围，然后输入一个素数列表直到底部一个，它将输出该范围内的素数列表。但是，我不太确定该怎么做。如果您能提供帮助，将不胜感激。

我阅读了有关该算法的 F# 版本的另一篇文章。我发现它非常优雅，并尝试将答案的一些想法结合起来。

尽管我对其进行了优化以减少检查（仅检查 6 左右的数字）并省略不必要的缓存，但它仍然非常缓慢。计算第 10,000^个素数已经花费了 5 多分钟。使用命令式方法，我可以在不多的时间内测试所有 31 位整数。

所以我的问题是我是否遗漏了一些让这一切变得如此缓慢的东西。例如，在另一篇文章中，有人推测LazyList可能会使用锁定。有人有想法吗？

由于 StackOverflow 的规则说不要发布新问题作为答案，我觉得我必须为此开始一个新话题。

这是代码：

我在查找第 10,001 个素数时内存不足。

这是因为在每次“迭代”（在这种情况下这是正确的术语吗？）之后primes，我将要调用的函数堆栈增加一个以获取下一个元素？

我在网上找到的一个不采用迭代解决方案的解决方案（我想避免进入函数式编程/惯用 scala）是这样的（问题 7）：

据我所知，这不会导致这种类似递归的方式。这是一个好方法，还是你知道更好的方法？

我正在尝试编写一个实现 Eratosthenes 筛子的素数生成器。但是，它在输出中包含一些合数（例如 25、49 和其他 5 和 7 的倍数）。

这是我的代码：

这是输出....

/blockquote>

1 2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97

我正在尝试使用 python 进行一些计算，但内存不足。因此，我想读/写一个文件以释放内存。我需要一个非常大的列表对象之类的东西，所以我想为文件中的每个对象写一行并读/写该行而不是内存。行排序对我来说很重要，因为我将使用行号作为索引。所以我想知道如何在不移动其他行的情况下替换 python 中的行（实际上，移动行是可以的，只要它们返回到我期望的位置）。

编辑

我正在尝试帮助一个朋友，这在 python 中比我差或等于我。该代码应该找到最大的素数，除以给定的非素数。此代码适用于数字，直到数字达到 100 万，但死后，我的记忆力在尝试制作数字列表时耗尽。

为每个索引写入不同的文件怎么样？例如十亿个长整数文件名的文件，文件中只有一个数字？

我看到了这个使用 Eratosthenes 的 Sieve 方法查找素数的 c 代码，但由于分配如此大的 char 数组的内存消耗，我无法将其扩展到更大的整数（例如，1000000000 甚至更大）。

将代码扩展到更大数字的策略是什么？也欢迎任何参考。

谢谢。