题解 P3912 【素数个数】
luoyoucheng · · 题解
线性筛把素数筛出来，然后直接输出
不说废话，把你们想要的代码送给你们
#include<iostream>
using namespace std;
bool isComp[100000005]; //是不是素数
int main ()
{
int n,ans=0;
cin>>n;
isComp[1]=1; //1的特判
for(int i=2;i*i<=n;i++)
{
if(isComp[i]==0) //如果是素数
for(int j=i*i;j<=n;j+=i) //将他的倍数记为合数
isComp[j]=1; //标记
}
for(int i=1;i<=n;i++)
{
if(isComp[i]==0) //如果是素数
ans++;
}
cout<<ans<<endl; //输出
return 0; //华丽结束
}