57.Acwing基础课第868题-简单-筛质数
题目描述
给定一个正整数 \(n\) ，请你求出 1∼ \(n\) 中质数的个数。
输入格式
共一行，包含一个整数\(n\) 。
输出格式
共一行，包含一个整数，表示 1∼\(n\) 中质数的个数。
输出格式
数据范围
1≤\(n\)≤2×106
输入样例：
8
输出样例：
4
代码：
朴素筛法
// 包含输入输出流头文件，用于 cin 和 cout
#include <iostream>
// 这里没用到，可以省略
#include <algorithm>using namespace std;// 定义数组最大范围，能处理 1e6 以内的质数
const int N = 1000010;// primes[] 存储筛出来的所有质数
// cnt 记录质数的总个数
int primes[N], cnt;
// st[] 是标记数组，st[i] = true 表示 i 是合数，不是质数
bool st[N];// 朴素筛法：筛出 2 ~ n 之间的所有质数
void get_primes(int n)
{// 从 2 开始遍历到 nfor (int i = 2; i <= n; i ++ ){// 如果 i 没有被标记，说明 i 是质数if (!st[i]) primes[cnt ++ ] = i; // 把质数存入 primes 数组，质数数量 +1// 核心：把当前数 i 的所有倍数都标记为合数（非质数）// j 从 i*2 开始，每次加 i，直到 nfor (int j = i + i; j <= n; j += i) st[j] = true; // 标记为合数}
}int main()
{int n;// 输入范围 n，求 2~n 之间有多少个质数cin >> n;// 调用筛法函数get_primes(n);// 输出质数的总个数cout << cnt << endl;return 0;
}
埃氏筛法
// 包含标准输入输出头文件（cin/cout依赖）
#include <iostream>
// 算法库（本代码未直接使用，属于通用模板保留）
#include <algorithm>// 使用std命名空间，避免重复写std::
using namespace std;// 常量定义：N为数组最大长度，1000010适配n≤1e6的场景（可根据需求调整）
const int N= 1000010;// 全局数组/变量（默认初始化为0/false，无需手动清零）
int primes[N]; // primes数组：存储筛选出的所有质数，primes[0]是第一个质数，primes[1]是第二个，依此类推
int cnt; // cnt：记录质数的个数（primes数组的有效长度）
bool st[N]; // st数组：标记是否为合数（st[i]=true → i是合数；st[i]=false → i是质数）// 埃氏筛核心函数：筛选出1~n中的所有质数，存入primes数组，并统计个数cnt
// 核心思想：从小到大枚举数，若当前数是质数，则筛掉它的所有倍数（标记为合数）
void get_primes(int n)
{// 枚举2~n的所有数（1不是质数，无需处理）for (int i = 2; i <= n; i ++ ){// 若st[i]=false，说明i未被标记（是质数）if (st[i]) continue; // 跳过合数，只处理质数primes[cnt ++ ] = i; // 将质数i存入primes数组，同时cnt计数+1// 筛除质数i的所有倍数（从i*2开始，步长i），标记为合数// 原理：质数的所有倍数一定是合数，无需后续重复判断for (int j = i + i; j <= n; j += i)st[j] = true; // 标记j为合数}
}int main()
{int n; // n：输入的上限，要求筛选出1~n中的所有质数cin >> n; // 输入上限nget_primes(n); // 调用筛法函数，筛选1~n的质数cout << cnt << endl; // 输出1~n中质数的总个数return 0; // 程序正常结束
}
线性筛法（欧拉筛法，核心重点）
// 包含标准输入输出头文件（cin/cout依赖）
#include <iostream>
// 算法库（本代码未直接使用，属于通用模板保留）
#include <algorithm>// 使用std命名空间，避免重复写std::
using namespace std;// 常量定义：N为数组最大长度，1000010适配n≤1e6的场景（可根据需求调整）
const int N = 1000010;// 全局数组/变量（全局区默认初始化为0/false，无需手动清零，非常方便）
int primes[N]; // primes数组：存储筛选出的所有质数，primes[0]是第一个质数，依此类推
int cnt; // cnt：记录质数的总个数（primes数组的有效元素个数）
bool st[N]; // st标记数组：st[i]=true → i是合数；st[i]=false → i是质数// 线性筛（欧拉筛）核心函数：筛选 2 ~ n 之间的所有质数
// 优点：每个合数只会被**最小质因子**筛掉一次，时间复杂度 O(n)，效率最高
void get_primes(int n)
{// 从 2 开始遍历到 n，逐个判断每个数 ifor (int i = 2; i <= n; i ++ ){// 如果 i 没有被标记（st[i]=false），说明 i 是质数if (!st[i])primes[cnt ++ ] = i; // 把质数 i 存入 primes 数组，质数计数 +1// 核心：遍历已找到的所有质数，标记合数// 条件 primes[j] <= n / i 是为了防止乘积超出数组范围，避免越界for (int j = 0; primes[j] <= n / i; j ++ ){// 标记 质数primes[j] * 当前数i 为合数st[primes[j] * i] = true;// 线性筛最关键的一步：保证每个合数只被最小质因子筛除// 如果 i 能被当前质数 primes[j] 整除，说明 primes[j] 是 i 的最小质因子// 此时必须 break，再往后就会重复标记，破坏线性复杂度if (i % primes[j] == 0) break;}}
}int main()
{int n; // 定义变量 n：表示要筛选质数的上限（求 1~n 中的质数）cin >> n; // 输入上限 nget_primes(n); // 调用线性筛函数，筛选出 2~n 之间的所有质数cout << cnt << endl; // 输出质数的总个数return 0; // 程序正常结束
}