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

对于优化后的埃氏筛法：

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)\)，和优化前的复杂度一致。