已知这个数字是两个质数的乘积,请求出这两个质数。c++
时间: 2024-03-24 11:39:30 浏览: 141
用C++完成求取两个数的商
这个问题可以使用质因数分解来解决。具体来说,我们可以从2开始,不断尝试将这个数除以2、3、4、5……,直到无法整除为止。这时候,如果这个数还大于1,说明它只能是一个质数,因为如果它能分解成两个质数的乘积,那么其中一个因子一定小于等于sqrt(n),另一个因子一定大于等于sqrt(n),而我们已经尝试过所有小于等于sqrt(n)的因子,因此这个数只能是一个质数。
下面是C++的代码实现:
```cpp
#include <iostream>
#include <cmath>
using namespace std;
bool is_prime(int n) {
if (n < 2) return false;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
int n;
cin >> n;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0 && is_prime(i) && is_prime(n / i)) {
cout << i << " " << n / i << endl;
break;
}
}
return 0;
}
```
我们可以先判断i是否为n的因子,如果是的话,就判断i和n/i是否都是质数。如果是,就输出它们。这里我们使用了一个辅助函数is_prime来判断一个数是否为质数。时间复杂度为O(sqrt(n))。
阅读全文