【C/C++】任意大于1的整数分解成素数因子乘积的形式
时间: 2024-01-22 17:04:00 浏览: 12
以下是一个用C++编写的程序,可以将任意大于1的整数分解成素数因子乘积的形式:
```cpp
#include <iostream>
#include <vector>
using namespace std;
vector<int> primeFactors(int n) {
vector<int> factors;
// 将n中所有的2因子都除掉
while (n % 2 == 0) {
factors.push_back(2);
n /= 2;
}
// 从3开始,每次加2,找到n的所有奇数因子
for (int i = 3; i * i <= n; i += 2) {
while (n % i == 0) {
factors.push_back(i);
n /= i;
}
}
// 如果n大于2,则n本身是一个素数因子
if (n > 2) {
factors.push_back(n);
}
return factors;
}
int main() {
int n;
cout << "请输入一个大于1的整数:";
cin >> n;
vector<int> factors = primeFactors(n);
cout << n << " = ";
for (int i = 0; i < factors.size(); i++) {
cout << factors[i];
if (i != factors.size() - 1) {
cout << " × ";
}
}
cout << endl;
return 0;
}
```
该程序的思路是先将n中所有的2因子都除掉,然后从3开始,每次加2,找到n的所有奇数因子。如果n大于2,则n本身是一个素数因子。最后将所有素数因子输出即可。
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![whl](https://img-home.csdnimg.cn/images/20210720083646.png)