分段如何提高埃拉托色尼筛的运行时间？
我遇到了一个分割的埃拉托斯特尼筛子的实现，它promise比传统版本运行快很多倍。有人可以解释一下分段如何改善运行时间吗？请注意，我想在 [1，b] 中找到素数。
它的原理是：（用于查找10^9之前的素数）
>
我们首先生成低于 sqrt（10^9） 的筛分素数，这是偶联倍数所必需的。然后我们开始划掉第一个素数2的倍数，直到我们达到2的倍数
为了筛选下一个段，我们重置了筛选数组，并通过segment_size增加了下偏移量。然后我们再次开始剪掉倍数，对于每个筛选素数，我们从下一个数组中检索筛选索引，然后从那里开始剪掉倍。。。
共有2个答案
即使筛子完全适合RAM，访问的位置仍然有很大的不同。一个C语言实现的概率只有Eratosthennes，它需要将近半分钟的时间来筛选前2^32个数字；相同的实现在256 KB的小片段（2^21位，代表2^22个数字）中初始化同一个筛子，在我的老化Nehalem上只需要8.5秒，它有256 KB L2缓存。
在对缓存友好的小段中筛选的速度在范围的较高区域会降低，因为筛选每次都必须迭代所有因子，直到sqrt（n），而不管段有多小或多大。这对于接近2^64的段最为明显，其中小因子包含203,280,221个素数（即完整的32位筛选）。
然而，分段操作仍然胜过完全筛选。你可以在接近2^64的地方筛选出每秒几百万个素数，在更低的地方每秒几千万个素数。那是数质数，不是数原矿。即使你有大量的记忆，全筛子在2^32附近也不实用。
分段筛子执行的所有操作与常规筛子相同，因此big-O时间复杂度不变。不同之处在于内存的使用。如果筛子足够小以适合内存，则没有差异。随着筛子大小的增加，引用的局部性成为一个因素，因此筛子过程变慢。在极端情况下，如果筛子不适合内存，必须分页到磁盘，筛子过程将变得非常慢。分段筛子保持内存大小不变，并且可能很小，因此筛子的所有访问都是本地的，因此速度很快。
-
做一个简单的筛子很容易： 但是当N非常大并且我无法在内存中持有这种数组时，该怎么办？我已经查找了分段筛方法，它们似乎涉及查找素数，直到sqrt（N），但我不明白它是如何工作的。如果 N 非常大（比如 10^18）怎么办？
-
我正在尝试对厄拉多塞的筛子进行并行实现。我做了一个布尔列表，对于给定的大小，用true填充。无论何时发现一个素数，该素数的所有倍数在布尔列表中都被标记为假。 我试图使这个算法并行的方法是在仍然过滤初始质数的同时启动一个新线程。例如，算法从素数 = 2 开始。在 for 循环中，当素数 * 素数时，我做另一个 for 循环，其中检查素数 （2） 和素数 * 素数 （4） 之间的每个数字。如果布尔列表
-
下面是我对埃拉托色尼筛的实现，以找到达到上限参数的质数。 目前，当我的参数为 2，000，000 时，我的代码将在大约 2 秒内完成。我看到我正在通过将数字设置为零来做一个额外的步骤，然后压缩而不是一步删除这些数字。 我将如何着手实现这一点？你还有其他提高我的代码速度的建议吗？
-
就像这个问题一样，我也在厄拉多塞的筛子上工作。同样来自《c语言编程原理和实践》一书的第4章。我能够正确地实现它，并且它的功能完全符合练习的要求。 现在，我怎样才能在输入的中处理真正的大数字？类型应该允许我输入2^32=4,294,967,296的数字。但是我不能，我运行内存溢出。是的，我已经计算过了：存储2^32量的int，每个32位。所以32/8*2^32=16 GiB的内存。我只有4 GiB…
-
我试图找到素数使用厄拉多塞筛位数组，但我使用的是无符号整数数组。我需要能够产生多达2，147，483，647个素数。我的代码工作正常，可以生成大约10，000，000个，但是当我增加数组的大小以容纳更大的数字时，它失败了。有人能指导我如何用c语言(不是c语言)使用位向量吗？谢谢 这是我的代码：
-
我正在尝试让我的埃拉托斯特尼筛程序仅输出用户请求的前n个素数。Sieve本身工作得很好 - 它正确地输出了前100个素数（如下面的数组所示），但是最后一个循环中的计数器变量无法正常工作，我无法找出原因。例如，如果用户输入“5”表示 n，则只会打印前 3 个定焦值。 有人可以帮我找出我的错误吗？我的目的是让“count”成为一个非常简单的计数器，每次都会增加1，直到它达到n。