p,q为两质数,且p*q=n,给定n求p,q C++
时间: 2024-02-09 09:09:46 浏览: 31
这个问题涉及到RSA算法的密钥生成过程,需要用到质数分解。以下是C++代码实现:
```c++
#include <iostream>
#include <cmath>
using namespace std;
bool is_prime(int n) {
if (n <= 1) return false;
int sqr = (int)sqrt(n);
for (int i = 2; i <= sqr; i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
int n;
cout << "请输入n的值:";
cin >> n;
int p = 0, q = 0;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0 && is_prime(i) && is_prime(n / i)) {
p = i;
q = n / i;
break;
}
}
if (p == 0 || q == 0) {
cout << "无法分解质因数" << endl;
} else {
cout << "p = " << p << ", q = " << q << endl;
}
return 0;
}
```
该程序首先输入n的值,然后从2到sqrt(n)遍历所有数,找到能够整除n且为质数的两个数p和q,输出结果。如果无法分解质因数,则输出“无法分解质因数”。
相关推荐
![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)
![](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)