C++中如何编写程序，将一个已知由两个不同素数相乘得到的正整数n分解并输出其中较大的素数？

在C++中，由于已知正整数n是两个不同素数的乘积，只需找到其中较小的素数因子p，再用n除以p即可得到较大的素数。

代码实现

#include <iostream>
using namespace std;

int main() {
    long long n;
    if (cin >> n) {
        for (long long i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                cout << n / i << endl;
                return 0;
            }
        }
    }
    return 0;
}

步骤说明

1. 读取输入的正整数n，建议使用long long类型以支持较大数值。
2. 从2开始循环遍历到i * i <= n（即sqrt(n)），逐一尝试整除。
3. 当首次遇到n % i == 0时，i即为较小的素数因子。因为n仅由两个素数相乘构成，所以无需额外判断i是否为素数。
4. 计算n / i并输出，即为所求的较大素数，随后结束程序。

判断依据

• 算术基本定理保证合数必有不超过其平方根的素因子。
• 题目限定n恰好为两个不同素数之积，因此第一个找到的因子必然是其中较小的素数，商必为较大的素数。

适用条件

• n必须是两个不同素数的乘积，且n > 1。
• 若n可能超出long long范围，需使用大数运算库。

常见误区

• 误加素性判断：在已知前提条件下，对找到的因子再做素性检测是多余的，会增加不必要的计算量。
• 循环上界设置不当：若将循环上界设为n而非sqrt(n)，时间复杂度会从O(√n)退化为O(n)，当n较大时导致超时。
• 数据类型溢出：使用int存储较大的n会导致溢出，应使用long long或更大范围的类型。