优化埃氏筛的时间复杂度分析

Posted on Edited on Views:

对于优化后的埃氏筛法：

bool v[N];

void sieve(int n) {
    memset(v, 0, sizeof(v));
    for (int i = 2; i <= n; i++) {
        if (v[i]) continue;
        for (int j = i; j <= n / i; j++)
            v[i * j] = true;
    }
}

简单分析一下它的流程，我们发现当i不是素数的时候内层循环才会执行，而内层循环执行的次数约为\frac{n}{i} - i次，暗示了其实对于i > \sqrt{n}，这个循环也不会被执行，这已经是埃氏筛的一个小优化：即一个数只会被它前半部分的素数筛去，那么总体的时间复杂度就可以表示为：

\begin{aligned} \sum_{素数p \le \sqrt{n}} \left(\frac{n}{p} - p\right) &= \sum_{素数p \le \sqrt{n}} \frac{n}{p} - \sum_{素数p \le \sqrt{n}} p \\ &= n \sum_{素数p \le \sqrt{n}} \frac{1}{p} - \sum_{素数p \le \sqrt{n}} p \end{aligned}
方便起见我们假设\sqrt{n}为整数，这样就可以避免写\left\lfloor \sqrt{n} \right\rfloor，我们先着手估计后半部分，即\sum_{素数p \le \sqrt{n}} p的值，通过计算贡献的办法我们得到：
\sum_{素数p \le \sqrt{n}} p = \sqrt{n}\pi\left(\sqrt{n}\right) - \sum_{i = 2}^{\sqrt{n} - 1}\pi(i)
根据素数定理，我们有\pi(x) \approx \frac{x}{\ln x}，那么我们可以得到：
\begin{aligned} \sqrt{n}\pi\left(\sqrt{n}\right) - \sum_{i = 2}^{\sqrt{n} - 1}\pi(i) &\approx \frac{n}{\ln \sqrt{n}} - \sum_{i = 2}^{\sqrt{n} - 1}\frac{i}{\ln i} \\ &= \frac{2n}{\ln n} - \sum_{i = 2}^{\sqrt{n} - 1}\frac{i}{\ln i} \\ &\approx \frac{2n}{\ln n} - \int_2^{\sqrt{n}}\frac{x}{\ln x}dx \\ &< \frac{2n}{\ln n} - \frac{n}{\ln n} \\ &= O\left(\frac{n}{\ln n}\right) \end{aligned}
对于前半部分，我们有Mertens Theorem指出：
\lim_{n \to \infty} \left( \sum_{素数p \le n}\frac{1}{p} - \ln\ln n - M \right) = 0
其中M \approx 0.2614972128 为Meissel-Mertens’ Constant。

这告诉我们前半部分的复杂度是O\left(n\ln\ln\sqrt{n}\right) = O (n\ln\ln n) 的，因此合并起来，整个算法的复杂度为O\left(n\ln\ln n - \frac{n}{\ln n}\right) = O(n \ln\ln n)，和优化前的复杂度一致。