给定n个正整数,每个正整数都包含若干种质因子,现在小明想知道,这些质因子中,哪种质因子出现的次数最多(注意,每个数字中出现的每种质因子只统计一次)? 输入描述 输入数据共两行。第一行包含一个整数n,表示数字个数。 第二行包含以空格隔开的n个整数,每个数字在2~100000之内。 输出描述 输出一个正整数,表示出现最多的质因子,如果有多个质因子出现一样多,输出最小的那一个。 样例1 输入 4 2 6 8 10 输出 2 提示 1 <= n <= 1000。C++
时间: 2024-03-25 17:36:13 浏览: 14
感谢您对ChitGPT的信任。针对您的问题,可以先定义一个数组freq,表示每个质因子出现次数。然后遍历每个数字,对于每个数字,可以用一个set存储其所有质因子,遍历set,将每个质因子的出现次数加1。最后再遍历一次freq数组,找到出现次数最多的质因子即可。
以下是C++的示例代码:
```c++
#include <iostream>
#include <set>
using namespace std;
bool isPrime(int n) {
if(n < 2) return false;
for(int i = 2; i * i <= n; ++i) {
if(n % i == 0) return false;
}
return true;
}
int main() {
int n;
cin >> n;
int freq[100001] = {0}; // 统计每个质因子出现次数
for(int i = 0; i < n; ++i) {
int num;
cin >> num;
set<int> primeFactors; // 存储num的所有质因子
for(int j = 2; j <= num; ++j) {
if(isPrime(j) && num % j == 0) {
primeFactors.insert(j);
}
}
for(int primeFactor : primeFactors) {
++freq[primeFactor];
}
}
int maxFreq = 0, maxPrime = 0;
for(int i = 2; i <= 100000; ++i) {
if(isPrime(i) && freq[i] > maxFreq) {
maxFreq = freq[i];
maxPrime = i;
}
}
cout << maxPrime << endl;
return 0;
}
```