首页 > 代码库 > 埃拉托色尼筛法的复杂度估计与改进及线性时间筛法简介

埃拉托色尼筛法的复杂度估计与改进及线性时间筛法简介

本文介绍求出1~n内的所有素数的有效算法——埃拉托色尼筛法(the Sieve of Eratosthenes),估计其算法复杂度,并介绍其改进——线性时间筛法。以下内容谢绝转载。                                                                                                                                                                                                                                                                                                                                                                                                        

 

1.埃拉托色尼筛法(the Sieve of Eratosthenes)

埃氏筛法是一种古老的筛选素数的方法,以古希腊数学家埃拉托色尼的名字命名。因其算法简单,容易编写,受到广泛的使用。

算法思想是从1~n中依次删除2的倍数,3的倍数,.......

算法伪码:

用$A[i]$表示$i$是否为素数,是为true,否为false。初始化$A[2 \cdots n]=true$.

for $i=2$ to $\sqrt n$

  if($A[i]$ is true)

    for $j=2$ to $n/i$

      $A[i]$=false;

    end

  end

end

输出:

all $p$ s.t. $A[p]$ is true

 

由于合数$N$一定有不超过$\sqrt N$的质因子,因此外层循环只需循环到$\sqrt n$

 

2.埃氏筛法的复杂度估计

复杂度估计可以如下简单地考虑:外层循环是 $i$ 时,内层循环共执行 $\frac{n}{i}$ 次。因此总的时间消耗为:

$$\sum_{primes \, p\le \sqrt n} \frac{n}{p} = n \sum_{primes \, p \le \sqrt n} \frac{1}{p}$$

根据Mertens‘ 2nd theorem:

$$\lim_{n\to\infty} \sum_{primes \ p \le n}\frac{1}{p} -\ln\ln n =M$$

其中$M$是Meissel-Mertens常数,约为$0.26$

由此可见算法的时间消耗为$\Theta  (n \log \log n)$

 

注:一个小优化

可以将内层循环的从$j=i$而不是$j=2$开始。这是因为一个合数一定在$i$是其最小素因子时所标记过,因此只要考虑$j$比$i$大的情况就可以了.

但是这个优化对复杂度的阶并没有改进。这是因为对于不超过$\frac{1}{2}n^{\frac {1}{4}}$的素因子来说,以上优化只减少了至多一半的操作量

然而上述求和即使把求和上限改成$\frac{1}{2}n^{\frac {1}{4}}$,其阶仍然有$\Omega (n \log \log n)$,因此这只是一个常数级别的优化。

 

3.埃氏筛法的改进——线性时间筛法

从上述分析可以看出,埃氏算法并不是一个线性时间算法。事实上,筛法有一个简单的改进,使得其复杂度降低到线性时间。

 

 

 

 

References:

Mertens‘ 2nd theorem:

http://en.wikipedia.org/wiki/Mertens%27_theorems

埃拉托色尼筛法的复杂度估计与改进及线性时间筛法简介