C++: 求两个质数乘积中的较大质数

已知正整数n是两个不同的质数的乘积，试求出较大的那个质数。

输入

输入只有一行，包含一个正整数 n。

• 对于60%的数据，6 ≤ n ≤ 1000。
• 对于100%的数据，6 ≤ n ≤ 2×10^9。

输出

输出只有一行，包含一个正整数 p，即较大的那个质数。

样例输入

21

样例输出

7

解题思路：

1. 首先，我们需要判断一个数是否为质数。质数是指除了1和自身以外没有其他因数的数。所以我们可以遍历从2到这个数的平方根，如果这个数能被其中任意一个数整除，则说明不是质数。
2. 对于给定的正整数n，我们需要找到两个不同的质数p和q，使得p*q=n，并且p>q。我们可以从n的平方根开始遍历，找到第一个能整除n的数p，然后再判断p是否为质数。如果p是质数，则p为较大的质数，输出p即可。

具体实现：

1. 首先，我们需要实现一个函数isPrime()来判断一个数是否为质数。该函数参数为一个正整数num，返回值为bool类型。我们可以遍历从2到num的平方根，判断num是否能被其中任意一个数整除。如果能整除，则返回false；如果遍历完都没有能整除num的数，则返回true。
2. 在主函数中，我们先读入正整数n。然后从n的平方根开始遍历，找到第一个能整除n的数p，并调用isPrime()函数判断p是否为质数。如果p是质数，则输出p并结束循环。
3. 最后，输出的p即为较大的质数。

C++代码实现如下：

#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
int main() {
int n;
cin >> n;
for (int i = sqrt(n); i >= 2; i--) {
if (n % i == 0 && isPrime(i)) {
cout << i << endl;
break;
}
}
return 0;
}