题解 | #质数因子#

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

/**
 * @author hll[yellowdradra@foxmail.com]
 * @since 2023-03-13 12:34
 **/
public class Main {

    public static List<Integer> PRIME_LIST;

    static {
        PRIME_LIST = new ArrayList<>();
        // 根据阴性素数定理 只有2和3是连起来的两个素数 
        //比较特殊 我们先把它们放进去
        PRIME_LIST.add(2);
        PRIME_LIST.add(3);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        // 质因数列表
        List<String> primeFactorList = new ArrayList<>();
        calcPrimeFactor(n, primeFactorList);
        System.out.println(String.join(" ", primeFactorList));
    }

    public static void calcPrimeFactor(int n, List<String> list) {
        // 快速判断一个数是否为质数
        // 如果是质数，则递归结束
        if (isPrimeQuickly(n)) {
            list.add(String.valueOf(n));
            return;
        }
        // 遍历质数列表(升序)
        for (int i = 0; i < PRIME_LIST.size(); i++) {
            int prime = PRIME_LIST.get(i);
            // 如果能被整除 则这个质数为质因子
            if (n % prime == 0) {
                list.add(String.valueOf(prime));
                calcPrimeFactor(n / prime, list);
                break;
            } else {
                // 寻找下一个质数 找到就将其放入质数列表
                // 开始做这道题的时候用欧拉筛法 初始化1到2*10^9+14的质数集合 然后可以非常快的分解质因数
                // 但是初始化时间太长了 要20秒 仔细想想 分解质因数的时候 n是爆发式缩小的(约等于阶乘)
                // 所以我们每次只贪一个质数 这个质数能分解完最好 分解不完 再算下一个
                int j;
                for (j = PRIME_LIST.get(PRIME_LIST.size() - 1) + 1; !isPrimeQuickly(j); j++) {
                }
                // 将找到的这个质数 加到质数列表尾部 保证质数序列是升序的
                PRIME_LIST.add(PRIME_LIST.size(), j);
            }
        }
    }

    public static boolean isPrimeQuickly(int n) {
        if (n == 2 || n == 3) {
            return true;
        }
        // 等价于 n % 2 == 0 即n是偶数
        if ((n & 1) == 0 || n <= 1) {
            return false;
        }
        int r = n % 6;
        if (r != 5 && r != 1) {
            return false;
        }
        int sqrt = (int) Math.sqrt(n);
        // 保证i为奇数
        for (int i = 5; i <= sqrt; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}