为了迎接国庆，信息学兴趣小组的同学在辅导老师的带领下，举办了一个盛大的晚会，晚会的第一项内容是做游戏：寻找质因数。老师会让若干个同学来回答问题，每次被提问的同学会拿到一张卡片，卡片上有N个数，他们的任务是求出N个数中质因数最大的数字。对于答对的同学，老师会派发一份精美的礼品。 输入 第一行，一个整数N，表示数字个数。 接下来N行，每行一个整数Ai，表示给出的数字。 N <= 5000 , Ai <= 20000 输出 一个整数，表示质因数最大的数字。

解题思路：

先预处理出所有小于等于20000的质数，再遍历每个给定的数字，将它分解质因数，记录出现次数最多的质数，输出即可。

具体实现：

先定义一个数组prime，存储所有小于等于20000的质数。

int prime[20005], cnt = 0;
bool isPrime[20005];
memset(isPrime, true, sizeof(isPrime));
for(int i = 2; i <= 20000; i++)
{
if(isPrime[i])
{
prime[cnt++] = i;
for(int j = i * i; j <= 20000; j += i)
{
isPrime[j] = false;
}
}
}

接下来，遍历每个给定的数字，将它分解质因数，记录出现次数最多的质数。

int n;
cin >> n;
int ans = 2, maxCnt = 0; //记录质因数最多的数字和其质因数个数
for(int i = 0; i < n; i++)
{
int num;
cin >> num;
int cnt = 0;
for(int j = 0; j < cnt && prime[j] <= num; j++) //对num进行分解质因数
{
if(num % prime[j] == 0)
{
cnt++;
while(num % prime[j] == 0) //统计prime[j]的个数
{
num /= prime[j];
}
}
}
if(cnt > maxCnt) //如果质因数个数更多，更新ans和maxCnt
{
ans = i;
maxCnt = cnt;
}
}

最后输出ans即可。

cout << ans << endl;