C 語言完數查找：n 以內所有完美數的枚舉與優化 (因子和等於自身)

問題描述

找出給定 n 以內所有完數：真因子（不含自身）之和等於自身的數。如 6 = 1+2+3，28 = 1+2+4+7+14。核心考點：因子枚舉優化、因子配對性質、已知完數數學結構。

原代碼：暴力枚舉 1 到 i-1

#include <stdio.h>

int main() {
    int i, j, n, sum, k = 0, perfect[1000];
    printf("請輸入整數: ");
    scanf("%d", &n);

    for (i = 1; i <= n; i++) {
        sum = 0;
        for (j = 1; j < i; j++) {  // ❌ 優化至 √i
            if (i % j == 0) sum += j;
        }
        if (sum == i) perfect[k++] = i;
    }
    // 輸出...
}

優化一：因子配對枚舉至 √i

因子成對出現：若 j 是因子，則 i/j 也是因子。枚舉至 √i 即可獲取所有因子對。

int sum_proper_divisors(int n) {
    if (n <= 1) return 0;
    int sum = 1;  // 1 永遠是真因子 (n>1)
    for (int j = 2; j * j <= n; j++) {
        if (n % j == 0) {
            sum += j;
            int paired = n / j;
            if (paired != j) sum += paired;  // 避免平方數重複加
        }
    }
    return sum;
}

優化二：歐拉-歐幾里得定理 (完數結構)

定理：所有偶數完數形式為 2^(p-1) × (2^p - 1)，其中 2^p - 1 是梅森素數。
截至目前未發現奇完數（若存在則 > 10¹⁵⁰⁰）。

已知前幾個完數對應梅森素數指數 p：

極致優化：直接生成完數 (O(已知完數個數))

void find_perfect_numbers_fast(int n) {
    // 已知前 8 個完數 (64位範圍內)
    long long perfects[] = {6, 28, 496, 8128, 33550336,
                            8589869056, 137438691328, 2305843008139952128};
    int count = sizeof(perfects)/sizeof(perfects[0]);

    printf("%d 以內的完數:\n", n);
    for (int i = 0; i < count; i++) {
        if (perfects[i] <= n) printf("%lld ", perfects[i]);
        else break;
    }
    printf("\n");
}

複雜度對比

篩法預計算因子和 (通用批量優化)

void sieve_divisor_sum(int n, int *sum) {
    for (int i = 1; i <= n; i++) sum[i] = 1;  // 1 是所有數>1的因子
    sum[1] = 0;  // 1 無真因子
    for (int i = 2; i <= n; i++) {
        for (int j = i*2; j <= n; j += i) {
            sum[j] += i;  // i 是 j 的真因子
        }
    }
}
// 使用後 sum[i] 即為 i 的真因子和，O(n log n) 一次性算完所有

總結

完數查找展示了從暴力枚舉到數學結構利用的算法昇華。關鍵收穫：

• 因子配對枚舉至 √n 是通用因子和計算優化；
• 歐拉-歐幾里得定理 給出偶完數完整結構：2^(p-1)(2^p-1)，2^p-1 為梅森素數；
• 64 位範圍內僅 8 個完數，**直接查表 O(1) 為終極優化**；
• 批量查詢用篩法預計算 O(n log n) 一次性解決所有；
• 奇完數至今未發現，若存在極大，工程中可忽略。