题解 | 质数因子

import java.util.Scanner;

// 注意类名必须为 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 n = in.nextInt();

            // 从2开始，从左向右遍历质数
            int i = 2;
            while (i <= n) {
                // boolean isZhiShu = true;

                // // 查看i是不是质数
                // for (int j = 2; j < i; ++j) {
                //     if (i % j == 0) {
                //         isZhiShu = false;
                //         break;
                //     }
                // }

                // // i 是质数
                // if (isZhiShu) {
                //     while (n % i == 0) {
                //         System.out.print(i + " ");
                //         n /= i;
                //     }
                // }

                // // 不管i是不是质数，每轮都要++
                // i++;

                // 以上时间复杂度是 O(n^2)，超时
                // 其实不用判断质数，因为是从小到大计算的，如果是合数，早就在之前被拆开了
                
                while (i <= n && n % i == 0) {
                    System.out.print(i + " ");
                    n /= i;
                }
                // 以下if语句，是因为偶数里只有2是质数，所以2以后的质因子全是奇数
                if (i == 2) i++;
                else i += 2;
            }
            System.out.println();
        }
        in.close();
    }
}