素数筛法的复杂度

作者: , 共 2708 字 , 共阅读 0

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)$$

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

但是纯O(n)的算法也不是没有,只不过需要增加辅助空间保存质数列表:

bool* prime(int n) {
    bool *isp = new bool[n];
    bool *p = new p(int(2*n/log(n)+20));
    memset(isp, 0, sizeof isp);
    memset(p, 0, sizeof p);
    int np = 0;
    for (int i = 2; i < n; i++) {
        if (~isp(i)) p(np++) = i;
        for (int j = 0; j < pn && p[j]*i < n; j++) {
            isp[p[j]*i] = 1;
            if(i%p[j] == 0) break;
        }
    }
    delete p;
    return isp;
}

这个算法的关键在于 if(i%pr[j] == 0) break;。它使得任何一个合数,只被它最小的质因数标记过一次。所以整个算法是线性的。但考虑到log(log(100000000))还不到 3 ,故这个线性算法其实也只有理论上的价值罢了。

Q. E. D.

类似文章:
编程 » C++
假设在 C++里有一个数据结构:
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本On the graph isomorphism problem
递归算法的复杂度通常很难衡量,一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大,如果我们可以保存每次子递归的结果的话,递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。
本科时有同学扫雷最快可以在 60 多秒完成高级难度,让我这种最快 130 秒的人非常惭愧,当时就想着编一个全自动的扫雷程序,不过一直也没写。今天才知道,原来扫雷问题是NP 完全的...
相似度: 0.064
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。
相似度: 0.064
这个问题有许多不同形式的阐述方式和变种,应用范围也很广。下面应该是比较吸引人和简单的那种,来自姚期智教授的理论计算机( I )的授课内容——我是其助教之一。
碎碎念 » GFW, 新宋, 西藏
以下是样本,绝对安全(不是说观点,而是指语言形式):
珍爱生命,远离政治。我们继续讨论算法。