Skip to content

因数

2021-07-06

INFO

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

定义

n÷d 为整数,则 dn 的因数,记作 dn

算数基本定理

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

n=p1c1p2c2pmcm

分解质因数

试除法

n 分解成 算数基本定理 的形式,如

360=23×32×5

枚举 i=2,3,,n,除尽 n 中的 i,并记录除的次数。

cpp
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

枚举 i=1,2,,n,并在 i 的倍数的因数集中加入 i

时间复杂度为 O(nlogn)

cpp
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);
        }
    }
}