親和數問題：500 萬以內全量求解，O(N log N) 線性篩思想

什麼是親和數？

畢達哥拉斯學派發現：兩數 a, b，若 a 的真因數和 = b，b 的真因數和 = a，則稱之為親和數。
例：220 真因數和 = 284，284 真因數和 = 220。
其他對：(1184,1210)、(2620,2924)……

暴力不可行，需巧思

直接模擬 + 剪枝，偽親和數量級達 10¹³，千萬次/秒也要 3 年。優化需空間換時間，但數據規模大，伴隨數組空間代價高。
關鍵洞察：利用下標即數值的數組特性，將「回溯」轉為「遞推預處理」——類埃氏篩。

核心算法：伴隨數組線性遍歷

// 時間複雜度 O(N log N) + O(N) = O(N log N) (log N 為調和級數)
#include <stdio.h>

int sum[5000010];  // 防越界

int main() {
    int i, j;
    // 1 是所有數真因數，初始化為 1
    for (i = 0; i <= 5000000; i++) sum[i] = 1;

    // 預處理：i 從 2 到 2500000，為所有倍數累加 i
    for (i = 2; i + i <= 5000000; i++) {
        j = i + i;               // 真因數不含自身，從 2*i 開始
        while (j <= 5000000) {
            sum[j] += i;         // j 是 i 的倍數，i 是 j 的真因數
            j += i;
        }
    }

    // 掃描：從最小親和數 220 開始
    for (i = 220; i <= 5000000; i++) {
        if (sum[i] > i && sum[i] <= 5000000 && sum[sum[i]] == i) {
            printf("%d %d ", i, sum[i]);  // 去重、不越界、滿足定義
        }
    }
    return 0;
}

運行結果

精華註解

1. 建立 500 萬數組，對每個 i 給其倍數位置加 i，循環結束後 sum[x] 即為 x 的真因數和（類埃氏篩）。
2. 連續數據映射可用數組下標替代，節省空間——數據結構的藝術。
3. 大規模回溯轉遞推生成，逆向思維——算法的藝術。
4. 把最簡單東西用得最巧妙，勝過用複雜方法解複雜問題。

小規模演示（10 以內）

初始全置 1 → i=2,3,4,5 為倍數加 i → 得 sum[6]=1+2+3=6、sum[10]=1+2+5=8……
掃描時 sum[220]=284 且 sum[284]=220，即得一對親和數。