Java 正整數分解質因數：修復邏輯錯誤與輸出格式優化

原代碼問題分析

public class Decomposition {
    public static void main(String[] args) {
        String str = "";
        int j;
        Scanner sc = new Scanner(System.in);
        int i = sc.nextInt();
        int k = sc.nextInt(); // 💥 錯誤：多讀了一個輸入，且未使用
        
        for (j = 2; j <= i; j++) {
            if (i % j == 0) {
                str = str + j + "*";
                i = i / j;
                j--; // 關鍵：同一因子可能重複，需重新嘗試當前 j
            }
        }
        str = str + j; // 💥 錯誤：循環結束 j = 原數+1，非最後因子
        System.out.println("分解結果是:" + k + "=" + str); // k 是第二個輸入數
    }
}

核心邏輯錯誤

1. 多讀輸入：int k = sc.nextInt() 導致程序等待第二個數，用戶以為無反應
2. 輸出變量錯誤：用 k（第二個輸入）而非原始數 i（已被修改）
3. 結果拼接錯誤：循環後 j 值不再是因子，末尾多加一個錯誤數字
4. 格式問題：尾部多餘 * 或缺少 *

修正版代碼

import java.util.Scanner;

public class Decomposition {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("請輸入一個正整數: ");
        
        if (!sc.hasNextInt()) {
            System.out.println("輸入無效，請輸入整數");
            return;
        }
        
        int n = sc.nextInt();
        if (n <= 1) {
            System.out.println("請輸入大於 1 的正整數");
            return;
        }
        
        int original = n; // 保存原始值用於輸出
        StringBuilder sb = new StringBuilder(); // 效率優於 String 拼接
        
        for (int factor = 2; factor <= n; factor++) {
            while (n % factor == 0) { // while 替代 if+j--，更清晰
                if (sb.length() > 0) {
                    sb.append("*"); // 非首個因子前加 *
                }
                sb.append(factor);
                n /= factor;
            }
        }
        
        System.out.println("分解結果是: " + original + "=" + sb.toString());
        sc.close();
    }
}

關鍵改進點

運行示例

請輸入一個正整數: 90
分解結果是: 90=2*3*3*5

請輸入一個正整數: 17
分解結果是: 17=17

請輸入一個正整數: 100
分解結果是: 100=2*2*5*5

進階優化：只遍歷到 sqrt(n)

for (int factor = 2; factor * factor <= n; factor++) {
    while (n % factor == 0) {
        // ... 同前
    }
}
if (n > 1) { // 剩餘 n 是質數
    if (sb.length() > 0) sb.append("*");
    sb.append(n);
}

時間複雜度從 O(n) 降至 O(√n)，大數分解顯著加速。

總結

• ✅ 只讀一個輸入，保存原始值
• ✅ 用 while 替代 if + j--
• ✅ StringBuilder 構建結果字符串
• ✅ 邊界處理：n <= 1、質數輸入