最大质因数

试题 算法训练 最大质因数

​
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
　　给出N个数字，求出有最大的最大质因数的那个数
输入格式
　　第一行：一个整数N。
　　接下来的N行，每行一个整数A_i，表示给出的那N个数字。
输出格式
　　第一行：一个整数，拥有最大的最大质因数的那个数。
样例输入
4
36
38
40
42
样例输出
38
数据规模和约定
　　60%的数据满足：N<=100
　　100%的数据满足：N<=2500,A_i<=20000 　　

#include<iostream>
using namespace std;

int GetMaxPrime(int n) {
	int i = 2;
	int res = 1;
	while (n > 2) {
		if (n%i == 0) {
			n /= i;
			res = i;
		}
		else
			i++;
	}
	return res;
}

int main(){
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int index=0;
	int max=GetMaxPrime(a[0]);
	for(int j=0;j<n;j++){
		if(GetMaxPrime(a[j])>max){
			max=GetMaxPrime(a[j]);
			index=j;
		}
	}
	cout<<a[index];
	return 0;
}