如何分割提高埃拉托色尼的筛的运行时间？ [英] How does segmentation improve the running time of Sieve of Eratosthenes?

问题描述

我碰到一个分段实施筛埃拉托色尼的这将运行速度比传统的版本快很多倍。 是否有人可以解释如何分割提高了运行时间？ 请注意，我想找到的素数的 [1，B]

它适用于这样的想法：（寻找素数到10 ^ 9）

  

  

• 我们首先生成下面的sqrt（10 ^ 9），这是需要跨关倍数筛选素数。然后我们开始渡区切换的第一原2的倍数，直到我们达到2> = segment_size的倍数，如果发生这种情况，我们计算出多个的索引中的下一个段使用（多 - segment_size）并将其存储在一个单独的阵列（下一页[]）。我们然后横断使用相同的步骤的下一个筛分素数的倍数。一旦我们已经越过关闭所有筛选素数的倍数，在第一部分，我们遍历数组筛，并打印出（或计数）的素数。

  

• 为了筛我们重置筛数组中的下段，我们增加了低segment_size抵消。然后我们重新开始穿越过多次，为每个筛分总理，我们检索筛指数从下一个阵列，我们开始穿越过倍数从那里...

  

解决方案

一个分段筛做所有相同的操作常规筛子，所以大O的时间复杂度不变。所不同的是，在使用的存储器。如果筛是足够小，适合在存储器中，没有差别。作为筛子尺寸的增加，参考局部性变为一个因素，所以筛分过程减慢。在极端的情况下，如果筛不适合在存储器，并具有被寻呼到磁盘，筛分过程将变得非常慢。分段的筛保持存储器大小恒定，和presumably小，所以筛的所有访问是局部的，从而快速

I came across a segmented implementation of sieve of Eratosthenes which promises to run many times faster than the conventional version. Can someone please explain how segmentation improves the running time? Note that I want to find prime numbers in [1,b].

It works on this idea: (for finding prime numbers till 10^9)

• We first generate the sieving primes below sqrt(10^9) which are needed to cross-off multiples. Then we start crossing-off the multiples of the first prime 2 until we reach a multiple of 2 >= segment_size, if this happens we calculate the index of that multiple in the next segment using (multiple - segment_size) and store it in a separate array (next[]). We then cross-off the multiples of the next sieving primes using the same procedure. Once we have crossed-off the multiples of all sieving primes in the first segment we iterate over the sieve array and print out (or count) the primes.

• In order to sieve the next segment we reset the sieve array and we increment the lower offset by segment_size. Then we start crossing-off multiples again, for each sieving prime we retrieve the sieve index from the next array and we start crossing-off multiples from there on...

解决方案

A segmented sieve does all the same operations as a regular sieve, so the big-O time complexity is unchanged. The difference is in the use of memory. If the sieve is small enough to fit in memory, there is no difference. As the size of the sieve increases, locality of reference becomes a factor, so the sieving process slows down. In the extreme case, if the sieve doesn't fit in memory and has to be paged to disk, the sieving process will become very slow. A segmented sieve keeps the memory size constant, and presumably small, so all accesses of the sieve are local, thus fast.

这篇关于如何分割提高埃拉托色尼的筛的运行时间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！