hdu Largest prime factor

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 1000100
 5 using namespace std;
 6 
 7 int f[maxn];
 8 
 9 void inti()
10 {
11     int num=0;
12     for(int i=2; i<maxn; i++)
13     {
14         if(f[i]==0)
15         {
16             num++;
17             for(int j=i; j<maxn; j+=i)
18             {
19                 f[j]=num;
20             }
21         }
22     }
23 }
24 
25 int main()
26 {
27     int n;
28     inti();
29     while(scanf("%d",&n)!=EOF)
30     {
31         printf("%d\n",f[n]);
32     }
33     return 0;
34 }