AcWing 868. 筛质数

https://www.acwing.com/activity/content/problem/content/937/

埃氏筛

#include <iostream>
using namespace std;
const int N = 1e6 + 10; // 定义数组大小
int st[N]; // 定义一个 bool 类型的数组，用于标记每个数是否为质数
int primes[N]; // 定义存储素数的数组
int cnt; // 定义计数器，记录素数个数
int n; // 定义素数上限
void get_primes(){ // 获取素数函数
    for(int i = 2;i<=n;i++){ // 从 2 到 n 枚举每个数
        if(!st[i]){ // 如果当前枚举的数 i 是质数
            primes[cnt++] = i; // 将 i 加入素数数组
            for(int j = i;j<=n;j+=i) st[j] = true; // 将 i 的倍数标记为合数
        }
    }
}
int main(void) {
    cin>>n; // 读入素数上限
    get_primes(); // 获取素数
    cout << cnt << endl; // 输出素数个数
    return 0; // 返回值表示程序正常结束
}