题解 P3912 【素数个数】

LiYanJun · 2017-10-29 23:06:41 · 题解

来一个短的代码

#include <iostream>//很简单的线性筛
#include <cstdio>
#include <cmath>
using namespace std;
bool val[100000001];//质数为0合数为1
int n,k;
int main(){
    scanf("%d",&n);
    int sum=0;//这里sum记录的是合数的个数
    for(int i=2;i<=sqrt(n);i++)//筛到根号n即可
        if(!val[i])//用质数筛
            for(k=2;k*i<=n;sum+=val[i*k]?0:1,val[i*k++]=1);//将i的倍数筛去
    printf("%d",n-sum-1);
    return 0;
}