2136.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include<cstdio>
#include<cmath>
int prime[1000001]={0};
const int maxsize=1000000;
int main()
{
    int n,i,j,k,c,max;
    c=1;
    for(i=2;i<=maxsize;i++)
        if(prime[i]==0){
            prime[i]=c;
            for(j=i*2;j<=maxsize;j+=i)
                prime[j]=c;
            c++;
        }
    while(scanf("%d",&n)!=EOF)
        printf("%d\n",prime[n]);
    return 0;
}