如何分割提高埃拉托色尼的筛的运行时间？

问题描述

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

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

解决方案

一个分段筛做所有相同的操作常规筛子，所以大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)

解决方案

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.

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