C語言尋找完數（Perfect Number）：1000 以內完數個數與分解式輸出

什麼是完數？

完數（Perfect Number）：一個正整數若等於其所有真因子（不含自身）之和，則稱為完數。
例：6 的真因子為 1、2、3，1+2+3=6，故 6 是完數。

數學背景補充

• 已知完數皆為偶數（至今未發現奇完數）
• 歐幾里得證明：若 2^p - 1 為質數（梅森質數），則 2^(p-1) × (2^p - 1) 為完數
• 1000 以內僅有 3 個完數：6、28、496

程式碼實作與優化

原始版本（教學示範）

int i, j, m = 0, x = 0, s, a[100];
for (i = 2; i < 1000; i++) {
    s = 0; j = 0; x = 0;
    while (++j < i) {
        if (i % j == 0) {
            s = s + j;
            a[x++] = j;
        }
    }
    if (s == i) {
        printf("%d=", i);
        for (m = 0; m < x; m++) {
            printf("%d", a[m]);
            if (m != x - 1) printf("+");
        }
        printf("\n");
    }
}

優化版本：減少迴圈次數

因子成對出現，只需檢查至 sqrt(i)：

#include <stdio.h>
#include <math.h>

int main() {
    int count = 0;
    for (int num = 2; num <= 1000; num++) {
        int sum = 1;  // 1 是所有大於 1 整數的因子
        int factors[50], fc = 0;
        factors[fc++] = 1;

        // 只檢查到 sqrt(num)
        for (int j = 2; j <= (int)sqrt(num); j++) {
            if (num % j == 0) {
                sum += j;
                factors[fc++] = j;
                int pair = num / j;
                if (pair != j) {  // 避免完全平方數重複計算
                    sum += pair;
                    factors[fc++] = pair;
                }
            }
        }

        if (sum == num && num != 1) {  // 1 不是完數
            count++;
            // 將因子排序後輸出
            // 簡單氣泡排序
            for (int i = 0; i < fc - 1; i++)
                for (int k = 0; k < fc - 1 - i; k++)
                    if (factors[k] > factors[k + 1]) {
                        int t = factors[k];
                        factors[k] = factors[k + 1];
                        factors[k + 1] = t;
                    }

            printf("%d = ", num);
            for (int i = 0; i < fc; i++) {
                printf("%d", factors[i]);
                if (i != fc - 1) printf(" + ");
            }
            printf("\n");
        }
    }
    printf("1000 以內共有 %d 個完數。\n", count);
    return 0;
}

執行結果

6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
1000 以內共有 3 個完數。

複雜度比較

學習重點

• 因子成對性：j 是因子 ⇒ num/j 也是因子，利用此性質大幅減少迴圈
• 邊界條件：完全平方數（如 36=6×6）避免重複加總
• 輸出格式化：因子排序、分隔符號處理（最後一個不印 +）
• 陣列大小估算：1000 以內數字因子數極少，int factors[50] 綽綽有餘

延伸思考：若改為「找出 10000 以內所有完數」，窮舉法會明顯變慢，此時優化版優勢更明顯。下一個完數是 8128（在 10000 內），再下一個是 33550336。