C++递归整数分解,将一个正整数分解成若干个正整数之和
时间: 2024-09-29 13:09:29 浏览: 24
在C++中,递归整数分解通常用于将一个正整数n分解为质因数的乘积。下面是一个简单的例子,展示了如何通过递归来找到所有小于等于n的质因子,并返回它们的组合:
```cpp
#include <iostream>
#include <vector>
// 判断是否为质数
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;
}
// 递归分解函数
std::vector<int> primeFactorsRecursion(int n, int factor = 2) {
std::vector<int> factors;
// 当n为质数时直接添加到结果中
if (n > 1 && isPrime(n))
factors.push_back(n);
// 否则继续查找下一个因子
else if (n >= factor) {
while (n % factor == 0) {
factors.push_back(factor);
n /= factor;
}
// 递归处理剩余部分
factors.insert(factors.end(), primeFactorsRecursion(n, factor + 1).begin(), primeFactorsRecursion(n, factor + 1).end());
}
return factors;
}
int main() {
int number;
std::cout << "Enter a positive integer: ";
std::cin >> number;
std::vector<int> factors = primeFactorsRecursion(number);
std::cout << "Prime factor decomposition of " << number << ": ";
for (const auto& factor : factors)
std::cout << factor << " ";
return 0;
}
```
在这个程序中,`primeFactorsRecursion` 函数首先检查输入的数字是否为质数,如果是,则添加到结果中。如果不是,就从最小的质因子开始(这里是2),不断除以这个因子直到不能再整除,然后递归地处理余下的部分。
当你运行这个程序并输入一个正整数,它会输出该数的所有质因子。