(hdu step 2.1.3)Largest prime factor

タイトル:
       
Largest prime factor
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4868 Accepted Submission(s): 1452
 
Problem Description
Everybody knows any number can be combined by the prime number.
Now, your task is telling me what position of the largest prime factor.
The position of prime 2 is 1, prime 3 is 2, and prime 5 is 3, etc.
Specially, LPF(1) = 0.
 
Input
Each line will contain one integer n(0 < n < 1000000).
 
Output
Output the LPF(n).
 
Sample Input

1
2
3
4
5

 
Sample Output

0
1
2
1
3

 
Author
Wiskey
 
Source
HDU 2007-11 Programming Contest_WarmUp
 
Recommend
ウイスキー
テーマ分析:
              数の最大質量因子の位置を求めます.例えば2の最大質量因子は2で、それは最初の素数なので、その最大質量因子の位置は1.同理で3を得ることができる最大質量因子の位置は2.この問題は予め表を打つ方式でした.
1)小さいものから大きいものまでのデータ範囲内のすべての数.素因数を含む数の位置をすべて素因数の位置と同じにする.
2)同じ数の位置は複数回複写される可能性がある.しかし,小さい頃から大きな遍歴であるため,この数の最大質量因子が最後に書き込まれる位置が保証される.
コードは次のとおりです.

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

#include 
#include 


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
",biao[n]);//biao[n]  n         
	}

	return 0;
}