题目链接：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;
}