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.
