已知正整数 n 是两个不同的质数的乘积,试求出较大的那个质数。 输入格式 输入只有一行,包含一个正整数 n(1=<n<=10^9)。 输出格式 输出只有一行,包含一个正整数 p,即较大的那个质数。用c++编程
时间: 2024-12-01 08:29:26 浏览: 19
Crypto:两次对RSA的著名攻击的实现
在C++中,你可以使用一个简单的算法来解决这个问题。由于已知n是两个质数的乘积,那么n一定可以分解成两个质因数的乘积,其中一个肯定是比另一个大的质数。你可以遍历从n的平方根到n的所有整数,检查每个数是否能整除n,如果找到一个能整除的数并且这个数不是n本身,那么它就是较小的那个质数,n除以这个数就得到较大的质数。
下面是一个示例C++程序:
```cpp
#include <iostream>
#include <cmath>
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 findLargerPrime(int n) {
int sqrt_n = std::sqrt(n);
for (int i = sqrt_n; i > 1; --i) {
if (n % i == 0 && isPrime(i)) {
// i是较小的质数,n/i是较大的质数
return n / i;
}
}
// 如果没有找到,说明n本身就是质数,返回n
return n;
}
int main() {
int n;
std::cin >> n;
int larger_prime = findLargerPrime(n);
std::cout << larger_prime << "\n";
return 0;
}
```
当运行这个程序时,你需要输入一个正整数n,然后它会找出并输出较大的质数。
阅读全文