|
我遇到了一个分段实施的Eratosthenes筛子,它的运行速度比传统版本高出许多倍.
有人可以解释一下细分如何改善运行时间？
请注意,我想在[1,b]中找到素数.
它适用于这个想法:(寻找素数到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…
解决方法
分段筛的操作与常规筛相同,因此大O时间复杂度不变.不同之处在于使用内存.如果筛子足够小以适合记忆,则没有区别.随着筛子尺寸的增加,参考局部成为一个因素,因此筛分过程减慢.在极端情况下,如果筛子不适合存储器并且必须被分页到磁盘,则筛分过程将变得非常慢.分段筛使记忆尺寸保持恒定,并且可能很小,因此筛的所有通道都是局部的,因此很快.
（编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
