思路分析

从后往前枚举虽然直觉上更直接（要找大的那个质数），但当数据很大时，从 n-1 开始往前枚举效率极差，会 TLE。

反过来从前往后枚举，找到第一个能被 n 整除的数，它就是较小的那个质因数，那么 n / i 就是较大的那个质因数，直接输出。

代码实现

1
2
3
4
5
6
7
8
9
long n = nextLong();
long i = 2;
while (i < Math.sqrt(n)) {
    if (n % i == 0) {
        System.out.println(n / i);
        return;
    }
    i++;
}

小结

  • 从前往后枚举往往比从后往前快得多
  • 枚举到 sqrt(n) 即可，因为因数成对出现