质数筛-线性筛

核心思想
每一个数只会被其最小的质因子筛一遍

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];  // false 表示质数

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++) {  // 避免爆int
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;

    return 0;
}