Java 遞歸演算法實作質因數分解：從基礎邏輯到程式碼優化

展示如何使用遞歸將長整數分解為質因數，程式碼簡潔易懂，適合學習遞歸與數學運算邏輯。

核心演算法

private static List<Long> getFactors(long n, long factor) {
  // 尋找最小能整除 n 的因子 (2, 3, 5, 7, 9...)
  while (n % factor != 0 && factor < n) {
    factor = factor < 2 ? 2 : factor == 2 ? 3 : factor + 2;
  }

  List<Long> result;
  if (factor >= n) {          // 因子已達 n，n 本身為質數
    result = new ArrayList<Long>();
  } else {                    // 找到因子，遞歸分解 n/factor
    result = getFactors(n / factor, factor);
  }
  result.add(factor);         // 將當前因子加入結果
  return result;
}

執行範例

public static void main(String[] args) {
  List<Long> factors = getFactors(5555566666L, 2);
  System.out.println(factors); // 輸出: [2, 7, 11, 13, 19, 53, 79, 181]
}

演算法解析

1. 因子搜尋優化：跳過偶數 (2 之後只檢查奇數)，減少迴圈次數。
2. 遞歸終止條件：當 factor >= n 表示剩餘值為質數，建立空列表並回傳。
3. 結果收集順序：遞歸回溯時由小到大加入因子，最終列表為遞增序列。

複雜度

時間複雜度約 O(√n)，空間複雜度取決於質因數個數 (遞歸深度)。對於 64 位長整數完全足夠。