【题目来源】
AcWing：868. 筛质数 - AcWing题库
【题目描述】
给定一个正整数 \(n\)，请你求出 \(1\sim n\) 中质数的个数。
【输入】
共一行，包含整数 \(n\)。
【输出】
共一行，包含一个整数，表示 \(1\sim n\) 中质数的个数。
【输入样例】
8
【输出样例】
4
【解题思路】
【算法标签】
《AcWing 868 筛质数》 #数学知识# #质数# #筛质数#
【代码详解】
// 埃式筛法
#include <bits/stdc++.h>
using namespace std;const int N = 1000005; // 定义筛法上限int primes[N], cnt; // primes数组存储素数，cnt记录素数个数
bool st[N]; // 标记数组，false表示是素数，true表示不是素数// 埃拉托斯特尼筛法求素数
void get_primes(int n)
{// 从2开始遍历到nfor (int i = 2; i <= n; i++){// 如果当前数未被标记为非素数if (!st[i]){primes[cnt++] = i; // 将当前数加入素数数组// 标记当前素数的所有倍数为非素数for (int j = i + i; j <= n; j += i)st[j] = true;}}
}int main()
{int n; // 输入的上限值cin >> n;// 调用筛法函数获取素数get_primes(n);// 输出素数个数cout << cnt << endl;return 0;
}
// 线性筛
#include <bits/stdc++.h>
using namespace std;const int N = 1000005; // 定义筛法上限int primes[N], cnt; // primes数组存储素数，cnt记录素数个数
bool st[N]; // 标记数组，false表示是素数，true表示合数// 线性筛法（欧拉筛）求素数
void get_primes(int n)
{// 从2开始遍历到nfor (int i = 2; i <= n; i++){// 如果i未被标记为合数，则i是素数if (!st[i])primes[cnt++] = i; // 将i加入素数数组// 用当前已找到的素数筛选合数for (int j = 0; primes[j] <= n / i; j++){st[primes[j] * i] = true; // 标记素数的倍数为合数// 关键优化：当primes[j]是i的最小质因子时终止筛选if (i % primes[j] == 0)break;}}
}int main()
{int n; // 输入的上限值cin >> n;// 调用线性筛法函数获取素数get_primes(n);// 输出素数个数cout << cnt << endl;return 0;
}
【运行结果】
8
4