埃拉托色尼的筛（减少空间复杂度）

Question

我想两个给定数字之间生成素数“A”和“B”（B> A）。我所做的是将布尔值存储在大小为b-1（即数字至b）的数组中，然后应用筛选方法。

有没有更好的办法，减少空间的复杂性，如果我不从至b需要的所有质数？

Answer 1

您需要存储小于等于b的平方根的所有素数，然后对于a和b之间的每个数字，检查它们是否可以被这些数字中的任何一个整除，并且它们不等于这些数字。所以在我们的情况下，幻数是sqrt（b）

Answer 2

您可以使用Eratosthenes的分段筛。基本的想法很简单。

在一个典型的筛子中，我们从大量的布尔值开始，将所有值设置为相同的值。这些代表奇数，从3开始。我们看第一个，看看它是真的，所以我们将它添加到素数列表中。然后，我们将该数字的每个倍数标记为不是素数。

现在，问题在于它不是非常缓存友好的。当我们标出每个数字的倍数时，我们会遍历整个数组。然后当我们到达最后时，我们从头开始（不再在缓存中）并再次遍历整个数组。每次通过数组时，我们再次从主存储器中读取整个数组。

对于分段筛，我们做的事情有点不同。我们首先发现只有我们关心的极限的平方根的质数。然后我们使用这些来标记主数组中的素数。这里的区别是订单其中我们标记了质数。而不是标出全部三个倍数，然后是所有倍数5，依此类推，我们首先标记适合缓存的数据的三倍。然后，我们回过头去标记适合缓存的数据的五个倍数，而不是继续增加数组中的数据。然后是7的倍数，依此类推。然后，当我们标记出该缓存大小的数据块中的所有倍数时，我们转向下一个缓存大小的数据块。我们首先在这个块中标记3的倍数，然后是5的倍数，依此类推，直到我们标记出该块中的所有倍数。我们继续这种模式，直到我们标出所有块中的所有非素数，然后我们完成了。

因此，如果N个素数低于我们关心的极限的平方根，那么一个幼稚的筛子将读取整个布尔数组的N次。相比之下，分段筛只会读取每个数据块的一次。一旦从主存储器读取大块数据，在从主存储器读取更多数据之前，该块上的所有处理完成。

这给出的确切加速将取决于缓存的速度与主内存的速度的比率，您使用的阵列的大小与缓存的大小等等。尽管如此，它通常是相当可观的 - 例如，在我的特定机器上，寻找高达1亿的质量，分段式筛具有大约10：1的速度优势。

有一点你必须记住，如果你使用的是C++。std::vector<bool>的一个众所周知的问题是在C++ 98/03下，vector<bool>被要求是一种专门化，它将每个布尔值存储为一个单独的位，并带有一些代理欺骗以获得类似于bool的行为。这项要求从此被解除，但许多图书馆仍然包括它。

对于非分段筛，通常是一种有用的折衷。虽然它需要一些额外的CPU时间来计算掩码，并且一次只修改一个位，但它可以为主内存节省足够的带宽，而不仅仅是补偿。使用分段筛，主内存的带宽几乎不是一个很大的因素，所以使用vector<char>通常似乎会给出更好的结果（至少在我使用编译器和处理器的情况下）。从分段筛获得最佳性能确实需要知道处理器缓存的大小，但要正确地获得它的正确性通常并不重要 - 如果您认为其大小比实际小，则不会必须最大限度地利用你的缓存，但你通常不会失去很多。