约数（因数）

wzzwzy · 2026-07-09 15:04:51 · 算法·理论

约数（因数）

本文部分内容参考李煜东《算法竞赛进阶指南》

更新记录：

• 2026/7/9：约数（因数）部分基本完成

概述

::::info[定义] 若整数 n 除以整数 d 的余数为 0，即 d 能整除 n，则称 d 是 n 的约数（或因数），n 是 d 的倍数，记为 d \mid n。 ::::

::::info[算术基本定理的推论]{open} 设正整数 N 被唯一分解为：

其中 c_i 为正整数，p_i 为质数，且 p_1 < p_2 < \cdots < p_m。

则 N 的正约数集合可表示为：

• 正约数个数为：

  (c_1 + 1)(c_2 + 1)\cdots(c_m + 1) = \prod_{i=1}^m (c_i + 1)

• 所有正约数之和为：

  (1 + p_1 + p_1^2 + \cdots + p_1^{c_1}) \cdots (1 + p_m + p_m^2 + \cdots + p_m^{c_m}) = \prod_{i=1}^m \left( \sum_{j=0}^{c_i} p_i^j \right)

  ::::

一、求约数

1. 试除法（求 N 的正约数集合）

若 d \ge \sqrt{N} 是 N 的约数，则 N/d \le \sqrt{N} 也是 N 的约数。也就是说，约数总是成对出现的（对于完全平方数，\sqrt{N} 会单独出现）。

因此，只需扫描 d = 1 \sim \lfloor \sqrt{N} \rfloor，判断 d 是否能整除 N。若能，则 d 和 N/d 都是 N 的约数。时间复杂度为 O(\sqrt{N})。

::::info[代码实现]

int factor[1600], m = 0;
for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
        factor[++m] = i;
        if (i != n / i) factor[++m] = n / i;
    }
}
for (int i = 1; i <= m; i++) cout << factor[i] << endl;

::::

::::info[试除法的推论]{open} 一个整数 N 的约数个数上界为 2\sqrt{N}。 ::::

2. 倍数法（求 1 \sim N 中每个数的正约数集合）

如果用试除法分别求出 1 \sim N 中每个数的正约数集合，时间复杂度为 O(N\sqrt{N})，过高。

换一种思路：对于每个数 d，1 \sim N 中以 d 为约数的数正是 d 的倍数：d, 2d, 3d, \dots, \lfloor N/d \rfloor \times d。于是我们可以枚举 d，将其加入这些倍数的约数集合中。这就是“倍数法”。

::::info[代码实现]

vector<int> factor[500010];
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n / i; j++)
        factor[i * j].push_back(i);

for (int i = 1; i <= n; i++) {
    for (int j = 0; j < factor[i].size(); j++)
        printf("%d ", factor[i][j]);
    puts("");
}

::::

上述算法的时间复杂度为：

::::info[倍数法的推论]{open}