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; // 返回值表示程序正常结束
}