题目：

1
2
3
4
5

0
1
2
1
3

题目分析：

              求一个数的最大质因子的位置。例如2的最大质因子是2，它是第一个素数，所以它的最大质因子的位置就是1.同理可得3的最大质因子的位置是2.这道题采用预先打表的方式来做。

1）从小到大遍历数据范围内的所有数。把包含质因子的数的位置都设成跟质因子的位置相同。

2）同一个数的位置可能被多次复写。但是由于是从小到大遍历，这就保证了最后一次写入的是该数的最大质因子的位置

代码如下：

/*
 * c1.cpp
 *
 *  Created on: 2015年1月30日
 *      Author: Administrator
 */

#include <iostream>
#include <cstdio>


using namespace std;

const int maxn = 1000005;
int biao[maxn];

/**
 * 求一个数的最大质因子的位置。如2的位置是1。
 * 3的位置是2
 */
void prepare(){
	int i;
	int k = 1;
	for(i = 2 ; i < maxn ; ++i){//遍历数据范围内的所有数
		if(biao[i] == 0){//如果这一个数的最大质因子的位置还没有确定
			int j;
			for(j = 1 ; i*j < maxn ; ++j){//把含有这个质因子的所有数的位置都标记成这个质因子的位置
				biao[i*j] = k;
			}
			k++;//质因子的位置索引+1
		}
	}
}


int main(){
	int n;
	prepare();
	while(scanf("%d",&n)!=EOF){
		printf("%d\n",biao[n]);//biao[n]表示n的最大质因子的位置
	}

	return 0;
}

(hdu step 2.1.3)Largest prime factor(求一个数的最大质因子的位置)