题解 | #质数因子#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Integer input = Integer.parseInt(scanner.nextLine());
        StringBuilder stringBuilder = new StringBuilder();

        findMinPrimeNumber(input, 2, stringBuilder);
        System.out.println(stringBuilder);
    }

    private static void findMinPrimeNumber(Integer input, int lastPrimeNumber,
                                           StringBuilder stringBuilder) {
        if (isPrimeNumber(input)) {
            stringBuilder.append(input).append(" ");
            return;
        }
        for (int i = lastPrimeNumber; i < input; i++) {
            if (!isPrimeNumber(i)) {
                continue;
            }
            if (input % i == 0) {
                stringBuilder.append(i).append(" ");
                input = input / i;
                lastPrimeNumber = i;
                findMinPrimeNumber(input, lastPrimeNumber, stringBuilder);
                return;
            }
        }
        return;
    }

    public static boolean isPrimeNumber(int num) {
        if (num <= 3) {
            return true;
        }
        //针对大于等于3的自然数，如果这个数是素数，那么一定满足 6x + 1或者 6x - 1。x是大于等于1的自然数
        //比如 11 就等于 6x2-1。5就等于6x1-1，7就等于6x1+1。
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
        //如果一个数a是合数，那么假设其可以分解为x,y.即 x * y = a.
        //假设 x <= y,那么一定会满足 x <= √a 且 y>= √a。
        //所以只要从2判断到√a，发现数a无法被任何数整除，那么就证明数a是素数
        int sqrt = (int) Math.sqrt(num);
        for (int i = 2; i <= sqrt; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}