输出一个正整数,表示出现最多的质因子,如果有多个质因子出现一样多,输出最小的那一个。c++
时间: 2024-03-23 11:38:17 浏览: 44
好的,以下是一个 C++ 的实现代码,请你参考:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 判断是否是质数
bool is_prime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
int main() {
int n;
cin >> n;
vector<int> factors;
// 质因数分解
for (int i = 2; i <= n; i++) {
if (is_prime(i)) {
while (n % i == 0) {
factors.push_back(i);
n /= i;
}
}
}
// 统计每个质因子出现的次数
vector<pair<int, int>> counts;
int cnt = 1;
for (int i = 1; i < factors.size(); i++) {
if (factors[i] == factors[i - 1]) {
cnt++;
} else {
counts.push_back(make_pair(factors[i - 1], cnt));
cnt = 1;
}
}
// 最后一个质因子的处理
counts.push_back(make_pair(factors.back(), cnt));
// 找到出现次数最多的那个质因子,并且要保证它是最小的
sort(counts.begin(), counts.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
if (a.second != b.second) {
return a.second > b.second;
} else {
return a.first < b.first;
}
});
cout << counts[0].first << endl;
return 0;
}
```
这个程序会先对输入的正整数进行质因数分解,然后统计每个质因子的出现次数,最后找到出现次数最多的那个质因子,并且要保证它是最小的,输出即可。
阅读全文