已知正整数n是两个不同的质数的乘积,试求出较大的那个质数。用C++写出来,简化
时间: 2024-09-21 18:01:45 浏览: 74
分解质因数与质因数乘积
已知正整数n可以表示为两个不同的质数p和q的乘积(即 n = p * q),要求解较大的质数q。由于n分解成质因数后只有一个重复的因子,我们可以遍历从 sqrt(n) 开始的所有数字,看它们是否能整除n,同时记录下这个因子,如果发现第二个相同的因子,则就是较小的那个质数p。较大的质数q就是n除以p的结果。
以下是使用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 >= 2; --i) { // 从根号n向下检查
if (isPrime(i) && n % i == 0) {
int smaller_prime = i;
int larger_prime = n / i;
return larger_prime; // 返回较大的质数
}
}
throw std::runtime_error("No unique prime factors found.");
}
int main() {
int n;
std::cout << "Enter a number that can be expressed as the product of two different primes: ";
std::cin >> n;
try {
int larger_prime = findLargerPrime(n);
std::cout << "The larger prime factor is: " << larger_prime << std::endl;
} catch (const std::exception& e) {
std::cerr << "Error: " << e.what() << std::endl;
}
return 0;
}
```
当你运行此程序并输入满足条件的n时,它会返回较大的质数。注意,这个实现假设输入的是合数,并且确实存在两个不同的质数因子。
阅读全文