Java 練習題：找出 1000 以內的所有完數（完美數）

題目：完數（Perfect Number）查找

定義：一個正整數如果恰好等於它的真因子（不包含自身的因子）之和，則稱為「完數」或「完美數」。例如：6 = 1 + 2 + 3，28 = 1 + 2 + 4 + 7 + 14。

解題思路

1. 遍歷 2 到 999 的每個整數 i
2. 對每個 i，找出所有小於 i 的因子 j（即 i % j == 0）
3. 累加所有因子之和 sum
4. 若 sum == i，則輸出該完數
5. 統計並輸出總個數

完整 Java 代碼實現

public class PerfectNumberFinder {
    public static void main(String[] args) {
        int count = 0;
        System.out.println("1000 以內的完數有：");
        
        for (int i = 2; i < 1000; i++) {
            int sum = 0;
            // 優化：只需遍歷到 sqrt(i)，成對收集因子
            for (int j = 1; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    sum += j;
                    int paired = i / j;
                    if (paired != j && paired != i) { // 排除自身與重複因子
                        sum += paired;
                    }
                }
            }
            if (sum == i) {
                System.out.println(i);
                count++;
            }
        }
        System.out.println("1000 以內的完數一共有 " + count + " 個。");
    }
}

運行結果

1000 以內的完數有：
6
28
496
1000 以內的完數一共有 3 個。

算法優化說明

原始雙層循環時間複雜度為 O(n²)。優化版利用因子成對出現特性（若 j 是因子，則 i/j 也是因子），將內層循環縮減至 sqrt(i)，複雜度降為 O(n√n)。對於 1000 以內數據量雖無明顯差異，但對擴展至百萬級數據至關重要。

數學延伸知識

• 目前已知完數皆為偶數，且與梅森素數（Mersenne Prime）密切相關：若 2^p - 1 是素數，則 (2^p - 1) × 2^(p-1) 是完數
• 前幾個完數：6, 28, 496, 8128, 33550336...
• 截至 2024 年，僅發現 51 個完數，最大完數超過 4900 萬位數字
• 未解之謎：是否存在奇完數？目前未發現，也未證明不存在

常見面試變體

• 判斷單個輸入數是否為完數
• 輸出完數及其因子分解式（如 6 = 1 + 2 + 3）
• 使用遞歸或流式 API (Java 8+) 實現