小红拿到了一个正整数 x,她想知道 x有多少个不同的素因子,你能帮帮她吗?c++
时间: 2024-12-28 10:30:19 浏览: 10
当然可以。在C++中,要计算一个正整数x的不同素因子的数量,你可以采用一种分解质因数的方法。首先,你需要创建一个哈希集合或计数数组(std::unordered_set 或 std::vector<bool>),用于存储每个素数是否已经出现过。然后,你可以从最小的素数2开始遍历,直到不大于√x的所有素数。对于每一个素数,如果它是x的因子,就将其添加到哈希集合中,并将x除以这个因子,继续寻找下一个因子。当x变成1时,所有找到的素数就是它的所有不同素因子。
这是一个简单的伪代码示例:
```cpp
#include <iostream>
#include <vector>
using namespace std;
bool isPrime(int num) {
if (num <= 1) return false;
for (int i = 2; i * i <= num; ++i)
if (num % i == 0) return false;
return true;
}
int countDistinctPrimeFactors(int x) {
vector<int> factors;
int divisor = 2;
while (x > 1) {
if (isPrime(divisor)) {
bool found = false;
while (x % divisor == 0) {
found = true;
x /= divisor;
}
if (found) factors.push_back(divisor);
}
divisor++;
}
return factors.size();
}
int main() {
int x;
cout << "Enter a positive integer: ";
cin >> x;
int distinct_factors = countDistinctPrimeFactors(x);
cout << "The number has " << distinct_factors << " different prime factors.\n";
return 0;
}
```
阅读全文