开始是把本题当作素数筛然后加上判断因子就行了，发现了TLE。只能另寻他路了

想了很久发现了可以和素数筛联系到的方法，用素数筛置值即可，由于我们求的是素因子在素数表的位置，

那么就可以打表了。

我们可以先不管因子与否，先将某素数（假设为a）的所有倍数(大于1)全部置为该素数的位置值，然后循环让接下来的其他素数将他们的倍数置为他们的位置值，这样到最后越大的数也就拥有相应的正确的位置值了

注意，这里的位置值指的是某数的最大素因子在素数表中的位置值。

这里说明一下，如果这个数是一个类似于2^n，或者3^n，5^n类型的数，你会发现的是除了他们的幂，没人可以更新他们的max_primefactor_position。

再举几个例子：

如10 = 5 * 2，因此从被2置过后，除了5没有可以更新它的max_primefactor_position

如12 = 3 * 2 * 2，因此从被2置过后，除了3没有可以更新它的max_primefactor_position

如14 = 7 * 2，因此从被2置过后，除了7没有可以更新它的max_primefactor_position（懒得打字了）

而由于是从2开始递增的，2，3，5，7这是前4个素数，故答案依次是3， 2， 4

如21 = 7 * 3， 22 = 11 * 2， 23 = 23， 24 = 2 * 2 * 2 * 3

你会发现的是将一个数不断的拆，只要他还能拆，将其拆成最长的相乘形式然后找出最大素数即可

下面是AC代码



#include<stdio.h>
const int maxn = 1000005;
int a[maxn];
int main()
{
	int g = 1;
	for(int i = 2; i < maxn; i++){
		if(a[i] == 0){//如果i是素数,每次会把后面的非素数置k 
			a[i] = g; //这时候记录下这个素数的位置 
			for(int j = 2; j*i < maxn; j++)
				a[j*i] = g;
            g++;
            /*将素数的倍数位置都置为k，这里无需担心，
			因为之后的素数倍数会将他们的倍数继续置为相应的k，
            相应数的最大素因子位置也就改变了。 */		
		}
	}
	int n;
	while(scanf("%d", &n) != EOF){
		printf("%d\n", a[n]);
	}
}

hdu2136 素因子筛

注意，这里的位置值指的是某数的最大素因子在素数表中的位置值。