C語言尋找區間內完美數：預計算與查表法高效解法

編輯：關於C語言

完美數指等於其真因子和的正整數 (如 6=1+2+3, 28=1+2+4+7+14)。已知完美數極稀少且增長極快，本文採用預計算已知完美數配合區間查詢，實現 O(1) 查詢效能的 C 程式解法。

完美數數學特性

歐幾里得證明：2^(p-1)(2^p-1) 為完美數，若 2^p-1 為梅森質數
歐拉證明：所有偶數完美數皆為此形式
奇數完美數：至今未發現，若存在則 > 10^1500
前 8 個完美數：6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128

查表法完整實作

#include <stdio.h>
#include <stdint.h>

int main() {
    // 已知完美數 (64位元範圍內僅 8 個)
    const uint64_t perfect[] = {
        6ULL, 28ULL, 496ULL, 8128ULL,
        33550336ULL, 8589869056ULL,
        137438691328ULL, 2305843008139952128ULL
    };
    const int COUNT = sizeof(perfect) / sizeof(perfect[0]);

    uint64_t m, n;
    while (scanf("%llu %llu", &m, &n) == 2) {
        if (m == 0 && n == 0) break;
        if (m > n) { uint64_t t = m; m = n; n = t; }  // 確保 m <= n

        int found = 0;
        for (int i = 0; i < COUNT; i++) {
            if (perfect[i] >= m && perfect[i] <= n) {
                if (found) printf(" ");
                printf("%llu", perfect[i]);
                found = 1;
            }
        }
        if (!found) printf("No");
        printf("\n");
    }
    return 0;
}

原始碼邏輯分析與改進

原始碼使用雙重迴圈尋找邊界索引 i、j，再輸出 [j, i) 區間。改進版直接單迴圈篩選，邏輯更清晰、避免邊界錯誤。

關鍵改進點

型別升級：使用 uint64_t 支援第 8 個完美數 (2.3×10¹⁸)
輸入交換：自動處理 m > n 情況
格式化輸出：%llu 對應 unsigned long long
終止條件：明確檢查 m==0 && n==0

動態計算法替代方案

若不使用查表，需對區間每個數測試是否為完美數：

// 測試單一數是否為完美數 - O(√n)
int is_perfect(uint64_t x) {
    if (x <= 1) return 0;
    uint64_t sum = 1;
    for (uint64_t i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            sum += i;
            if (i != x / i) sum += x / i;
        }
    }
    return sum == x;
}

但對大區間極其低效，查表法在已知完美數極少時為最優解。

梅森質數生成完美數

// 已知梅森質數指數 p (前 8 個)
int mersenne_p[] = {2, 3, 5, 7, 13, 17, 19, 31};

uint64_t gen_perfect(int p) {
    return ((1ULL << (p-1)) * ((1ULL << p) - 1));
}
// 注意：p=31 時 1ULL<<31 溢位 32 位元，需用 128 位元或大數庫

大數完美數處理 (超過 64 位元)

第 9 個完美數有 37 位數字，需大數庫：

// 使用 GMP 庫
#include <gmp.h>

void gen_perfect_gmp(mpz_t result, int p) {
    mpz_t mersenne;
    mpz_init(mersenne);
    mpz_ui_pow_ui(mersenne, 2, p);  // 2^p
    mpz_sub_ui(mersenne, mersenne, 1);  // 2^p - 1
    mpz_mul_2exp(result, mersenne, p-1);  // * 2^(p-1)
    mpz_clear(mersenne);
}

效能比較

方法	預處理	單次查詢	適用場景
查表法 (本文)	O(1)	O(1) ~ 8 次比較	已知完美數範圍內最優
動態試除	無	O(n√n)	教學驗證、未知完美數
梅森質數生成	O(p²) 大數運算	O(1) 查表	需生成超大完美數