线性筛

线性筛

1. 素数

如何判断一个数是不是 素数?

bool isPrime(a) {
    if (a < 2) return false;
    for (int i = 2; i * i <= a; ++i)
        if (a % i == 0) return 0;
    return true;
}

2. 素数筛法

如果我们想要知道小于等于 $n$ 有多少个素数呢?

2.1 暴力思路

一个很自然的想法就是: 对于小于等于 $n$ 的每一个数进行素数判断, 并统计素数个数, 但显然达不到最优的时间复杂度

2.2 埃拉托斯特尼筛法 $O(n\log {\log {n}})$

对于一个数 $x(x > 1)$, 那么它的 $x(x > 1)$ 倍一定是 合数, 就可以避免很多不必要的检测

具体做法: 从小到大考虑每一个数, 并将该数的所有倍数都标记为合数, 那么最后没有被标记的就是素数了

// C++ Version
int Eratosthenes(int n) {
    int p = 0;

    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            prime[p++] = i;  // prime[p]是i, 后置自增运算代表当前素数数量
            if ((long long)i * i <= n)
            {
                for (int j = i + i; j <= n; j += i)
                {
                    // 因为从 2 到 i - 1 的倍数我们之前筛过了, 这里直接从 i 的倍数开始, 提高了运行速度
                    is_prime[j] = 0;  // 是i的倍数的均不是素数
                } 
            }
        }
    }
    return p;
}

2.3 线性筛法

埃氏筛法仍然有优化空间

why ?

因为埃氏筛法会将同一个 合数 多次标记(例如: 10 同时被 2 和 5 标记)

那么, 能否省去这些重复步骤呢? 如果可以, 又该如何省去?

// C++ Version
int Euler(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            pri[cnt++] = i;
        }
        for (int j = 0; j < cnt; ++j) {
            if (1ll * i * pri[j] >= MAXN) break;
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                // i % pri[j] == 0
                // 换言之，i 之前被 pri[j] 筛过了
                // 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定也是
                // pri[j] 的倍数 它们都被筛过了，就不需要再筛了，所以这里直接 break
                // 掉就好了
                break;
            }
        }
    }
}