题解 | 分解质因数-Java

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        scanner.close();

        List<Long> factors = primeFactorization(n);

        // 输出结果
        for (int i = 0; i < factors.size(); i++) {
            if (i > 0) {
                System.out.print(" ");
            }
            System.out.print(factors.get(i));
        }
    }

    /**
     * 对n进行质因数分解
     * @param n 要分解的数
     * @return 质因数列表，按从小到大排序
     */
    private static List<Long> primeFactorization(long n) {
        List<Long> factors = new ArrayList<>();

        // 处理2的情况（唯一的偶质数）
        while (n % 2 == 0) {
            factors.add(2L);
            n /= 2;
        }

        // 处理奇数的情况，从3开始
        for (long i = 3; i * i <= n; i += 2) {
            while (n % i == 0) {
                factors.add(i);
                n /= i;
            }
        }

        // 如果剩余的n本身是一个质数（大于2）
        if (n > 1) {
            factors.add(n);
        }

        return factors;
    }
}