Tag: 初始化eratosthenes筛选

分割如何改善Eratosthenes筛选的运行时间？

我遇到了一个分段的Eratosthenes筛子实施，它的运行速度比传统版本高出许多倍。 有人可以解释一下细分如何改善运行时间？ 请注意，我想在[1，b]中找到素数。 它适用于这个想法:(寻找素数到10 ^ 9） 我们首先生成低于sqrt（10 ^ 9）的筛分质数，这是交叉多次所需的。 然后我们开始交叉第一个素数2的倍数，直到我们达到2> = segment_size的倍数，如果发生这种情况，我们使用（multiple – segment_size）计算下一个段中该倍数的索引并将其存储在一个单独的array（next []）。 然后我们使用相同的程序交叉下一个筛分素数的倍数。 一旦我们在第一段中划掉所有筛分质数的倍数，我们就在筛子arrays上迭代并打印出（或计数）质数。 为了筛选下一个段，我们重置了筛子arrays，并通过segment_size增加了较低的偏移量。 然后我们再次开始交叉倍数，对于每个筛选素数，我们从下一个数组中检索筛子索引，然后我们从那里开始交叉倍数…