素数筛

引入

如果我们想要求出小于 n 的所有素数，一个很自然的想法就是从 1 到 n 进行遍历，然后对素数进行记录，但这样的话时间复杂度为 \(O(n^{\frac{3}{2}})\) ，当 n 足够大的时候这个算法是较慢的，有没有更高效的算法呢？

接下来我们介绍最常见的两种素数筛，以 Leetcode 模版题为例：计数质数

埃氏筛

埃氏筛也叫埃拉托斯特尼筛法，考虑任意素数 x ，则 x 的所有倍数都是合数。

class Solution {
public:
    int countPrimes(int n) {
        // 埃式筛
        bool* notPrime = new bool[n]();
        int res = 0;
        for (int i = 2; i < n; i++) {
            if (!notPrime[i]) {
                res++;
                for (long long k = (long long)i * i; k < n; k += i) {
                    // 若 j < i，则 j * i 一定已经被筛过
                    notPrime[k] = true;
                }
            }
        }

        return res;
    }
};

时间复杂度：\(O(n\ loglogn)\)

如果想了解其证明，读者可以自行去 OI Wiki 上看。

尽管埃氏筛法已经有较高的效率，但其仍然无法达到线性时间复杂度，因为有些数存在重复筛除的情况，例如 12，其会被 2，3 分别筛除一次，有没有办法可以避免重复筛除呢？

欧式筛（线性筛）

欧式筛，即 Euler 筛法，其避免了上述的重复筛而造成的时间浪费，真正意义上实现了线性时间复杂度。对于特别大的数据量（\(n > 10^8\)）时适用。

class Solution {
public:
    int countPrimes(int n) {
        if (n < 2) return 0;
        int* primeNum = new int[(int)(1.5 * n / log(n)) + 1];
        // π(n) < 1.5 * n / ln(n) 素数数目的一个粗糙上界
        bool* notPrime = new bool[n]();
        int res = 0;
        for (int i = 2; i < n; i++) {
            if (!notPrime[i]) {
                primeNum[res++] = i;
            }
            for (int j = 0; j < res && i * primeNum[j] < n; j++) {
                notPrime[i * primeNum[j]] = true;
                if (i % primeNum[j] == 0) break;
                // 如果 i 能被 primeNum[j] 整除，则 i 的倍数一定会被 primeNum[j] 的倍数筛除
                // 故此刻不需要继续再筛除，退出循环
            }
        }

        return res;
    }
};

时间复杂度：\(O(n)\)

注意到，欧式筛中被筛除的合数都是被当前记录的最小素数筛除的，所以我们我们也可以同时得到每个数的最小质因数。

案例

HDU - 6954

#include <iostream>
#include <cmath>

#define MAX_NUM 10000005

using i64 = long long;

bool notPrime[MAX_NUM];
i64 ans[MAX_NUM];
int primeNum[MAX_NUM];
int cnt = 0;

int main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    for (int i = 2; i < MAX_NUM; i++) {
        if (!notPrime[i]) {
            ans[i] = ans[i - 1] + 2ll * i;
            primeNum[cnt++] = i;
        }
        else {
            ans[i] = ans[i - 1] + i;
        }
        for (int j = 0; j < cnt && (i64)i * primeNum[j] < MAX_NUM; j++) {
            notPrime[i * primeNum[j]] = true;
            if (i % primeNum[j] == 0) break;
        }
    }

    int numTest;
    std::cin >> numTest;
    int n;
    while (numTest--) {
        std::cin >> n;
        std::cout << ans[n] - 4 << '\n';
    }

    return 0;
}