题解 P3912 【素数个数】

不到前10不改名 · 2018-03-31 01:27:36 · 题解

史上最短AC代码之一

#include<stdio.h>
bool a[100000000];//话说我当初short int都没过，只从80到了90
int main()
{
    int n,i,j,s=0;
    scanf("%d",&n);
    s=n-1;//把一给去掉
    for(i=2;i*i<=n;i++)
    {if(a[i]==0)//正常筛法，无需解释（无黑科技，也不用高级筛法）
    for(j=i*2;j<=n;j+=i)//结合正常判断素数去做就能达到高级筛法的效果
    if(a[j]==0)（例如说i*i和筛法结合可以节省不少时间）
    {a[j]=1;
    s--;}}
    printf("%d",s);
    return 0;
}