思路

题目保证 n 恰好是两个质数的乘积（n = p × q，p ≤ q）。这大大简化了问题：我们只要从 2 开始往上找，找到第一个能整除 n 的数，那它必然是较小的质因数 p，较大的那个就是 n / p。

为什么第一个找到的因数一定是质数？因为如果它是合数，它的质因数更小、也会整除 n，早就被先找到了。

为什么找到 p 后不用再往下找？因为 n 只有两个质因数，n / p 就是答案 q 本身，不需要再分解。

从 2 试到 √n 就够了：p ≤ q 意味着 p × p ≤ p × q = n，所以 p 不超过 √n（√(2×10⁹) ≈ 44721，循环最多四万多次，非常快）。

代码

#include <stdio.h>

int main() {
    long long n;                 // 2*10^9 已接近 int 上限，用 long long 更稳
    scanf("%lld", &n);

    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {        // 找到较小质因数 i
            printf("%lld\n", n / i);   // 较大的就是 n / i
            return 0;
        }
    }
    return 0;
}

用样例走一遍

n = 15：

• i = 2：15 % 2 = 1，不行；
• i = 3：15 % 3 = 0！输出 15 / 3 = 5。✓

再看 n = 6：

• i = 2：6 % 2 = 0，输出 6 / 2 = 3。

易错点

• n 最大约 2×10⁹，已经贴近 int 上限（2147483647）。用 int 读入虽勉强够，但 i * i 中间计算容易溢出，建议全程 long long，格式符用 %lld。
• 循环条件写 i * i <= n 而不是 i <= sqrt(n)：sqrt 是浮点运算，对大数可能有误差，导致差 1 的判断错误。
• 不需要判质数！题目保证只有两个质因数，找到第一个因数后 n / i 自动就是质数。写一个 isPrime 再逐个验证是多余的。
• 别循环到 n：那样最多要循环 20 亿次，会超时。√n 是关键。