2 回答
您需要存储小于等于 b 平方根的所有素数，然后对于 a 和 b 之间的每个数字，检查它们是否可以被这些数字中的任何一个整除并且它们不等于这些数字。所以在我们的例子中，幻数是 sqrt(b)
您可以使用 Eratosthenes 的分段筛。基本思想非常简单。
在一个典型的筛子中，我们从一大堆布尔值开始，全部设置为相同的值。这些代表奇数，从 3 开始。我们看第一个，发现它是真的，所以我们将它添加到素数列表中。然后我们将该数字的每个倍数标记为非质数。
现在，问题在于它对缓存不是很友好。当我们标记每个数字的倍数时，我们遍历整个数组。然后当我们到达终点时，我们从头开始（不再在缓存中）并再次遍历整个数组。每次通过数组，我们都会再次从主存中读取整个数组。
对于分段筛，我们做的事情有点不同。我们首先只找到直到我们关心的极限平方根的素数。然后我们用它们来标记主数组中的素数。这里的区别是我们标记素数的顺序。不是标记所有3 的倍数，然后标记所有 5 的倍数，等等，我们首先标记出适合缓存的数据的 3 的倍数。然后，我们不再继续处理数组中的更多数据，而是返回并标记出适合缓存中数据的 5 的倍数。然后是 7 的倍数，以此类推。
然后，当我们标记出该缓存大小的数据块中的所有倍数时，我们将继续处理下一个缓存大小的数据块。我们从标记这个块中的 3 的倍数开始，然后标记 5 的倍数，依此类推，直到我们标记掉了这个块中的所有倍数。我们继续这种模式，直到我们标记出所有块中的所有非质数，我们就完成了。
因此，给定 N 个低于我们关心的极限平方根的素数，一个朴素的筛子将读取整个布尔数组 N 次。相比之下，分段筛只会读取每个数据块一次。一旦从主内存中读取了一块数据，在从主内存中读取更多数据之前，对该块的所有处理都已完成。
这给出的确切加速将取决于高速缓存速度与主内存速度的比率、您使用的阵列的大小与高速缓存的大小等等。尽管如此，它通常是相当可观的——例如，在我的特定机器上，寻找高达 1 亿的素数时，分段筛的速度优势约为 10:1。
如果您使用的是 C++，您必须记住一件事。一个众所周知的问题std::vector<bool>是在 C++98/03 下，vector<bool>需要将每个布尔值存储为一个位，并使用一些代理技巧来获得类似布尔的行为。此后该要求已被取消，但许多图书馆仍然包含它。
使用非分段筛，这通常是一个有用的权衡。虽然计算掩码需要一点额外的 CPU 时间，例如一次只修改一个位，但它为主内存节省了足够的带宽来弥补。
使用分段筛，到主内存的带宽几乎没有那么大的因素，因此使用 avector<char>通常似乎可以提供更好的结果（至少对于我手边的编译器和处理器而言）。
从分段筛获得最佳性能确实需要了解处理器缓存的大小，但精确正确通常并不重要 - 如果您假设大小小于实际大小，您不一定会获得最佳使用你的缓存，但你通常也不会丢失很多。