题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2136
题解：
水题
埃氏筛的同时把这个素数的倍数都标记为这个素数的序号
从小到大更新的同时就能保证一个数的序号是它的最大质因数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[1000010],n;
int main()
{
    int tot=0;
    for(int i=2;i<=1e6;i++)
        if(!f[i])
        {
            ++tot;
            for(int j=i;j<=1e6;j+=i)    f[j]=tot;
        }
    while(~scanf("%d",&n))
        printf("%d\n",f[n]);
    return 0;
}