题解 | #质数因子#

import java.util.Scanner;
import java.util.ArrayList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int num = in.nextInt();
            int[] arr = {0, num};
            ArrayList<Integer> arrl = new ArrayList<Integer> ();
            /*
                num的质因子<=num/2或者是num本身
                使用arrayList存储质因子
                首先判断num是否为质数，是的话将num写入arrayList
            */
            while (arr[0] != 1) {
                getFactor(arr, arr[1]);

                if (arr[0] != 1) {
                    arrl.add(arr[0]);
                } else {
                    arrl.add(arr[1]);
                }
            }

            for (int i = 0; i < arrl.size() - 1; i++) {
                System.out.print(arrl.get(i));
                System.out.print(' ');
            }
            System.out.print(arrl.get(arrl.size() - 1));

        }
    }

    //boolean isPrime,判断是否为质数，输入整数，返回布尔值
    public static boolean isPrime(int num) {
        int sqrtNum = (int)Math.sqrt(num);
        for (int i = 2; i <= sqrtNum; i++) {
            if (num % i == 0) {
                return false;
            } else {
                continue;
            }
        }
        return true;
    }

    //void getFactor,计算一个数的最小质因子
    public static void getFactor(int[] arr, int num) {
        if (isPrime(num)) {
            arr[0] = 1;
            arr[1] = num;
        } else {
            int sqrtNum = (int)Math.sqrt(num);
            for (int i = 2; i <= sqrtNum; i++) {
                if (isPrime(i)) {
                    if (num % i == 0) {
                        arr[0] = i;
                        arr[1] = num / i;
                        break;
                    } else {
                        continue;
                    }
                }
            }
        }
    }

}