1620：质因数分解

题目描述

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

输入格式

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

输出格式

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

样例

样例输入 #1

21

样例输出 #1

7

样例解释 #1

$21 = 3 \times 7$，较大的质数是 $7$。

数据范围

• 对于 $30\%$ 的数据，$n \le 1000$；
• 对于全部数据，$6 \le n \le 2 \times 10^9$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：由于 $n$ 是两个不同质数的乘积，所以 $n$ 的因数只有 $1$、较小的质数、较大的质数和它本身。我们只需要找到 $n$ 的一个大于 $1$ 且小于 $n$ 的因数，那么另一个因数就是 $n$ 除以这个因数。较大的那个就是答案。

因为 $n$ 不超过 $2 \times 10^9$，我们可以从 $2$ 开始枚举到 $\sqrt{n}$（因为如果 $n$ 是合数，必有一个因数不大于 $\sqrt{n}$）。由于 $n$ 是两个质数的乘积，所以枚举到的第一个因数一定是较小的那个质数（因为质数从小到大枚举）。时间复杂度 $O(\sqrt{n})$，在 $n \le 2 \times 10^9$ 时，$\sqrt{n} \le 44721$，可以接受。

注意：题目保证 $n$ 是两个不同质数的乘积，所以不需要判断枚举到的数是否为质数（因为 $n$ 只有两个质因数，且它们都是质数）。直接找到第一个能整除 $n$ 的数 $i$，则较大的质数为 $n / i$。