概述

本题要求出正整数 ~n~ 的两个不同质因数中较大的那个。关键在于从小到大递增试除：第一个能整除 ~n~ 的数必然是较小的质因数，用 ~n~ 除以它即得答案。

分析

核心观察

~n~ 的正因数只有 ~1~、~p~、~q~、~n~ 这四个（其中 ~p < q~ 均为质数）。因此从 ~2~ 开始递增试除，第一个整除 ~n~ 的数一定是 ~p~，它本身必为质数，无需额外的质数判定。

思路

设 ~n = p \times q~，其中 ~p < q~ 均为质数。由 ~p < q~ 可得

$$\displaystyle p^2 < p \times q = n $$

即 ~p < \sqrt{n}~，较小质数必定落在 ~\sqrt{n}~ 以内。

于是从小到大枚举 ~i = 2, 3, \dots~，第一个满足 ~n \bmod i = 0~ 的 ~i~ 就是 ~p~，输出 ~n \div p~ 即可。枚举过程中不会先遇到合数因子——~n~ 的因数集只有 ~\{1, p, q, n\}~，这保证了第一个被找到的因子必为质数。

若把枚举上界放松到 ~n~，复杂度会退化为 ~O(n)~，在 ~n = 2 \times 10^9~ 时无法接受；把上界收紧到 ~\sqrt{n}~ 是解法的全部要点。另有先筛出 ~\sqrt{n}~ 以内全部质数再试除的做法，复杂度同为 ~O(\sqrt{n})~，但需要额外数组，本题直接试除即可。

具体示例

以 ~n = 21~ 为例：枚举 ~i = 2~ 时 ~21 \bmod 2 = 1~，不整除；枚举 ~i = 3~ 时 ~21 \bmod 3 = 0~，整除，故较小质数为 ~3~，答案为 ~21 \div 3 = 7~。

再看 ~n = 1999878319~：该数分解为 ~44711 \times 44729~，两因子均为质数，且 ~44711 < \sqrt{n} < 44729~，因此循环需从 ~2~ 一直枚举到 ~44711~，共试除 ~44710~ 次，是本题数据中最坏的一组。可见上界 ~\sqrt{n} \approx 44721~ 与实际的首次命中位置相当接近。

算法步骤

1. 读入整数存入 n，令 i 的初值为 ~2~。
2. 若 i 的平方大于 n，结束循环（题面保证输入合法，实际不会走到这一步）。
3. 若 i 整除 n，输出 n 除以 i 的商并结束程序。
4. 令 i 增加 ~1~，回到第 ~2~ 步。

复杂度分析

• 时间：~O(\sqrt{n})~。最坏情况试除次数不超过 ~44720~ 次。
• 空间：~O(1)~。

实现注意事项

• 循环条件写成 ~i \times i \le n~，不要用开方结果作比较，可完全避免浮点误差。
• 当 ~n~ 取到 ~2 \times 10^9~ 时，中间量 ~i \times i~ 最大约 ~2.0 \times 10^9~，虽未超出 ~32~ 位有符号整数上限，但余量很小；用 ~64~ 位整数保存 ~i~ 更为稳妥。
• 只需输出较大质数，即 ~n \div i~，不要输出枚举到的 ~i~ 本身。
• 找到整除的数后应立即输出并退出，无需继续枚举。
• 题面保证 ~n~ 是两个不同质数的乘积，最小值 ~6 = 2 \times 3~ 对应 ~6 \div 2 = 3~，不需要特判。
• Python 中取商须使用整除运算符，写成单斜杠会得到浮点数并可能引入精度误差。

源代码

#include <iostream>
using namespace std;

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

n = int(input())
i = 2
while i * i <= n:
    if n % i == 0:
        print(n // i)
        break
    i += 1