题解 | #质数因子#

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long num = in.nextLong();
        long sqr = (long)Math.sqrt(num);
        for (int i = 2; i <= sqr; i++) {
            while (num % i == 0) {
                System.out.print(i+" ");
                num /= i;
            }
        }
        System.out.println(num == 1? " " : num + " ");
    }
}

先上代码。这道求解质数因子的的题目，花了一个多小时，在看了别人的题解和知乎上的解释后，终于算是理解了。简单的在这里整理一下这道题的解题思路，分享给正在疑惑的朋友，更多的是为自己留一个记录，方便以后做参考。

题解链接：https://blog.nowcoder.net/n/9ada1e1b34c54ad29df16cc154a3f7c8

知乎链接：https://www.zhihu.com/question/410344030

这道题有两个重点：第一个是在求解一个数的质数因子的时候，思路就是从2开始遍历（for循环），如果num可以整除2，那就让它一直除下去（while循环），直到2无法整除了，那就接着用3除....一直遍历到这个数本身。但这样做的问题是效率太低了，如果num很大，代码就会超时，用例就通不过了，所以就有了第二点。

第二点，其实就是对for循环的终止条件进行了优化，之前是遍历到这个数本身，现在改成遍历到这个数的平方根，这样遍历的数就少了，特殊用例就能通过了。这样操作的原理是：一个正整数n最多只会有一个质因子大于n的平方根。（证明过程看上方知乎链接）

具体解释就是：在遍历的过程中，如果i 大于平方根了，那就不用再继续遍历了，因为后面最多只会有一个质因子，而且这个质因子就是当前的这个num（num != 1时成立），所以14行在输出时会做一个判断 ，如果是1，就不输出，否则输出，这样答案就是完整的。

举两个例子，便于理解14行代码的作用：以42为例，42 = 2 * 3 *7，42的平方根取整是6，也就是说上面的循环到i = 6时，是最后一次，num = 7，当i=7，循环退出，将num=7输出刚好。

以49为例，49 = 7*7，平方根是7，所以最后一次后num= 1，这个1肯定不能输出，所以加了判断