Java 實作質因數分解演算法完整教學

質因數分解：從數學邏輯到 Java 程式碼

質因數分解是經典的程式設計練習題，能幫助理解迴圈、遞迴與數學邏輯的轉換。本文提供完整的 Java 實作與詳細解析。

演算法邏輯

1. 找到最小的質數 k（從 2 開始）。
2. 若 k == n，分解結束，列印 k。
3. 若 n % k == 0，列印 k，將 n 更新為 n / k，重複步驟 1。
4. 否則 k++，重複步驟 1。

Java 程式碼實作（遞迴版）

import javax.swing.*;

public class PrimeFactorization {
    public void factorize(int n) {
        for (int i = 2; i <= n / 2; i++) {
            if (n % i == 0) {
                System.out.print(i + "*");
                factorize(n / i);
                return; // 找到因子後直接返回，避免重複列印
            }
        }
        System.out.print(n); // n 本身為質數
    }

    public static void main(String[] args) {
        String input = JOptionPane.showInputDialog("請輸入正整數 N（輸入 exit 退出）：");
        try {
            int N = Integer.parseInt(input);
            System.out.print(N + " 分解質因數：" + N + "=");
            new PrimeFactorization().factorize(N);
        } catch (NumberFormatException e) {
            System.err.println("輸入格式錯誤，請輸入整數。");
        }
    }
}

關鍵點說明

• 使用 JOptionPane 進行視窗輸入，適合初學者互動。
• 遞迴呼叫 factorize(n / i) 簡化邏輯，但需注意堆疊深度。
• 迴圈條件 i <= n / 2 可優化為 i * i <= n 提升效能。

進階優化建議

若處理大數字，建議改用試除法優化（只檢查到 sqrt(n)）或引入 Pollard's Rho 等進階演算法。初學階段掌握遞迴邏輯即可。