AcWing 868. 筛质数
原题链接
简单
作者:
Drifter
,
2021-01-12 11:56:53
,
所有人可见
,
阅读 259
寒假打卡
1.12过
方法一
//线性筛法
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000010;
int n,cnt;
int prime[N];
bool st[N];
void get_prime_num(int n)
{
if(n==1) return;
for(int i=2;i<=n;i++)
{
if(!st[i]) prime[cnt++]=i;
for(int j=0;prime[j]<=n/i;j++)
{
st[prime[j]*i]=true;
if(i%prime[j]==0) break;
}
}
}//get_prime_num
int main(void)
{
scanf("%d",&n);
get_prime_num(n);
printf("%d\n",cnt);
return 0;
}
方法二
//埃氏筛法
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000010;
int n,cnt;
int prime[N];
bool st[N];
void get_prime_num(int n)
{
if(n==1) return;
for(int i=2;i<=n;i++)
{
if(!st[i]) prime[cnt++]=i;
for(int j=0;prime[j]<=n/i;j++)
{
st[prime[j]*i]=true;
if(i%prime[j]==0) break;
}
}
}//get_prime_num
int main(void)
{
scanf("%d",&n);
get_prime_num(n);
printf("%d\n",cnt);
return 0;
}