本文共 531 字，大约阅读时间需要 1 分钟。

题目出处：

http://acm.hdu.edu.cn/game/entry/problem/show.php?chapterid=2&sectionid=1&problemid=5

#include
   
    using namespace std;int a[1000000];int main(){    int k=1;//k初始化为1,位置        memset(a,0,sizeof(a));    /*筛选位置*/      for(int i=2;i<1000000;i++)//要到N,而不是sqrt(N)    {        if(!a[i])        {          a[i]=k;//素数i的位置               for(int j=i+i;j<1000000;j+=i)                a[j]=k;    //构造出j的暂时最大素数因子的位置             k++;        }    }    int n;    while(~scanf("%d",&n))    {        printf("%d\n",a[n]);    }    return 0;}
   

转载地址：http://agiqi.baihongyu.com/