求 500 萬以內所有親和數：線性篩法的極致優雅

什麼是親和數？

若兩數 a, b 滿足：a 的真因數（不含自身）之和 = b，且 b 的真因數之和 = a，則稱 (a,b) 為親和數對。
經典例：220 & 284、1184 & 1210、2620 & 2924。

暴力思路為何不可行？

對每個數 i 遍歷 √i 找因子，再對因子和找因子。
500 萬數字，單次因子枚舉 ≈ N^1.5 ≈ 10^10 量級，單線程需數天。必須預處理 + 線性掃描。

核心算法：類埃拉托斯特尼篩法預處理因子和

關鍵洞察：每個數 i 都是其倍數的真因數。
初始化 sum[1..N] = 1（1 是所有數真因數）。
對 i = 2 到 N/2，將 i 加到所有倍數 j = 2i, 3i, ... 的 sum[j] 中。
複雜度：N/2 + N/3 + N/4 + ... ≈ N log N（調和級數）。

C 代碼實現

#include <stdio.h>

#define N 5000000
int sum[N + 1];

int main() {
    // 1. 初始化：1 是所有數的真因數
    for (int i = 1; i <= N; ++i) sum[i] = 1;

    // 2. 篩法累加真因數和：i 從 2 到 N/2
    for (int i = 2; i + i <= N; ++i) {
        for (int j = i + i; j <= N; j += i)
            sum[j] += i;
    }

    // 3. 掃描輸出親和數對：去重條件 sum[i] > i 且 sum[sum[i]] == i
    for (int i = 220; i <= N; ++i) { // 220 是最小親和數
        int s = sum[i];
        if (s > i && s <= N && sum[s] == i)
            printf("%d %d\n", i, s);
    }
    return 0;
}

複雜度分析

• 時間：O(N log N)（調和級數）+ O(N) 掃描 ≈ O(N log N)。
  實測 500 萬 < 1 秒（C/C++ 優化編譯）。
• 空間：int[5000001] ≈ 20 MB，完全可接受。

優化細節

1. 外層循環上界：i <= N/2，因真因數不超過 N/2
2. 內層從 2i 開始：避免將數自身算作真因數
3. 掃描從 220 開始：已知最小親和數，微優化
4. 去重條件：sum[i] > i 確保只輸出 (a,b) 其中 a < b
5. 邊界檢查：sum[i] <= N 防越界

運行結果（部分）

220 284
1184 1210
2620 2924
5020 5564
6232 6368
...

延伸思考

• 社會數：長鏈 sum[a]=b, sum[b]=c, ..., sum[z]=a，同樣可用此預處理數組快速探測
• 更大範圍（10^8+）：分段篩法 + 磁盤存儲，或數論公式（σ函數）配合質因子分解
• 並行化：外層循環易於 OpenMP 並行，#pragma omp parallel for 即可線性加速

總結

親和數問題展示了「遞推替代回溯、空間換時間、篩法思想」的威力。將「求單個數的因子和」轉化為「所有數同時累加因子貢獻」，從 O(N^1.5) 降至 O(N log N)，是算法設計中逆向思維的經典範例。