C語言完美數搜尋：找出 N 以內所有完全數（因子和等於自身）

完全數定義

正整數 n 若等於其所有真因子（不含自身）之和，則為完全數。
已知最小完全數：6 (1+2+3)、28 (1+2+4+7+14)、496、8128...

演算法複雜度分析

• 暴力法：對每個 i (1..N)，檢查 j (1..i-1) 是否為因子 → O(N²)
• 優化：因子成對出現，只需檢查到 √i → O(N√N)
• 本程式採用暴力法，適合 N ≤ 10000 教學示範

完整程式碼（修正邊界）

#include <stdio.h>

int main()
{
    int limit;
    printf("請輸入上限 N: ");
    scanf("%d", &limit);

    printf("%d 以內的完全數：\n", limit);
    int found = 0;
    for (int i = 2; i <= limit; i++) {  // 1 無真因子
        int sum = 0;
        for (int j = 1; j <= i/2; j++) {  // 優化：只需檢查到 i/2
            if (i % j == 0) sum += j;
        }
        if (sum == i) {
            printf("%d ", i);
            found = 1;
        }
    }
    if (!found) printf("無\n");
    printf("\n");
    return 0;
}

執行範例

請輸入上限 N: 10000
10000 以內的完全數：
6 28 496 8128 

數學背景補充

• 歐幾里得證明：2^(p-1) × (2^p - 1) 為完全數，若 2^p - 1 為質數（梅森質數）
• 所有已知完全數皆為偶數，奇完全數存在性未解
• 截至 2024 年僅知 51 個完全數，最大者超過 4900 萬位數

優化版因子求和（√N 法）

int sumDivisors(int n) {
    int sum = 1;  // 1 是所有 n>1 的因子
    for (int d = 2; d*d <= n; d++) {
        if (n % d == 0) {
            sum += d;
            if (d != n/d) sum += n/d;  // 配對因子
        }
    }
    return (n==1) ? 0 : sum;
}