欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LuoguP3912 素数个数 解题报告【筛法求素数】

程序员文章站 2024-03-23 16:07:46
...

LuoguP3912 素数个数 解题报告【筛法求素数】
解题报告
这是一道筛法求素数的练习题

#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;
}