素数筛法的复杂度

zhiqiangMarch 30, 2008 计算机科学

Xie Xie给我看了一个链接性能调优--永远超乎想象，里面提到了素数筛法的复杂度，作者用实验发现此筛法是线形的。

所谓素数筛法就是那个求小于n的所有素数最简单的算法：

bool* prime(int n) {
  bool *p = new bool[n];
  memset(p, 0, sizeof p);
  for (int i = 2; i < n; i++)
    if (!p[i])
      for (int j = 2*i; j < n; j+=i)
        p[j] = true;
  return p;
}

此算法复杂度实际为 $O(\sum_{p<n}n/p) = O(n\log\log n)$ 。在可以测试的范围内，的确是接近线形的，虽然实际上不是。下面是如何估计 $\sum\frac1p$ :

$\begin{eqnarray}\log\log\infty&=&\ln \left( \sum_{n=1}^\infty \frac{1}{n}\right) = \ln \left( \prod_{p} \frac{1}{1-p^{-1}}\right) = \sum_{p} \ln \left( \frac{1}{1-p^{-1}}\right) = \sum_{p} - \ln(1-p^{-1}) \\&=&\sum_{p} \left( \frac{1}{p} + \frac{1}{2p^2} + \frac{1}{3p^3} + \cdots \right) = \left( \sum_{p}\frac{1}{p} \right) + \sum_{p} \frac{1}{p^2} \left( \frac{1}{2} + \frac{1}{3p} + \frac{1}{4p^2} + \cdots \right)\\&=& \sum_{p} \left( \frac{1}{p} + \frac{1}{2p^2} + \frac{1}{3p^3} + \cdots \right) = \left( \sum_{p}\frac{1}{p} \right) + \sum_{p} \frac{1}{p^2} \left( \frac{1}{2} + \frac{1}{3p} + \frac{1}{4p^2} + \cdots \right)\\&<& \left( \sum_{p}\frac{1}{p} \right) + \sum_{p} \frac{1}{p^2} \left( 1 + \frac{1}{p} + \frac{1}{p^2} + \cdots \right) = \left( \sum_{p} \frac{1}{p} \right) + \left( \sum_{p} \frac{1}{p(p-1)} \right)\\&=& \left( \sum_{p} \frac{1}{p} \right) + C\end{eqnarray}$

更精确的，

$\sum_{p<n}\frac1p = \log\log n+\Theta(1)$

注意此估计可直接得出素数有无穷多个。

查看更多关于复杂度, 复杂性, 算法, 素数的内容。

你可能感兴趣的

At 2008.03.31 10:05, sog.white said:

求素数有没有效率比较高的算法？

上次我面试，还遇到让我写这个算法，我想了半天，最后还是写了这个反复相乘的法子。

最后估计了一下这个的时间复杂性，感到很没有面子。

[Reply]
At 2008.03.31 12:36, Cody said:

我土。最后一句是为啥？由这个算法复杂度怎么得出素数有无穷多个？

[Reply]
- At 2008.03.31 15:56, sog.white said:
  
  It's just joke
  
  倒置举证法
  
  [Reply]
At 2008.03.31 19:47, fcicq said:

for (int i = 2; i < n; i++)
替换为
s = sqrt(n) + 1;
for (int i = 2; i < s; i++)

想想为什么?

[Reply]
At 2008.03.31 20:04, zhiqiang said:

@sog white: 如果需要求出小于n的所有素数，这个算法在数量级上应该无法突破了，但细节上还可以优化很多，就如fcicq所说，加快个一两倍的速度都是可能的。

@cody: 素数的倒数和都是无穷大了，素数当然更是无穷多个了。

[Reply]
At 2008.04.01 14:46, rex said:

恰巧，我刚写了一篇博客文章，分析“使用正则式运行质数、合数判定的内幕”。其中遇到一个问题，即，设有m,n均为非0自然数，是否能够证明，(m+1)*(n+1)全等于所有合数的集合？

原文链接在此。

[Reply]
At 2008.04.05 02:27, rmq said:

for (int j = 2*i; j < n; j+=i)
是不是应该
for (int j = i*i; j < n; j+=i)

[Reply]

« 如何和谐议政

Perfect Shuffle的算法 »

素数筛法的复杂度

查看更多关于复杂度, 复杂性, 算法, 素数的内容。

7条留言

阅微堂