线性筛素数
作者:
不易.
,
2023-10-30 22:06:40
,
所有人可见
,
阅读 159
线性筛素数时间到
给定一个数字n,快速找出 1 - n有多少个素数
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
bool is_sushu[N];
// 存第i个数是否是素数
int sushu[N];
// 存已经筛出的素数
int cnt = 0;
// 初始cnt全局变量为0,记录从1 - n有几个素数
void init(int n)
{
memset(is_sushu, true, sizeof(is_sushu));
// 初始化is_sushu,
// 将is_sushu内所有元素标为true
is_sushu[1] = false;
// 第一个数1既不是质数也不是合数
for(int i = 2; i <= n; i++)
// 开始遍历,筛素数
{
if(is_sushu[i])
// 如果第i个是素数,则存入sushu[N]数组中
sushu[++cnt] = i;
// 记录i入sushu[N]数组中
for(int j = 1; j <= cnt && i * sushu[j] <= n; j++)
// 开筛, 往后遍历
// j <= cnt 是因为不能超过已经有记录的素数个数
// i * sushu[j] <= n 是因为不能超过需要求的最大数
{
is_sushu[i * sushu[j]] = false;
// 第 i 个数乘第第j个素数的积显然不是素数
if(!(i % sushu[i]))
break;
}
}
}
int main()
{
int n;
cin >> n;
init(n);
cout << cnt << endl;
return 0;
}
毛毛粉丝