C語言求自然數所有約數之和：O(√n) 優化算法與代碼實現

問題描述

輸入一個自然數 n，輸出其所有正約數之和。

範例： n=6 → 約數 1,2,3,6 → 和=12

朴素 O(n) 算法

int sum_divisors_naive(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++)
        if (n % i == 0) sum += i;
    return sum;
}

簡單直觀，但 n=10⁹ 時需 10⁹ 次循環，太慢。

優化 O(√n) 算法

約數成對出現：i × (n/i) = n。遍歷到 √n 即可。

int sum_divisors_fast(int n) {
    int sum = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i) sum += n / i; // 避免完全平方數重複
        }
    }
    return sum;
}

完整程序（含約數列印）

#include <stdio.h>

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        int sum = 0;
        printf("%d 的約數有：", n);
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                printf("%d ", i);
                sum += i;
                if (i != n / i) {
                    printf("%d ", n / i);
                    sum += n / i;
                }
            }
        }
        printf("\n約數和為 %d\n", sum);
    }
    return 0;
}

數學擴展：約數個數與和的公式

若 n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ（質因數分解），則：

• 約數個數：d(n) = (a₁+1)(a₂+1)…(aₖ+1)
• 約數和：σ(n) = ∏ (pᵢ^(aᵢ+1)-1)/(pᵢ-1)

例： 7A (A 為質數) = 7¹ × A¹ → 約數個數 = (1+1)(1+1) = 4（即 1, 7, A, 7A）。

總結

求約數和是數論基礎操作。O(√n) 配對遍歷 是工程標準寫法；大規模查詢可預處理質因數分解或使用篩法預計算 σ(n)。理解約數成對特性與質因數公式，能靈活解決相關變體問題。