[数据结构与算法]【算法/数论】埃拉托斯特尼筛法时间复杂度的证明

一、埃拉托斯特尼筛法简介

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种能快速求出$1～n$内所有质数的方法。埃拉托斯特尼就是用很聪明的方法测出地球周长的那个希腊人。算法的过程是：枚举$1～n$中的每个数$i$，如果它没有被前面的数标记过，则$i$为质数，此时标记它的$2,3,4?$倍为合数。C++代码如下：

bool isprime[MAXN]; // isprime[i]表示i是否为质数
int prime[MAXN]; // 筛出的质数列表
int cnt; // 质数个数
int n; // 上界

void Eratosthenes() // 埃拉托斯特尼筛法：1~n
{
    memset(isprime, true, sizeof(isprime));
    // 先全部设为质数
    for(int i = 2; i <= n; ++i)
    // 枚举i从2到n
    {
        if(isprime[i]) // 没有被标记为合数
        {
            prime[++cnt] = i; // 加入质数列表
            for(int j = i + i; j <= n; j += i)
            // j取2i, 3i, 4i, ...一直到n
                isprime[j] = false;
                // 标记i的倍数为合数
        }
    }
    // 现在prime[1] = 2, prime[2] = 3, prime[3] = 5,
    // prime[4] = 7, prime[5] = 11, ...
}

可以看出，对于每个质数$i$，我们都要将$i$的倍数标记为合数。而$i$的倍数在$1～n$内共有$?\frac{n}{i}?$个，所以在忽略线性复杂度的外层循环的情况下，算法需要进行的运算次数就是$$?\frac{n}{2}?+?\frac{n}{3}?+?\frac{n}{5}?+?\frac{n}{7}?+?+?\frac{n}{p_m}?$$其中$p_m$是$n$以内最大的质数。为了简化计算，将取整符号去掉，就是$$n\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+?+\frac{1}{p_m}\right)$$这里所做的的近似误差不超过$O(n)$，对结果没有影响。我们知道，埃拉托斯特尼筛法的复杂度是$O(n\log (\log (n)))$，令$h(n)=\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+?+\frac{1}{p_m}=\sum _{p\in \text{Prime},p\le n}\frac{1}{p}$，则我们要证明的就是$h(n)=O(\log (\log (n)))$。

二、黎曼$\zeta$函数与欧拉乘积公式

要证明上面这个结论，就不得不介绍以下黎曼$\zeta$函数。黎曼$\zeta$函数的定义是$$\zeta (s)=\sum _{n=1}^{\infty }{n}^{?s}=\frac{1}{1^s}+\frac{1}{2^s}+\frac{1}{3^s}+\frac{1}{4^2}+?①$$这里用$s$而不是$x$作为变量的字母是因为自变量是复数。例如，当$s=2$时有$$\zeta (2)=1+\frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+?=\frac{{\pi }^2}{6}$$另外，黎曼猜想就是说$\zeta (s)$的零点要么是负偶数，要么是实部为$\frac{1}{2}$的复数。

下面介绍欧拉乘积公式。在$\zeta (s)$两边同时乘以$\frac{1}{2^s}$得$$\frac{1}{2^s}\zeta (s)=\frac{1}{1^s?2^s}+\frac{1}{2^s?2^s}+\frac{1}{3^s?2^s}+\frac{1}{4^s?2^s}+?=\frac{1}{2^s}+\frac{1}{4^s}+\frac{1}{6^s}+\frac{1}{8^s}+?②$$$①?②$，偶数项消掉，留下奇数项得$$(1?\frac{1}{2^s})\zeta (s)=\frac{1}{1^s}+\frac{1}{3^s}+\frac{1}{5^s}+\frac{1}{7^s}+?③$$在$③$两边同时乘以$\frac{1}{3^s}$得$$\frac{1}{3^s}(1?\frac{1}{2^s})\zeta (s)=\frac{1}{3^s}+\frac{1}{9^s}+\frac{1}{15^s}+\frac{1}{21^s}+?④$$$③?④$，消去$3$的倍数项得$$(1?\frac{1}{3^s})(1?\frac{1}{2^s})\zeta (s)=\frac{1}{1^s}+\frac{1}{5^s}+\frac{1}{7^s}+\frac{1}{13^s}+?⑤$$不断重复这种操作，在原式两端乘上$\frac{1}{p^s}$（$p$为某个质数）再用原式减掉，就可以在右边消去这个质数的倍数。当所有质数都经历过这种操作后，右边就只剩下$1$，所以得到$$(1?\frac{1}{2^s})(1?\frac{1}{3^s})(1?\frac{1}{5^s})(1?\frac{1}{7^s})(1?\frac{1}{11^s})?\zeta (s)=1$$即$$\zeta (s)=\prod _{p\in \text{Prime}}\frac{1}{1?\frac{1}{p^s}}$$这就是欧拉乘积公式。

三、问题求解

在欧拉乘积公式中代入$s=1$得$$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+?=\prod _{p\in \text{Prime}}\frac{1}{1?\frac{1}{p}}$$两边取对数得$$\ln \left(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+?\right)=?\sum _{p\in \text{Prime}}\ln \left(1?\frac{1}{p}\right)⑥$$考虑将函数$f(x)=\ln (1?x)$展开成麦克劳林级数$$\ln (1?x)=?x?\frac{x^2}{2}?\frac{x^3}{3}???\frac{x^n}{n}??=?\sum _{k=1}^{\infty }\frac{x^k}{k}$$令$x=\frac{1}{p}$，将展开式代入$⑥$式右边得$$\ln \left(\sum _{k=1}^{\infty }\frac{1}{k}\right)=\sum _{p\in \text{Prime}}\sum _{k=1}^{\infty }\frac{1}{k{p}^k}⑦$$回顾一下我们要证明的结论：$$h(n)=\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+?+\frac{1}{p_m}=O(\log (\log (n)))$$要证$h(n)=O(\log (\log (n)))$，只需证$$\underset{n\to \infty }{\lim }\frac{h(n)}{\ln (\ln (n))}=1$$我们知道，$\sum _{k=1}^n\frac{1}{k}=\ln n+O(1)$，亦即$?M>0$，使得$?n\in {\mathbb{N}}^{+}$，都有$\sum _{k=1}^n\frac{1}{k}\le \ln n+M$。设$\delta =\ln n?\sum _{k=1}^n\frac{1}{k}$，则$?n\in {\mathbb{N}}^{+}$有$\delta <M$。由拉格朗日中值定理知，$\ln (\ln n+\delta )?\ln (\ln n)=\frac{1}{\xi }\delta$，其中$\xi \in (\ln n,\ln n+\delta )$。而$\delta \le M$，$\xi >n\ge 1$，所以有$$\ln (\ln n+\delta )=\ln (\ln n)+\frac{\delta }{\xi }\le \ln (\ln n)+M$$注意到$\sum _{k=1}^n\frac{1}{k}=\ln n+\delta$，故$$\underset{n\to \infty }{\lim }\frac{\ln \left(\sum _{k=1}^n\frac{1}{k}\right)}{\ln (\ln n)}=1⑧$$令$z(n)=\sum _{p\in \text{Prime},p\le n}\sum _{k=1}^{\infty }\frac{1}{k{p}^k}$，将$⑦$表示为极限形式：$$\underset{n\to \infty }{\lim }\ln \left(\sum _{k=1}^{\infty }\frac{1}{k}\right)=\underset{n\to \infty }{\lim }z(n)$$再由$⑧$，知$$\underset{n\to \infty }{\lim }\frac{z(n)}{\ln (\ln n)}=1$$所以只需证$$\underset{n\to \infty }{\lim }\frac{h(n)}{z(n)}=1$$我们采用夹逼准则。设等式左边的值为$c$。
(1) 对分母进行缩小，注意到$z(n)=\sum _{p\in \text{Prime},p\le n}\sum _{k=1}^{\infty }\frac{1}{k{p}^k}=\left(\sum _{p\in \text{Prime},p\le n}\frac{1}{p}\right)+\sum _{k=2}^{\infty }\frac{1}{k}\left(\sum _{p\in \text{Prime},p\le n}\frac{1}{p^k}\right)=h(n)+\sum _{k=2}^{\infty }\frac{1}{k}\left(\sum _{p\in \text{Prime},p\le n}\frac{1}{p^k}\right)$，故$z(n)\ge h(n)$，$c\le \underset{n\to \infty }{\lim }\frac{h(n)}{h(n)}=1$。
(2) 对分母进行放大，注意到$\frac{1}{k{p}^k}\le \frac{1}{p^k}$，且$\sum _{k=1}^{\infty }\frac{1}{p^k}=\frac{1}{p?1}$，有$z(n)\le \sum _{p\in \text{Prime},p\le n}\sum _{k=1}^{\infty }\frac{1}{p^k}=\sum _{p\in \text{Prime},p\le n}\frac{1}{p?1}$，因此$$c\ge \underset{n\to \infty }{\lim }\frac{h(n)}{\sum _{p\in \text{Prime},p\le n}\frac{1}{p?1}}$$容易验证$\frac{1}{p?1}=\frac{1}{p}+\frac{1}{p(p?1)}$，代入得$$c\ge \underset{n\to \infty }{\lim }\frac{h(n)}{\sum _{p\in \text{Prime},p\le n}\frac{1}{p}+\sum _{p\in \text{Prime},p\le n}\frac{1}{p(p?1)}}=\underset{n\to \infty }{\lim }\frac{h(n)}{h(n)+\sum _{p\in \text{Prime},p\le n}\frac{1}{p(p?1)}}=\underset{n\to \infty }{\lim }\frac{1}{1+\frac{\sum _{p\in \text{Prime},p\le n}\frac{1}{p(p?1)}}{h(n)}}$$其中$$\underset{n\to \infty }{\lim }\frac{\sum _{p\in \text{Prime},p\le n}\frac{1}{p(p?1)}}{h(n)}\le \underset{n\to \infty }{\lim }\frac{\sum _{p\in \text{Prime},p\le n}\frac{1}{p\frac{p}{2}}}{h(n)}=\frac{1}{2}\underset{n\to \infty }{\lim }\frac{\sum _{p\in \text{Prime},p\le n}\frac{1}{p^2}}{h(n)}\le \underset{n\to \infty }{\lim }\frac{\sum _{k=1}^n\frac{1}{k^2}}{h(n)}$$其中分母的和式是收敛的：$\sum _{k=1}^{\infty }\frac{1}{k^2}=\zeta (2)=\frac{{\pi }^2}{6}$，那么我们只需讨论$h(n)$的收敛性。
首先，$\underset{n\to \infty }{\lim }z(n)=\sum _{p\in \text{Prime},p\le n}\sum _{k=1}^{\infty }\frac{1}{k{p}^k}$一定是发散的，因为$\underset{n\to \infty }{\lim }\ln (\ln n)=+\infty$，而$\underset{n\to \infty }{\lim }\frac{z(n)}{\ln (\ln n)}=1$。又$c\ge \underset{n\to \infty }{\lim }\frac{h(n)}{\sum _{p\in \text{Prime},p\le n}\frac{2}{p}}=\frac{1}{2}$，因此$h(n)$与$\sum _{p\in \text{Prime},p\le n}\sum _{k=1}^{\infty }\frac{1}{k{p}^k}$敛散性相同，即$h(n)$发散。因此$\underset{n\to \infty }{\lim }\frac{\sum _{k=1}^n\frac{1}{k^2}}{h(n)}=0$，$c\ge 1$。
综上，由夹逼准则知$c=1$。
因此，$\underset{n\to \infty }{\lim }\frac{h(n)}{\ln (\ln n)}=1$，$h(n)=\Theta (\ln (\ln n))$，埃拉托斯特尼筛法的时间复杂度为$O(n\log (\log (n)))$。