题解 | #质数因子#

import java.lang.Math;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int num = in.nextInt();
        reslove(num);
    }

    private static void reslove(int num) {
        //由2开始的质因数，由于递归的原因，
        //如果i不是质因数：则其必然可以被分解为小于math.sqrt(i)的质因数，
        //如果i是质因数：则要么能被num除尽(调用递归)，
        //            ：要么不能被出尽(不是能被分解的,下一个i)
        //如果对于num，一整个循环完成，仍然不能被分解，则其本身是质因数
        for (int i = 2; i <= Math.sqrt(num); i++) {
            //能除尽说明是质因数
            if (num % i == 0) {
			    //在递归的前面打印，就是先序，后面就是后序，和树的递归一致
                System.out.print(i + " ");
                reslove(num / i);
			   //这里注意，找到了一个质因数，就去递归被除后的数，这里就到叶子节点了直接返回了
                return;
            }
        }
	    //这里注意，循环完了还找不到，说明它本身是质数，打印并返回，这里是叶子节点了
        if (num > 1) {
            System.out.print(num + " ");
            return;
        }
    }
}

一开始没有想明白为什么在不知道质数列表的情况下要怎么去循环判断？

实际上有一点可以帮助我们通过递归解决不知道循环过程中的数是不是质数的问题，那就是：

一个数要么是是质数，要么是可以被分解为比自己小的质因数的乘积

另一点，如果一个数不是质数，它的最大质因数必然小于等于其平方根，

所以，只要我们按照有小到大的循环递归，那么递归到i的时候，小于i的质因数必然已被分解，比如i=4的时候必然不能被除尽即num%i ==0必然不会成立，为什么？因为4可以被分解为2*2,2<=sqrt(4),如果还能被分解为2则必然i才到2，到不了4，到了4的时候前面的递归已经把2分解完了，也就是说以这样的方式递归，则完全无需考虑i本身是非质因数，因为它必然不会被除尽（num%i ==0必然不会成立）