题解 P3912 【素数个数】

⚡进击_蒟蒻⚡ · 2019-04-28 20:03:28 · 题解

这道题的数据贼非常大，所以我用了欧拉筛）

因为时间复杂度基本上在O(n)，相信许多daolao早以使用过了

所以我就不做过多解释了。

直接上代码：

#include<bits/stdc++.h>
using namespace std;

bool a[100000001];
int main()
{
    int n,num=0;
    scanf("%d",&n);
    int n1=n;
    for(int i=2;i<=sqrt(n);i++)
    if(!a[i])
    for(int j=i*2;j<=n;j+=i)
    {
        if(!a[j])
       n1--;
    a[j]=1;
    }
    printf("%d",n1-1);
    return 0;
}

于是，就A了这题。