C# 判斷完全數：約數之和等於自身的數字

完全數指所有真約數（不含自身）之和等於自身的自然數。最小完全數為 6 (1+2+3)，其次 28 (1+2+4+7+14)、496、8128...

演算法邏輯

1. 遍歷 1 到 n-1，累加所有能整除 n 的數
2. 比較總和與 n 是否相等
3. 若相等，輸出分解式並回傳 true

實作程式碼

public bool IsPerfectNumber(int num) {
    if (num <= 1) return false;
    
    int sum = 0;
    List<int> divisors = new List<int>();
    
    // 優化：只需遍歷到 sqrt(num)
    for (int i = 1; i * i <= num; i++) {
        if (num % i == 0) {
            divisors.Add(i);
            if (i != 1 && i != num / i) // 避免重複添加平方根與 1 對應的 num
                divisors.Add(num / i);
        }
    }
    
    sum = divisors.Where(d => d < num).Sum(); // 排除自身
    
    if (sum == num) {
        divisors.Sort();
        string formula = $"{num}=" + string.Join("+", divisors.Where(d => d < num));
        Console.WriteLine(formula); // 輸出：28=1+2+4+7+14
        return true;
    }
    return false;
}

優化版：O(√n) 複雜度

public bool IsPerfectNumberOptimized(int num) {
    if (num <= 1) return false;
    
    int sum = 1; // 1 永遠是約數
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            sum += i;
            if (i != num / i) sum += num / i; // 加入配對約數
        }
    }
    return sum == num;
}

已知完全數

截至目前發現 51 個完全數，全為偶數，形式為 2^(p-1) × (2^p - 1) 其中 (2^p - 1) 為梅森質數。前 5 個：