题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2136
题目大意：
每个素数在素数表中都有一个序号，设1的序号为0，则2的序号为1，3的序号为2，5的序号为3，以此类推。现在要求输出所给定的数n的最大质因子的序号，0<n<1000000。
解题思路：
一开始用暴力超时，想到利用素数筛法，在筛素数的同时，每筛出一个素数就对之后的位置进行染色，比如2就对2的所有倍数染色，染成2的序号，3也是这样，而且会覆盖之前一部分2所染的地方，这样正好符合题意，求的是最大的素因子的位置序号。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<sstream>
#define Mem(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int INF = 1e9 + ;
const int maxn = +;
int ans[maxn];
bool is_prime[maxn];
int sieve(int n)//返回n以内素数的个数
{
int p = ;
for(int i = ; i <= n; i++)is_prime[i] = ;
is_prime[] = is_prime[] = ;
for(ll i = ; i <= n; i++)
{
if(is_prime[i])
{
p++;
ans[i] = p;
for(ll j = * i; j <= n; j += i)is_prime[j] = , ans[j] = p;
}
}
return p;
}
int main()
{
int tot = sieve();
int n;
while(scanf("%d", &n) != EOF)
{
if(n == )
{
printf("0\n");
continue;
}
printf("%d\n", ans[n]);
}
return ;
}