题解 | #质数因子#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            System.out.println(findZhiYinZiList(sc.nextInt()));
        }
    }

    /**
     * 数学知识忘完了，快快补课：
     *      质数（也称素数）：一个自然数，如果只有1和它本身两个约数，这个数叫做质数。
     *      因数（也称约数）：指整数a除以整数b(b≠0) 的商正好是整数而没有余数，称b是a的因数。
     *      质因数：一个数的因数是质数，就叫做这个数的质因数。
     *          若a是b的因数，且a是质数，则称a是b的质因数。例如2，3，5均为30的质因数。6不是质数，所以不算。7不是30的因数，所以也不是质因数。
     *      互质数：公因数只有1的两个非零自然数,叫做。
     *      合数：除了1和它本身还有其它正因数。
     *      1只有正因数1，所以它既不是质数也不是合数。
     * 解题思路：
     *      关键在于只需要检查小于等于sqrt(n)的因子。这是基于以下原理：
     *          如果n有一个因子a（a > 1），那么必然存在另一个因子b（b > 1），使得a * b = n。
     *      这意味着a和b中至少有一个因子不大于sqrt(n)，否则a和b的乘积将大于n（因为a > sqrt(n)且b > sqrt(n)时，a * b > n）。
     *
     *      因此，可以得出结论：如果n有一个大于sqrt(n)的因子，那么它必定还有一个小于等于sqrt(n)的对应因子。
     *      意味着我们只需要检查小于等于sqrt(n)的因子，就可以找到n的所有因子。
     *
     *      通过仅检查小于等于sqrt(n)的因子，我们可以显著减少计算量，提高算法的效率。
     *      在这道题中，我们使用一个for循环检查小于等于sqrt(n)的因子，如果找到一个因子，将其添加到结果中，并相应地更新n的值。
     *      这样，可以确保找到n的所有质因子，同时避免不必要的计算。
     * @param n
     * @return
     */
    private static String findZhiYinZiList(int n) {
        StringBuilder sb = new StringBuilder();

        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                sb.append(i).append(" ");
                n = n / i;
            }
        }

        // 最后的商
        if (n > 1) {
            sb.append(n).append(" ");
        }

        return sb.toString().trim();
    }
}