HDU 2136Largest prime factor（打表）

Largest prime factor Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit  Status  Practice  HDU 2136 Appoint description:  System Crawler  (Oct 13, 2016 7:58:16 PM)

Description

Everybody knows any number can be combined by the prime number. 

Now, your task is telling me what position of the largest prime factor. 

The position of prime 2 is 1, prime 3 is 2, and prime 5 is 3, etc. 

Specially, LPF(1) = 0. 

Input

Each line will contain one integer n(0 < n < 1000000). 

Output

Output the LPF(n). 

Sample Input

1
2
3
4
5      

Sample Output

0
1
2
1
3      

每個數都可以全由質數組成，找出組成此數最大質數位置。      

#include<iostream>
using namespace std;
int a[1000000];
int main()
{
    int k=1; 
     memset(a,0,sizeof(a));
    for(int i=2;i<1000000;i++)
    {
        if(!a[i])
        {
          a[i]=k; 
            for(int j=i+i;j<1000000;j+=i)
                a[j]=k;     
            k++;
        }
    }
    int n;
    while(~scanf("%d",&n))
    {
        printf("%d\n",a[n]);
    }
    return 0;
}