先写一遍思路，跟素数表很类似吧。
1）从小到大遍历数据范围内的所有数。把包含质因子的数的位置都设成跟质因子的位置相同。
2）同一个数的位置可能被多次复写。但是由于是从小到大遍历，这就保证了最后一次写入的是该数的最大质因子的位置
一道题墨迹了好久，上代码分析
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn=;
int a[maxn];
void prime()
{
int i,j,k=;
for(i=; i<maxn; i++)
{
if(a[i]==)
{
k++;
a[i]=k;
for(j=; j*i<maxn; j++)
{
a[i*j]=k;
}//把这个for循环是写在if里面还是外面纠结了好久，写在外面怎么可能对呢？= =
}
}
}
int main ()
{
int n;
prime();
while(~scanf("%d",&n))
{
memset(a,,sizeof());//首先刚开始把prime()写到这里了，= =怪不得超时，蠢哭 printf("%d\n",a[n]);
}
return ;
}
总之，在网上看完思路写代码的过程中也是状况百出，一年前接触过素数表，现在早都忘记了，重拾后运用的依旧不熟练啊。