题解 P3912 【素数个数】

Bronya18C · 2017-12-05 14:33:18 · 题解

1.首先，你要判断它是不是1（第一个点），

2.然后，要把二的倍数去掉。

3.再用线筛去完成（2的倍数去掉）

注意：

1.把二的倍数去掉，不然会超时。

2.数组用bool型，其他用整形int，才能确保不会MLE。

#include<iostream>
#include<cmath>
using namespace std;
int N,sum,n;
bool a[100000000];
int main()
{
 cin>>N;
 if(N<2){cout<<"0";return 0;}
 sum=N;
 sum-=N/2-1;
 a[1]=true;
for(register int i=3;i<=sqrt(N);i+=2)
 {
     if (a[i]==false)
     {
     for(register int j=i*2;j<=N;j+=i)
     {
     if (a[j]==false&&j%2!=0) 
     {
        sum--;
     }
     a[j]=true;
     }
    }
 }
 cout<<sum-1;
 return 0;
}