Dhr*_*ick 3 c c++ algorithm primes sieve-of-eratosthenes
我遇到了一个分段实施的Eratosthenes筛子,它的运行速度比传统版本高出许多倍.有人可以解释一下细分如何改善运行时间？请注意,我想在[1,b]中找到素数.
它适用于这个想法:(寻找素数到10 ^ 9)
我们首先生成低于sqrt(10 ^ 9)的筛分质数,这是交叉倍数所需的.然后我们开始交叉第一个素数2的倍数,直到我们达到2> = segment_size的倍数,如果发生这种情况,我们使用(multiple-segment_size)计算下一个段中该倍数的索引并将其存储在一个单独的数组(下一个[]).然后我们使用相同的程序交叉下一个筛分素数的倍数.一旦我们在第一段中划掉所有筛分质数的倍数,我们就在筛子阵列上迭代并打印出(或计数)质数.
为了筛选下一个段,我们重置了筛子阵列,并通过segment_size增加了较低的偏移量.然后我们再次开始交叉倍数,对于每个筛分素数,我们从下一个数组中检索筛分指数,然后我们从那里开始交叉倍数...
分段筛的操作与常规筛相同,因此大O时间复杂度不变.不同之处在于使用内存.如果筛子足够小以适合记忆,则没有区别.随着筛子尺寸的增加,参考局部成为一个因素,因此筛分过程减慢.在极端情况下,如果筛网不适合内存并且必须分页到磁盘,则筛分过程将变得非常慢.分段筛使记忆尺寸保持恒定,并且可能很小,因此筛的所有通道都是局部的,因此很快.
即使筛子完全适合 RAM，访问的位置仍然有很大的不同。C++ 实现的只有几率的 Eratosthenes 需要将近半分钟来筛选前 2^32 个数字；同样的实现在 256 KB 的小段（2 ^ 21 位，代表 2 ^ 22 个数字）中初始化相同的筛子，在我老化的 Nehalem 上只需要 8.5 秒，它的 256 KB L2 缓存。
在较小的缓存友好段中筛分的加速在该范围的较高区域中会降低，因为筛子每次都必须迭代所有因素直到 sqrt(n)，而不管该段有多大或多小。这对于接近 2^64 的段最为显着，其中小因子包含 203,280,221 个素数（即完整的 32 位筛）。
不过，分段操作仍然胜过完全筛分。您可以筛选接近 2^64 的片段，以每秒数百万个素数、较低区域每秒数千万个素数的速度进行筛选。那是计算素数，而不是原始数字矿石。超过 2^32 左右的全筛是不实用的，即使你有大量的记忆。