因数

若无特殊说明，本章涉及的变量皆为正整数.

定义 #

若 $n \div d$ 为整数，则 $d$ 是 $n$ 的因数，记作 $d\mid n$.

算数基本定理 #

任意正整数 $n$ 都能唯一地分解为有限个质数的乘积.

$$n=p_1^{\normalsize c_1}\cdot p_2^{\normalsize c_2}\cdots p_m^{\normalsize c_m}$$

分解质因数 #

试除法 #

将 $n$ 分解成算数基本定理的形式. 如 $$360=2^3\times 3^2\times 5$$

枚举 $i=2,3,\cdots,\sqrt{n}$，除尽 $n$ 中的 $i$，并记录除的次数.

const int N = 1e6;
vector<int> P, C;

void factor(int n) {
    for (int i = 2; i <= sqrt(n); i ++) {
        if (n % i == 0) {
            P.push_back(i), C.push_back(1);
            while (n % i == 0)
                n /= i, C.back() ++;
        }
    }
    if (n != 1) {
        P.push_back(n);
        C.push_back(1);
    }
}

倍数法 #

求 $[1,n]$ 中各整数的因数集 $fact$. 如

$$fact[12]=\{1,2,3,4,6,12\}$$

对各整数依次进行试除法效率差，此时考虑倍数法：

$i$ 的倍数必有因数 $i$.

枚举 $i=1,2,\cdots,n$，并在 $i$ 的倍数的因数集中加入 $i$.

时间复杂度为 $O(n\log{n})$.

const int N = 1e6;

vector<int> fact[N];

void factor(int n) {
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; i * j <= n; j ++) {
            fact[i * j].push_back(i);
        }
    }
}