$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

算法1 埃氏筛法

$O(n \log \log n)$

每次扫到一个还没有被标记的数，它就是质数。
然后标记这个质数的所有倍数。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 15;
int n, ans = 0;
bool st[N];
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        if (st[i]) continue;
        ans++;
        for (int j = i + i; j <= n; j += i) st[j] = 1;
    }
    printf("%d\n", ans);
    return 0;
}

算法2 线性筛法

$O(n)$

仍然是扫到一个未被标记的，它就是质数。
否则，这个算法的思路是：每个合数只被它最小的质因子筛掉。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 15;
int n, p[N], tot = 0;
bool st[N];
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        if (!st[i]) p[++tot] = i;
        for (int j = 1; j <= tot && i * p[j] <= n; j++) {   //只筛 <= n 的合数
            st[i * p[j]] = 1;
            if (i % p[j] == 0) break;
            /*
            若 i % p[j] == 0，则后面的 i * p[k]（k > j） 由于 i 这一项包含 p[j]，一定被筛过了
            要保证每个数只被最小质因子筛掉，才能保证时间复杂度是线性的。
            */
        }
    }
    printf("%d\n", tot);
}