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.

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

Output the LPF(n).

1
2
3
4
5

0
1
2
1
3


解题思路：
	题意是求所给数的最大质因数。并且求出这个质因数在素数表中为第几位。
	一开始把题目理解错了，以为是把一个数拆分成两个质因数相加。结果果断TLE。。
	只能说英语不行啊。。。

算法：
	素数筛选。在给素数标记时有个巧妙的小窍门，详见代码。

代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a[1000005][2]= {0};
int main ()
{
    int n,i,j,t=1;
    for (i=2; i<=1000000; i++)
    {
        if (a[i][0]==0)
        {
            for (j=i*2; j<=1000000; j+=i)
            {
                a[j][0]=1;
                a[j][1]=t;  //用t来表示这是第几个素数
            }
            a[i][1]=t;
            t++;    //每次标记完一个素数后，将标记量加1
        }
    }
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d\n",a[n][1]);
    }
    return 0;
}