最近又研究了線性篩素數(shù)方法的擴展，的確非常強大。
經(jīng)典的應(yīng)用是線性時間篩歐拉函數(shù)和求約數(shù)個數(shù)。我想了一下線性時間篩約數(shù)和(積性函數(shù))，也是可行的。
對于一個大于1的數(shù)n，可以寫成p1 ^ a1 * p2 ^ a2 * ... * pn ^ an，那么n的約數(shù)和就是(p1 ^ 0 + p1 ^ 1 + ... p1 ^ a1) * ... * (pn ^ 0 + ... + pn ^ an)，由此就可以有遞推關(guān)系了：
設(shè)f[i]表示i的約數(shù)和，e[i]表示i的最小素因子個數(shù)，t[i]表示(p1 ^ 0 + .. + p1 ^ a1)，p1是t的最小素因子，a1是p1的冪次，這樣對于i * p[j]，如果p[j]不是i的因子，那么根據(jù)積性條件，f[i*p[j]] = f[i] * (1 + p[j])，e[i] = 1，t[i] = 1 + p[j]；如果p[j]是i的因子，那么相當(dāng)于t[i]多了一項p1 ^ (a1 + 1)，首先e[i]++，然后tmp = t[i]，t[i] += p[j] ^ e[i]，f[i*p[j]] = f[i] / tmp * t[i]。這樣也就做到了O(1)的時間計算出了f[i*p[j]]同時也計算出了附加信息。

這種方法還可以繼續(xù)推廣，例如可以記錄i的最小素因子，這樣就可以做到O(log n)時間的素因子分解。