Java 實現質因子分解與最小公倍數計算：算法優化與大數處理

質因子分解算法

基礎試除法 (適用于 int 範圍)

public static List primeFactors(int n) {
    List factors = new ArrayList<>();
    if (n <= 1) return factors;
    
    // 提取因子 2
    while (n % 2 == 0) {
        factors.add(2);
        n /= 2;
    }
    
    // 奇數因子，只需試除到 sqrt(n)
    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            factors.add(i);
            n /= i;
        }
    }
    
    // 剩餘 n > 1 則為質數
    if (n > 1) factors.add(n);
    
    return factors;
}

// 測試
primeFactors(60);  // [2, 2, 3, 5]
primeFactors(97);  // [97] (質數)
primeFactors(100); // [2, 2, 5, 5]

優化版：預計算質數表 (Sieve of Eratosthenes)

public class PrimeFactorizer {
    private final List primes;
    
    public PrimeFactorizer(int limit) {
        // 埃氏篩法生成質數表
        boolean[] isPrime = new boolean[limit + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= limit; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= limit; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        primes = new ArrayList<>();
        for (int i = 2; i <= limit; i++) if (isPrime[i]) primes.add(i);
    }
    
    public List factorize(int n) {
        List factors = new ArrayList<>();
        for (int p : primes) {
            if ((long) p * p > n) break;
            while (n % p == 0) {
                factors.add(p);
                n /= p;
            }
        }
        if (n > 1) factors.add(n);
        return factors;
    }
}

大數分解：Pollard's Rho 算法 (BigInteger)

public class PollardRho {
    private static final SecureRandom RANDOM = new SecureRandom();
    
    public static List factor(BigInteger n) {
        List factors = new ArrayList<>();
        factorRec(n, factors);
        Collections.sort(factors);
        return factors;
    }
    
    private static void factorRec(BigInteger n, List factors) {
        if (n.equals(BigInteger.ONE)) return;
        if (n.isProbablePrime(20)) { // Miller-Rabin 檢測
            factors.add(n);
            return;
        }
        
        BigInteger d = pollardRho(n);
        factorRec(d, factors);
        factorRec(n.divide(d), factors);
    }
    
    private static BigInteger pollardRho(BigInteger n) {
        if (n.mod(BigInteger.TWO).equals(BigInteger.ZERO)) return BigInteger.TWO;
        if (n.mod(BigInteger.valueOf(3)).equals(BigInteger.ZERO)) return BigInteger.valueOf(3);
        
        BigInteger c = new BigInteger(n.bitLength(), RANDOM).mod(n);
        BigInteger x = new BigInteger(n.bitLength(), RANDOM).mod(n);
        BigInteger y = x;
        BigInteger d = BigInteger.ONE;
        
        while (d.equals(BigInteger.ONE)) {
            x = x.multiply(x).add(c).mod(n);
            y = y.multiply(y).add(c).mod(n);
            y = y.multiply(y).add(c).mod(n);
            d = x.subtract(y).abs().gcd(n);
        }
        return d.equals(n) ? pollardRho(n) : d; // 重試
    }
}

最小公倍數 (LCM) 計算

核心公式：LCM(a, b) = a * b / GCD(a, b)

// 最大公約數 - 輾轉相除法 (歐幾里得算法)
public static long gcd(long a, long b) {
    while (b != 0) {
        long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// 最小公倍數
public static long lcm(long a, long b) {
    if (a == 0 || b == 0) return 0;
    return Math.abs(a / gcd(a, b) * b); // 先除後乘防溢出
}

// 多數 LCM
public static long lcm(long... numbers) {
    long result = 1;
    for (long n : numbers) {
        result = lcm(result, n);
        if (result == 0) return 0;
    }
    return result;
}

// 測試
lcm(6, 8);      // 24
lcm(3, 5, 7);   // 105
lcm(12, 18, 24); // 72

大數 LCM (BigInteger)

public static BigInteger lcm(BigInteger a, BigInteger b) {
    if (a.equals(BigInteger.ZERO) || b.equals(BigInteger.ZERO)) 
        return BigInteger.ZERO;
    BigInteger gcd = a.gcd(b);
    return a.divide(gcd).multiply(b); // 先除後乘
}

性能基準對比 (JMH 參考)

實戰應用場景

• 分數運算：通分用 LCM，約分用 GCD
• 定時任務調度：多個周期任務同步觸發時間 = LCM(周期們)
• 齒輪/齒輪箱設計：齒數比簡化、嚙合週期
• 密碼學：RSA 模數分解攻擊、大質數生成
• 信號處理：採樣率轉換、諧波分析

完整工具類

public final class MathUtils {
    private MathUtils() {}
    
    // GCD
    public static long gcd(long a, long b) {
        a = Math.abs(a); b = Math.abs(b);
        while (b != 0) { long r = a % b; a = b; b = r; }
        return a;
    }
    
    // LCM
    public static long lcm(long a, long b) {
        if (a == 0 || b == 0) return 0;
        return Math.abs(a / gcd(a, b) * b);
    }
    
    public static long lcm(long... nums) {
        long res = 1;
        for (long n : nums) { res = lcm(res, n); if (res == 0) return 0; }
        return res;
    }
    
    // 質因子分解 (int)
    public static List primeFactors(int n) {
        List f = new ArrayList<>();
        if (n <= 1) return f;
        while ((n & 1) == 0) { f.add(2); n >>= 1; }
        for (int i = 3; i * i <= n; i += 2) {
            while (n % i == 0) { f.add(i); n /= i; }
        }
        if (n > 1) f.add(n);
        return f;
    }
    
    // 大數分解入口
    public static List factorBig(BigInteger n) {
        return PollardRho.factor(n);
    }
}

質因子分解與 LCM/GCD 是數論基礎算法，掌握從試除法到 Pollard's Rho 的演進、防溢出技巧與大數處理，可應對從基礎運算到密碼學級別的計算需求。