埃氏筛

skystars

我们先来看一道题：给出一个整数n，求2~n中质数的个数，其中n≤1e8。

一开始，我想先从最简单的方法开始讲起。

[C++] 纯文本查看 复制代码

#include <iostream>#include <cstdio>
#include <cmath>
using namespace std;
typedef unsigned uint;
bool IsPrime(uint n) {
    for (uint i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}
int main() {
    uint n;
    cin >> n;
    uint cnt = 0;
    for (uint i = 2; i <= n; i++) {
        if (IsPrime(i)) cnt++;
    }
    cout << cnt;
    return 0;
}

这种方法是最简单的方法，先定义一个函数来判断质数，根据算术基本定理可以得出，我们只需要判断到n的平方根即可，时间复杂度 O(nsqrtn)。

接着，我们来测试一下上面这段代码的运行时间（使用洛谷作为评测工具）。





可以发现，我们只通过了5个测试点，运行速度太慢了

当然，我们可以在此基础上继续优化：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
using namespace std;
typedef unsigned uint;
bool IsPrime(uint n)
{
    if (n <= 1) return false;
    if (n == 2 || n == 3 || n == 5 || n == 7) return true;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return false;
    for (uint i = 7; i * i <= n; i += 30) {
        if (n % i == 0 || n % (i + 4) == 0 || n % (i + 6) == 0 || n % (i + 10) == 0 || n % (i + 12) == 0 || n % (i + 16) == 0 || n % (i + 22) == 0 || n % (i + 24) == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    uint n;
    cin >> n;
    uint cnt = 0;
    if (n >= 2) cnt++;
    for (uint i = 3; i <= n; i += 2) {
        if (IsPrime(i)) cnt++;
    }
    cout << cnt;
    return 0;
}

只对2和大于2的奇数进行判断，大大加快了运行速度，评测结果如图所示：



我们会发现，只有两个测试点没通过了，怎么办？接下来我们要介绍一种方法——埃氏筛，代码如下：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <bitset>
using namespace std;
typedef unsigned uint;
bool b[100000005];
int main() {
    uint n;
    cin >> n;
    uint cnt = 0, sqr = sqrt(n);
    for (uint i = 2; i <= n; i++) {
        if (!b[i]) { // 是质数（未被标记）
            cnt++;
            if (i <= sqr) { // 只需要筛到n的平方根即可
                for (uint j = i * i; j <= n; j += i) { // 将i的倍数筛去
                    b[j] = true; // 标记
                }
            }
        }
    }
    cout << cnt;
    return 0;
}

埃氏筛是将质数的倍数进行标记，未标记的就一定是质数，为什么这里的j是从i*i开始循环呢？因为i*i之前i的倍数都已经被标记过了，时间复杂度为 O(nloglogn)。

我们可以结合动图来理解埃氏筛：



测试结果如下：



因为数据太大（1e8），仍然有一个测试点超时

我们可以仅对奇数进行筛除，优化运行速度，这样就能够通过本题了：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <bitset>
using namespace std;
typedef unsigned uint;
bool b[100000005];
int main() {
    uint n;
    cin >> n;
    uint cnt = 0, sqr = sqrt(n);
    if (n >= 2) cnt++;
    for (int i = 3; i <= n; i += 2) {
        if (!b[i]) { // 是质数（未被标记）
            cnt++;
            if (i <= sqr) { // 只需要筛到n的平方根即可
                for (int j = i * i; j <= n; j += i * 2) { // 将i的奇数倍数筛去
                    b[j] = true; // 标记
                }
            }
        }
    }
    cout << cnt;
    return 0;
}

测试点信息如下：

skystars

我们也可以像第二段代码一样，对埃氏筛进行进一步的优化：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <bitset>
using namespace std;
int n, cnt, sqr, t;
bool b[100000005];

inline void sieve(int i) {
    if (!b[i]) { // 是质数（未被标记）
        cnt++;
        if (i <= sqr) { // 只需要筛到n的平方根即可
            for (int j = i * i; j <= n; j += i * 2) { // 将i的奇数倍数筛去
                b[j] = true; // 标记
            }
        }
    }
}
int main() {
    scanf("%d", &n);
    if (n <= 1) { // 特判
        putchar('0');
        return 0;
    }
    if (n >= 2) cnt++;
    if (n >= 3) cnt++;
    if (n >= 5) cnt++;
    sqr = sqrt(n);
    t = n - 30;
    register int i;
    for (i = 7; i <= t; i += 30) {
        sieve(i);
        sieve(i + 4);
        sieve(i + 6);
        sieve(i + 10);
        sieve(i + 12);
        sieve(i + 16);
        sieve(i + 22);
        sieve(i + 24);
    }
    if (i <= n) {
        sieve(i);
        if (i + 4 <= n) sieve(i + 4);
        if (i + 6 <= n) sieve(i + 6);
        if (i + 10 <= n) sieve(i + 10);
        if (i + 12 <= n) sieve(i + 12);
        if (i + 16 <= n) sieve(i + 16);
        if (i + 22 <= n) sieve(i + 22);
        if (i + 24 <= n) sieve(i + 24);
    }
    printf("%d", cnt);
    return 0;
}

测试结果如下：