题解 | #最大公约数#

// 判断数字是否为质数，改进用根号降低时间复杂度
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> arr = new ArrayList<Integer>();
        get(arr,n);
        if(arr.size() == 0)
            arr.add(n);
        for(int i = 0;i < arr.size();i++){
            System.out.print(arr.get(i)+" ");
        }
    }
    public static void get(ArrayList<Integer> arr,int n) {
        // extern condition:identiy is zhi number
        if(isNumber(n)){
            arr.add(n);
            return;
        } 
        for(int i=2;i<=Math.sqrt(n);i++){
            if(n % i == 0){
                n = n / i;
                arr.add(i);
                break;
            }
        }
        get(arr,n);
    }
    public static boolean isNumber(int n) {
        for(int i = 2;i<=Math.sqrt(n);i++){
            if(n % i == 0)
                return false;
        }
        return true;
    }
}