OpenJudge 完數查找問題：C++ 解法與常見錯誤分析

題目要求

輸入多個整數 n（以 0 結束），對每個 n 輸出不大於 n 的所有完數（完數 = 所有真因子之和等於自身，如 6=1+2+3）。輸出格式：n: 完數1 完數2 ...。

原代碼錯誤分析

• 邏輯完全偏離：計算階乘、雙重循環判斷乘積，與完數定義無關。
• 未正確讀取多組輸入，數組處理混亂。
• 未預先計算完數，導致重複計算效率低。

正確解法思路

1. 預計算範圍內（如 10000）所有完數存入容器。
2. 讀取每個 n，遍歷完數列表輸出 ≤ n 的值。

參考代碼 (C++)

#include <cstdlib>
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

const int MAX = 10000;

int main() {
    vector<int> perfect;
    for (int i = 2; i < MAX; ++i) {
        int sum = 0;
        for (int j = 1; j <= i / 2; ++j)
            if (i % j == 0) sum += j;
        if (sum == i) perfect.push_back(i);
    }

    int n;
    while (cin >> n && n != 0) {
        cout << n << ":";
        for (int p : perfect) {
            if (p <= n) cout << " " << p;
            else break;
        }
        cout << endl;
    }
    return EXIT_SUCCESS;
}

關鍵優化

• 因子遍歷只需到 i/2，減少循環次數。
• 預計算避免重複判斷，滿足 1000ms 時限。