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

在试验除法算法中，确定数字ѭ0是否为质数可能需要做的最多工作是测试素数的可除性，直到约1ѭ。 当

n

是素数或几乎相同大小的两个素数的乘积（包括素数的平方）时，会遇到最坏的情况。如果

n

具有两个以上的素数或两个大小相差很大的素数，它们中的至少一个比

sqrt(n)

小得多，所以即使是所有这些数字所需要的累加功（构成了直到

N

，对于足够大的

N

而言，是相对微不足道的，我将忽略这一点，并以虚构数来确定复合数而无需做任何工作（两个近似相等的素数的乘积数很少，因此尽管它们各自花费高达大小相似的素数，总共可忽略不计）。 那么，对ѭ5以下的素数进行测试需要做多少工作？ 根据素数定理，素数

<= n

（对于

n

足够大）大约为

n/log n

（it11ѭ）。相反，这意味着第k个素数（对于k来说不会太小）约为

k*log k

（+低阶项）。 因此，测试第k个素数需要先除以

pi(sqrt(p_k))

，约

2*sqrt(k/log k)

的素数。将for15的总和得出大约

4/3*N^(3/2)/(log N)^2

的总和。因此，通过忽略组合，我们发现通过试算（仅使用质数）找到不超过

N

的质数为

Omega(N^1.5 / (log N)^2)

。对复合材料的进一步分析显示，它为'19ѭ。使用轮子可以减少常数因子，但不会改变复杂性。 另一方面，在筛子中，每种复合物以至少一个质数的倍数被划掉。取决于您是在ѭ20还是在21 crossing开始相交，复合材料被剔除的次数会多次，因为它具有不同的素因数或不同的素因数

<= sqrt(n)

。由于任何数字最多具有一个超过

sqrt(n)

的素数，因此相差并不大，因此对复杂度没有影响，但是很多数字中只有两个素数（或者三个具有大于

sqrt(n)

的素数），因此，它在运行时间上有明显的不同。无论如何，数字

n > 0

仅有很少的不同素数，一个简单的估计表明，不同素数的数量以

lg n

（以2为底的对数）为界，所以过筛数的上限是

N*lg N

。 。 通过不计算每个复合物被抵消的频率，而是计算每个素数的多少倍被抵消，就像IVlad所做的那样，人们很容易发现交叉的数量实际上是28。同样，使用轮子不会改变复杂性，但会减少常数因子。但是，这里的影响比试用部门更大，因此至少应该跳过偶数操作（除了减少工作量之外，还减少了存储大小，因此提高了缓存的位置）。 因此，即使不考虑除法比加法和乘法更昂贵，我们也会看到筛子所需的操作数比试除法所需的操作数小得多（如果限制不是太小）。 总结： 试算法通过分割素数来完成无效的工作，而筛子则通过反复划开合成物来进行无效的工作。质数相对较少，但复合数很多，因此人们可能会以为试验部门浪费更少的工作。 但是：复合材料只有很少几个不同的素数因子，而低于ѭ29的素数却很多。     

在幼稚的方法中，对检查素数的每个数字number31ѭ进行

O(sqrt(num))

运算。这总共是32英镑。 在筛分法中，对于从1到

n

的每个未标记数字，在标记

2

的倍数时进行

n / 2

运算，在标记

3

的倍数时标记

n / 3

，在标记

5

的倍数时标记

n / 5

。这是

n*(1/2 + 1/3 + 1/5 + 1/7 + ...)

，即

O(n log log n)

。看到这里的结果。 因此，渐近复杂度就不一样了，就像您说的那样。即使是天真的筛子也会很快击败天真的素数生成方法。筛子的优化版本可以获得更快的速度，但是大哦保持不变。 两者并不像您所说的一样。对于每个数字，您将在幼稚素数生成算法中以相同的素数

2, 3, 5, 7, ...

检查除数。随着您的前进，您会用相同的数字序列检查可除性（当您接近

n

时，您会越来越多地检查它的可逆性）。对于筛子，接近ѭ0时，检查会越来越少。首先，您以

2

递增，然后以

3

递增，然后以

5

递增，依此类推。这将达到

n

并停止得更快。     

因为使用sieve方法，您可以在运行质数到达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)

。     

本文介绍：http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf 我认为即使没有Haskell知识，它也很容易阅读。     

第一个区别是除法比加法要昂贵得多。即使每个数字都被“标记”了几次，与“哑”算法所需的大量除法相比，它也是微不足道的。     

Eratosthenes的一个“天真”筛将多次标记非质数。 但是，如果您将数字放在链表上，并且删除的数字是整数倍（您仍然需要遍历列表的其余部分），那么在找到素数之后要做的工作总是比找到素数之前要少。 。     

http://en.wikipedia.org/wiki/Prime_number#Number_of_prime_numbers_below_a_given_number \“ dumb \”算法对每个素数执行

i/log(i) ~= N/log(N)

实算法对每个素数都执行

N/i ~= 1

乘以大约55个素数。