正整數質因數分解 Java 實作：遞迴與迭代兩種寫法

問題描述

輸入一個正整數 N，輸出其質因數分解式，例如 10=2*5、60=2*2*3*5。

遞迴版本（原始碼修正版）

import javax.swing.JOptionPane;

public class PrimeFactorization {
    public static void main(String[] args) {
        String input = JOptionPane.showInputDialog("請輸入正整數 N（輸入 exit 結束）：");
        if (input == null || input.equalsIgnoreCase("exit")) return;

        try {
            int n = Integer.parseInt(input.trim());
            if (n <= 1) {
                JOptionPane.showMessageDialog(null, "請輸入大於 1 的正整數");
                return;
            }
            System.out.print(n + " = ");
            factorize(n);
            System.out.println();
        } catch (NumberFormatException e) {
            JOptionPane.showMessageDialog(null, "輸入格式錯誤，請輸入整數");
        }
    }

    /**
     * 遞迴分解質因數，直接輸出到標準輸出
     */
    private static void factorize(int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                System.out.print(i + "*");
                factorize(n / i);
                return; // 關鍵：找到最小質因子後立即遞迴並返回，避免重複輸出
            }
        }
        // 迴圈結束仍未 return，表示 n 本身是質數
        System.out.print(n);
    }
}

迭代版本（生產環境推薦）

public static String factorizeIterative(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            sb.append(i).append('*');
            n /= i;
        }
    }
    if (n > 1) sb.append(n);
    else if (sb.length() > 0) sb.setLength(sb.length() - 1); // 移除尾端 *
    return sb.toString();
}

關鍵細節對比

常見錯誤提醒

• ❌ 迴圈條件寫 i <= n/2 → 效率極差，正確為 i * i <= n。
• ❌ 遞迴缺少 return → 導致重複輸出（如 12 輸出 2*2*3*3）。
• ❌ 未處理 N=1 或 N<1 的邊界情況。

擴展：大數分解

若 N 超過 long 範圍，需引入 BigInteger 搭配 Pollard's Rho 演算法，單純試除法不再適用。