题解 | #质数因子#

import java.util.ArrayList;
import java.util.Scanner;
public class Main {
     public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int num = scanner.nextInt();
            if (num >1 ){
               ArrayList arrayList = new ArrayList();
                arrayList = getPrimeFactors(num,arrayList);
                StringBuffer stringBuffer = new StringBuffer();
                for (int i = 0; i < arrayList.size(); i++) {
                    stringBuffer.append(arrayList.get(i)).append(" ");
                }
                System.out.println(stringBuffer.toString().trim());
            }
        }
    }
    private static ArrayList getPrimeFactors(int num,ArrayList arrayList) {
            ArrayList primes = getPrimes(num);
            for (int i = 0; i < primes.size(); i++) {
                Integer integer = primes.get(i);
                if (num % integer == 0){
                    arrayList.add(integer);
                    num = num/integer;
                    if (num != 1){
                        // 使用递归的方式实现短除法
                        getPrimeFactors(num,arrayList);
                        // 递归出口，否则死循环会造成栈溢出
                        break;
                    }else
                        return arrayList;
                }
            }
            return arrayList;
    }
    private static ArrayList getPrimes(int num) {
        ArrayList arrayList = new ArrayList();
        boolean flag = ifPrimeNumber(num);
        if (flag){
            arrayList.add(num);
        }else{
            for (int i = 2; i <= Math.sqrt(num); i++) {
                if (num % i == 0 && ifPrimeNumber(i)){
                    arrayList.add(i);
                }
            }
        }
        return arrayList;
    }
    private static boolean ifPrimeNumber(int num) {
        boolean flag = true;
        if (num == 2 ) return true;
        else {
            for (int i = 2; i <= Math.sqrt(num); i++) {
                if (num % i ==0){
                    flag = false;
                    break;
                }
            }
        }
        return flag;
    }
}

解题思路是：先判断输入的num是否为素数，如果不是素数，则保存所有能整除它的质数，如果是素数，保存自身即可。然后使用短除法，求出符合题意的质数因子。短除法使用递归的方式实现，后接break的作用是及时退出递归，因为层层递归的目的只是为了保存质数因子，保存后即可退出，不需要再执行外层递归，不然外层递归因没有终止条件将一直执行，直到栈溢出。当使用短除法求得num为1时，说明所有质数因子已经找完，直接返回保存的质数因子。