Eratosthenes筛(降低空间复杂度)

Question

我想在两个给定的数字‘a’和‘b’(b > a)之间生成素数。我所做的是将布尔值存储在一个大小为b-1的数组中(即数字2到b)，然后我应用了筛法。

如果我不需要从2到b的所有素数，那么还有更好的方法来降低空间复杂度吗？

Answer 1

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

Answer 2

你可以使用埃拉托斯提尼的分割筛。基本的想法很简单。

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

现在，问题在于它对缓存不太友好。当我们标记每个数字的倍数时，我们遍历整个数组。然后，当我们到达终点时，我们从头开始(不再在缓存中)，并再次遍历整个数组。每次遍历数组时，我们都会再次从主内存读取整个数组。

对于一个分割的筛子，我们做的事情有点不同。我们首先只找到我们所关心的极限的平方根的素数。然后我们使用这些标记主数组中的素数。这里的区别在于我们标记素数的顺序。与其将所有3的倍数，然后是5的倍数，以此类推，我们首先对缓存中适合的数据进行3的倍数标记。然后，我们不再继续处理数组中的更多数据，而是返回并标记符合缓存的数据的倍数为5。然后7的倍数，以此类推。

然后，当我们标记掉缓存大小的数据块中的所有倍数时，我们将继续讨论下一个缓存大小的数据块。我们从在这个块中标记3的倍数开始，然后再加上5的倍数，以此类推，直到我们把这个块中的所有倍数都划掉。我们继续这个模式，直到我们把所有的非素数都划掉，我们就完成了。

因此，给定N个素数低于我们所关心的限制的平方根，一个简单的筛子将读取整个Booleans N次数组。相反，分割的筛子只会读取数据的每一块一次。一旦从主存读取数据块，则在从主内存读取更多数据之前，对该块进行所有处理。

它所提供的确切速度将取决于缓存速度与主内存速度的比率、所使用的数组的大小与缓存的大小等。尽管如此，它通常是相当可观的--例如，在我的特定机器上，寻找高达1亿的素数，分段筛子的速度优势约为10:1。

如果您正在使用C++，您必须记住一件事。std::vector<bool>的一个众所周知的问题是在C++98/03下，vector<bool>必须是一种专门化，它将每个布尔值存储为一个带有某种代理欺骗的位元，以获得类似bool的行为。这一要求已被取消，但许多图书馆仍然包括它。

有了一个没有分割的筛子，这通常是一个有用的权衡。虽然它需要额外的CPU时间来计算掩码，并且每次只修改一个比特，但它节省了足够的主存带宽，足以弥补不足。

使用分段的筛子，主内存的带宽几乎不是一个很大的因素，所以通常使用vector<char>似乎会带来更好的结果(至少在我有方便的编译器和处理器时是这样)。

从一个分割的筛子中获得最佳性能确实需要知道处理器缓存的大小，但准确正确并不是关键--如果你假设它的大小小于实际大小，你不一定会得到缓存的最佳使用，但你通常也不会损失很多。