LuoguP3912 素数个数 解题报告【筛法求素数】
程序员文章站
2024-03-23 16:07:46
...
解题报告
这是一道筛法求素数的练习题
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e8;
bool flag[N+5];
int prime[N+5],n,num;
void init()
{
memset(flag,true,sizeof(flag));
flag[1]=false;
for(register int i=2;i<=n;i++)//据说不写register要挂一个点
{
if(flag[i])prime[++num]=i;
for(register int j=1;j<=n&&i*prime[j]<=n;j++)
{
flag[i*prime[j]]=false;
if(i%prime[j]==0)break;//i被以前的prime[j]筛掉了
}
}
}
int main()
{
scanf("%d",&n);
init();
printf("%d",num);
return 0;
}