为什么Eratosthenes的Sieve比简单的"哑"算法更有效？

Question

如果你需要从1到N生成素数,那么"愚蠢"的方法就是迭代从2到N的所有数字并检查这些数字是否可以被到目前为止找到的任何素数除以小于有问题的数字的平方根.

在我看来,Eratosthenes的筛子做了同样的事情,除了其他方式 - 当它找到一个素数N时,它标记所有N的倍数的数字.

但是,当你找到N时是否标记X,或者你检查X是否可以被N除可,基本的复杂性,大O保持不变.你仍然按照数字对进行一次恒定时间操作.事实上,愚蠢的算法一旦找到一个素数就会中断,但是Eratosthenes的筛子会多次标记每个数字 - 一次对于每个素数它都可以被分割.对于除素数之外的每个数字,这是最少两倍的操作.

我在这里误解了什么吗？

Answer 1

在试验分割算法中,确定数字是否n为素数可能需要的大部分工作是通过素数来测试可分性sqrt(n).

当n一个素数或两个几乎相同大小的素数(包括素数的正方形)的乘积时,就会遇到最坏的情况.如果n有两个以上的素因子,或者两个不同大小的素数因子,至少有一个因素要小得多sqrt(n),所以即使是所有这些数字所需的累积工作量(构成绝大多数数字的因素N,足够大N)是相对无关紧要的,我将忽略这一点并使用虚构,即复合数字是在没有做任何工作的情况下确定的(两个近似相等素数的乘积在数量上很少,所以尽管它们单独地花费了相似的素数大小,总共这是一个可以忽略不计的工作量).

那么,对素数的测试需要做多少工作N？

根据素数定理,素数的数量<= n(n足够大),约为n/log n(它的n/log n + lower order terms).相反,这意味着第k个素数(对于k不太小)关于k*log k(+低阶项).

因此,测试第k个素数需要试验除以pi(sqrt(p_k))近似2*sqrt(k/log k)素数.总结一下,k <= pi(N) ~ N/log N产量大致4/3*N^(3/2)/(log N)^2为总和.因此,通过忽略复合材料,我们发现N通过试验分割(仅使用素数)找到素数是Omega(N^1.5 / (log N)^2).对复合材料的更深入分析表明它是Theta(N^1.5 / (log N)^2).使用滚轮减少了常数因素,但不会改变复杂性.

另一方面,在筛子中,每种复合物作为至少一种撇号的倍数被划掉.根据您是否开始穿越送行2*p或者p*p,复合材料被划掉了很多次,因为它具有鲜明的首要因素或不同的素因子<= sqrt(n).由于任何数字最多只有一个素数因子超过sqrt(n),差异不是很大,它对复杂性没有影响,但是有很多数字只有两个素数因子(或者三个比一个更大sqrt(n)),因此它使得运行时间明显不同.无论如何,一个数字n > 0只有很少的不同素数因子,一个简单的估计表明不同素数因子的数量受lg n(基数2对数)的限制,所以筛子的交叉数量的上限是N*lg N.

通过计算每个复合材料被剔除的频率,但是每个撇子的多少次被划掉,正如IVlad已经做过的那样,人们很容易发现交叉的数量实际上就是这样Theta(N*log log N).同样,使用车轮不会改变复杂性,但会降低常数因素.但是,这里它的影响力比试验分区要大,所以至少应该跳过平均值(除了减少工作量,它还减少了存储空间,因此改善了缓存局部性).

因此,即使不考虑该划分比加法和乘法更昂贵,我们也看到筛子所需的操作次数远小于试验所需的操作次数(如果限制不是太小).

总结:
试验部门通过划分素数来完成徒劳的工作,筛子通过反复交叉复合材料来完成徒劳的工作.有相对较少的素数,但许多复合材料,所以人们可能会想到试验师浪费较少的工作.
但是:复合材料只有很少的不同的素因子,而下面有许多素数sqrt(p).

Answer 2

在天真的方法中,您O(sqrt(num))为num检查素数的每个数字执行操作.这是O(n*sqrt(n))总的.

在筛选方法中,对于从1到1的每个未标记的数字,当标记那些时,当标记那些时,n你做n / 2标记的多次操作.这就是.请看这里的结果.2n / 33n / 55n*(1/2 + 1/3 + 1/5 + 1/7 + ...)O(n log log n)

所以渐近的复杂性与你所说的不一样.即使是一个天真的筛子也会很快击败天真的素数法.筛网的优化版本可以更快,但大哦保持不变.

这两个并不像你说的那样.对于每个数字,您将2, 3, 5, 7, ...在朴素素数生成算法中通过相同的素数检查可分性.随着您的进步,您可以通过相同的数字系列检查可分性(当您接近时,您会越来越多地检查n).对于筛子,当你接近时,你会越来越少地检查n.首先检查增量2,然后检查3,然后5等等.这将n更快地击中和停止.

Answer 3

因为使用筛选方法,当运行的素数到达N的平方根时,停止标记正在运行的素数的多个.

比如,你想找到不到一百万的所有素数.

首先设置一个数组

for i = 2 to 1000000
  primetest[i] = true

然后你迭代

for j=2 to 1000         <--- 1000 is the square root of 10000000
  if primetest[j]                                    <--- if j is prime
    ---mark all multiples of j (except j itself) as "not a prime"
    for k = j^2 to 1000000 step j
      primetest[k] = false

您不必在1000之后检查j,因为j*j将超过一百万.并且你从j*j开始(你不必将j的倍数标记为小于j ^ 2,因为它们已被标记为先前找到的较小的素数的倍数)

所以,最后你完成了1000次循环,而if部分仅用于那些作为素数的j.

第二个原因是,用筛子,你只做乘法,而不是除法.如果你聪明地做,你只做加法,甚至不是乘法.

分裂的复杂性大于加法.通常的划分方式有O(n^2)复杂性,而加法则有O(n).

Answer 4

本文解释:http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

我认为即使没有Haskell知识它也很可读.