C語言尋找完全數（完美數）：1000以內因子和等於自身的數

數學定義

完全數（Perfect Number），又稱完美數，是指其所有真因子（不包括自身的約數）之和等於自身的自然數。最小的完全數是 6（1+2+3=6），其次是 28（1+2+4+7+14=28）、496、8128……

優化實現代碼

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

// 計算真因子和（優化至 √n）
int sum_proper_divisors(int n) {
    if (n <= 1) return 0;
    int sum = 1;  // 1 是所有 n>1 的真因子
    int limit = (int)sqrt(n);

    for (int i = 2; i <= limit; i++) {
        if (n % i == 0) {
            sum += i;
            int complement = n / i;
            if (complement != i) {  // 避免平方數重複加加
                sum += complement;
            }
        }
    }
    return sum;
}

int main() {
    printf("1000 以內的完全數及其分解：\n");
    for (int i = 2; i <= 1000; i++) {
        if (sum_proper_divisors(i) == i) {
            // 格式化輸出：6 = 1 + 2 + 3
            printf("%d = 1", i);
            for (int j = 2; j < i; j++) {
                if (i % j == 0) printf(" + %d", j);
            }
            putchar('\n');
        }
    }
    return 0;
}

算法優化詳解

因子配對原理

若 i 是 n 的因子，則 n/i 也是因子。只需遍歷到 √n，成對累加，時間複雜度從 O(n) 降為 O(√n)。

特殊情況處理

• n=1：無真因子，和為 0
• 平方數（如 16=4×4）：配對因子相同，只加一次

執行結果

1000 以內的完全數及其分解：
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248

數學拓展：歐拉-歐幾里得定理

所有偶數完全數均符合形式：2^(p-1) × (2^p - 1)，其中 2^p - 1 是梅森質數（Mersenne Prime）。

• p=2 → 2×3 = 6
• p=3 → 4×7 = 28
• p=5 → 16×31 = 496
• p=7 → 64×127 = 8128（超過1000）

截至2024年，僅發現51個梅森質數，對應51個偶數完全數。奇數完全數是否存在仍是數學未解之謎。

工程應用場景

• 密碼學：某些協議利用完全數特性
• 算法面試：考察循環優化、邊界處理、格式化輸出
• 數論研究：驗證梅森質數發現的新完全數

總結

本文修正了原代碼的輸出格式問題（避免重複因子），並引入√n優化策略。理解完全數的數學本質與因子配對規律，不僅能寫出高效代碼，更能觸類旁通解決相關約數問題（如親和數、虧數/盈數判斷）。