给定n个正整数,每个正整数都包含若干种质因子,现在小明想知道,这些质因子中,哪种质因子出现的次数最多(注意,每个数字中出现的每种质因子只统计一次)?用c++语言作答
时间: 2024-03-25 22:40:49 浏览: 59
好的,可以使用以下代码来实现:
```c++
#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int, int> countFactors(int n, int* nums) {
unordered_map<int, int> counts;
for (int i = 0; i < n; i++) {
int x = nums[i];
while (x > 1) {
int p = 2;
while (p <= x / p) {
if (x % p == 0) {
counts[p] = 1;
while (x % p == 0) {
x /= p;
}
}
p++;
}
if (x > 1) {
counts[x] = 1;
x = 1;
}
}
}
return counts;
}
int main() {
int n;
cin >> n;
int nums[n];
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
auto counts = countFactors(n, nums);
int maxCount = 0;
int maxFactor = 0;
for (auto p : counts) {
int count = 0;
for (int i = 0; i < n; i++) {
int x = nums[i];
while (x % p.first == 0) {
count++;
x /= p.first;
}
}
if (count > maxCount) {
maxCount = count;
maxFactor = p.first;
}
}
cout << maxFactor << endl;
return 0;
}
```
这段代码首先定义了一个函数countFactors,用来统计n个正整数中每种质因子出现的次数。这个函数内部首先对每个数字进行质因数分解,然后将每种质因子作为key,其出现次数作为value,存储到一个unordered_map中,并返回这个unordered_map。然后,在主函数中,读入n和n个数字,调用countFactors统计每种质因子出现的次数,并找到出现次数最多的那种质因子。具体来说,对于每种质因子p,遍历所有数字,统计p在这些数字中出现的次数,并更新出现次数最多的质因子和其出现次数。最后输出即可。
需要注意的是,当n比较大时,n个正整数中每种质因子出现的次数可能会很多,需要使用类似于map的方式来存储和处理。
阅读全文