试除法分解质因数

初始版本

public List<Integer> getPrimeList(int num) {
    List<Integer> factors = new ArrayList<>();
    // 0,1不为质数，从2开始遍历
    for (int i = 2; i * i <= num; i++) {         // 优化点：只遍历到 sqrt(num)
        if (num % i == 0) {                      // 能整除，i 为 num 的因数
            factors.add(i);
            while (num % i == 0) num /= i;
        }
    }
    if (num > 1) factors.add(num);
    return factors;
}

从最小质数 2 开始遍历，并将 i 除尽，保证较大的合数被较小的质数分解。

例如：遍历到 4 时，此时 num 已没有因数 2，所以 num % 4 != 0 会跳过。

加一次列表，再试除，保证质因数列表不重复。

优化版本

public List<Integer> getPrimeList(int num) {
    List<Integer> factors = new ArrayList<>();
    if (num < 2) return factors;
    // 特殊处理
    if (num % 2 == 0) {
        factors.add(2);
        while (num % 2 == 0) num /= 2;
    }

    // 步长为2，只遍历奇数
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0) {
            factors.add(i);
            while (num % i == 0) num /= i;
        }
    }

    if (num > 1) factors.add(num);
    return factors;
}

所有质数中只有 2 为偶数，先处理掉 2，接下来只遍历奇数。

预处理版本

public List<Integer> getPrimeList(int num) {
    List<Integer> factors = new ArrayList<>();
    for (int prime = 2; prime < isPrime.length; prime++) {
        if (!isPrime[prime]) continue;
        if (prime * prime > num) break;
        if (num % prime == 0) {
            factors.add(prime);
            while (num % prime == 0) num /= prime;
        }
    }
    
    if (num > 1) factors.add(num);
    return factors;
}

通过质数筛预处理，可以看这篇博客：质数筛。

假设已预处理得到一个 isPrime 数组，只需要遍历质数，判断是否为因数即可。

要点：isPrime 数组长度需要大于 num 开根。