约数与因子枚举

1 问题：怎样找出一个数的全部因子

在 整除 中，我们已经知道：若正整数 $d$ 能整除正整数 $n$，就称 $d$ 是 $n$ 的因数，也叫约数或因子。本文只讨论正约数，不枚举负数。

例如 $36$ 的全部正约数是：

注意不要把「约数」和「质因数」混淆：$4$、$6$、$9$ 都是 $36$ 的约数，但它们不是质数。

接下来分别解决两个问题：

1. 给一个正整数 $n$，列出它的全部正约数。
2. 给一个上界 $N$，预处理 $1\sim N$ 每个数的全部正约数。

2 先从朴素枚举开始

正约数不可能大于 $n$，所以直接检查 $1,2,\ldots,n$：若 n % i == 0，就找到了一个约数。

这需要 $O(n)$ 次检查。若 $n=10^{12}$，就要检查一万亿次，显然不适合直接做。

有没有办法，不检查所有候选，也能找到全部约数？

3 单个数：约数总是成对出现

3.1 一次整除，得到两个约数

如果 $d\mid n$，那么存在正整数 $q$ 满足

这说明 $q=n/d$ 也能整除 $n$。例如 $36$ 的约数可以这样配对：

当发现 $2$ 是约数时，就不必再走到 $18$ 才发现另一个约数：计算 $36/2$ 即可。

3.2 为什么只需要检查到平方根

一对约数 $d,q$ 满足 $dq=n$。若它们都大于 $\sqrt n$，乘积就会大于 $n$，产生矛盾。

因此，每对约数中至少有一个不超过 $\sqrt n$。只要枚举

就能遇到每一对约数中的较小者，再通过 $n/d$ 找到较大者，不会漏掉任何约数。

3.3 完全平方数：平方根只记录一次

对于 $36$，枚举到 $d=6$ 时，配对的约数也是 $6$，只能记录一次。

因此每次整除成功时：

1. 记录 $d$；
2. 计算 $q=n/d$；
3. 仅当 $d\ne q$ 时，才记录 $q$。

d == n / d 是在已经确认整除的前提下，判断当前这一对约数是否重合，也就是当前是否正好枚举到平方根。不要理解成「只要 n 是完全平方数，每一对都只记录一个」。例如 $36$ 的 $(2,18)$ 仍然需要记录两个。

3.4 如何直接得到升序结果

如果每找到一对就立即输出，顺序会是 1 36 2 18 ...，并非升序。

可以先把全部结果放在一个数组里，最后排序；也可以利用约数对本身的顺序，不额外排序：

• 小约数按枚举顺序进入 small，天然递增；
• 大约数进入 large，因为 $n/d$ 随着 $d$ 增大而减小，所以天然递减；
• 最后把 large 反转，接到 small 后面。

例如 $n=36$：

1
2
3
4

small：1 2 3 4 6
large：36 18 12 9
反转 large：9 12 18 36
拼接结果：1 2 3 4 6 9 12 18 36

3.5 C++ / Python 实现

两份程序都读入一个正整数 $n$，输出它的全部正约数，按升序排列。C++ 输入需要在 long long 的正数范围内；Python 使用整数运算，不依赖浮点平方根。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <iostream>
#include <vector>
using namespace std;

vector<long long> get_factors(long long n) {
    vector<long long> small, large;
    // d <= n / d 等价于 d * d <= n，但不会发生乘法溢出。
    for (long long d = 1; d <= n / d; d++) {
        if (n % d != 0) continue;
        small.push_back(d);
        long long other = n / d;
        if (d != other) large.push_back(other);
    }
    // 大约数原本递减，反向拼接后得到升序结果。
    for (int i = (int)large.size() - 1; i >= 0; i--) {
        small.push_back(large[i]);
    }
    return small;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    if (!(cin >> n)) return 0;
    vector<long long> factors = get_factors(n);
    for (int i = 0; i < (int)factors.size(); i++) {
        if (i > 0) cout << ' ';
        cout << factors[i];
    }
    cout << '\n';
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import sys


def get_factors(n: int) -> list[int]:
    small = []
    large = []
    d = 1
    while d * d <= n:
        if n % d == 0:
            small.append(d)
            other = n // d
            if d != other:
                large.append(other)
        d += 1
    # 小约数递增，大约数递减；反转后拼接。
    small.extend(reversed(large))
    return small


def main():
    n = int(sys.stdin.buffer.readline())
    print(*get_factors(n))


if __name__ == '__main__':
    main()

输入：

1

36

输出：

1

1 2 3 4 6 9 12 18 36

C++ 用 d <= n / d 作为循环条件，而不是 d * d <= n，避免乘法溢出。对于正整数，这两个条件等价。Python 整数没有固定宽度溢出问题，可以直接使用 d * d <= n。

设 $\tau(n)$ 表示 $n$ 的正约数个数。按通常的整数运算计数方式：

• 检查候选耗时 $O(\sqrt n)$；
• 拼接、输出耗时 $O(\tau(n))$；
• 总时间为 $O(\sqrt n+\tau(n))=O(\sqrt n)$，存储结果需要 $O(\tau(n))$ 空间。

这里没有额外排序，因此不会多出 $O(\tau(n)\log\tau(n))$ 的排序开销。若输入是任意精度大整数，单次除法也有自身的位运算开销，上述复杂度不能理解成与整数位数无关的运行时间保证。

4 批量预处理：反过来枚举倍数

4.1 从「谁是它的约数」到「它是谁的约数」

如果需要得到 $1\sim N$ 每个数的约数，逐个试除的总时间约为 $O(N\sqrt N)$。

换一个枚举方向：

不再问「$j$ 的约数有哪些」，而是问「$d$ 是哪些数的约数」。

答案很直接：$d$ 是 $d,2d,3d,\ldots$ 的约数。

因此可以先建立 factors[0..N]，然后：

1. 从小到大枚举 $d=1,2,\ldots,N$；
2. 枚举 $d$ 的所有倍数 $j=d,2d,\ldots\le N$；
3. 把 $d$ 加入 factors[j]。

例如外层枚举到 $d=3$ 时，就把 $3$ 放进 $3,6,9,12,\ldots$ 的列表里。

4.2 为什么不漏、不重，而且有序

如果 $d$ 是 $j$ 的约数，那么 $j$ 一定是 $d$ 的倍数，所以在枚举 $d$ 时必然访问到 $j$，不会遗漏。

每个 $d$ 只枚举一次，它的每个倍数也只访问一次，因此同一个列表不会重复加入同一个约数。

由于外层 $d$ 从小到大，每个列表都按升序接收约数，结果天然有序，不需要再排序。

4.3 C++ / Python 实现

程序第一行读入 $N,q$，随后读入 $q$ 个查询数 $x$，要求 $1\le x\le N$。每个查询输出一行，列出 $x$ 的全部正约数。这里的查询数可以分布在任意空白分隔的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> precompute_factors(int n) {
    vector<vector<int>> factors(n + 1);
    for (int d = 1; d <= n; d++) {
        // 使用 long long 防止 j += d 时发生 int 溢出。
        for (long long j = d; j <= n; j += d) {
            factors[j].push_back(d);
        }
    }
    return factors;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<vector<int>> factors = precompute_factors(n);
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        for (int j = 0; j < (int)factors[x].size(); j++) {
            if (j > 0) cout << ' ';
            cout << factors[x][j];
        }
        cout << '\n';
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import sys


def precompute_factors(n: int) -> list[list[int]]:
    # 为每个数创建独立列表，不能写成 [[]] * (n + 1)。
    factors = [[] for _ in range(n + 1)]
    for d in range(1, n + 1):
        for j in range(d, n + 1, d):
            factors[j].append(d)
    return factors


def main():
    # 按行读入并依次产生整数，避免一次保留所有查询和输出。
    data = (int(value) for line in sys.stdin.buffer for value in line.split())
    n = next(data)
    q = next(data)
    factors = precompute_factors(n)
    for _ in range(q):
        x = next(data)
        print(*factors[x])


if __name__ == '__main__':
    main()

输入：

1
2
3
4

12 3
1
6
12

输出：

1
2
3

1
1 2 3 6
1 2 3 4 6 12

下标 $0$ 的列表保持为空，只是为了方便直接用正整数作为下标，不是在枚举零的约数。

4.4 为什么复杂度是 $O(N\log N)$

外层枚举 $d$ 时，内层访问 $\lfloor N/d\rfloor$ 个倍数，总次数为

因此预处理时间为 $O(N\log N)$。每次内层访问都存入一个约数，所以总共也需要存储 $S(N)$ 个条目，连同 $N+1$ 个列表，空间为 $O(N+S(N))=O(N\log N)$。

查到 factors[x] 这个列表只需 $O(1)$；但遍历或输出其全部元素仍需要 $O(\tau(x))$，不能说整次输出查询是 $O(1)$。

若只需要每个数的约数个数或约数和，可以把“加入列表”改成累加计数或累加 $d$，不保存全部约数，结果数组只需 $O(N)$ 空间。枚举的总次数不变。

5 怎样选择方法

不能只看到「查询多」就一定预处理。例如只有几百个数，但最大值达到 $10^{12}$，建立整个值域的列表根本不可行。

反过来，即使 $N=10^6$ 看起来不算特别大，保存全部列表也已经是千万级约数条目。Python 还有列表对象、引用和整数对象的额外开销，C++ 也有容器与分配开销，都应先核对内存限制。若只有一次查询，不必预处理所有数。

单个 $n\le10^{12}$ 时试除最多检查约 $10^6$ 个候选，仍要结合查询次数与语言时限判断是否合适，不能把值域例子当成必过保证。

6 常见用途与边界

• 缩小答案范围：若某个候选答案必须整除 $n$，只枚举约数，再逐个验证，不必检查所有整数。
• 统计整除关系：枚举一个数的约数，查询这些约数在频次表中出现了多少次。
• 完整重复块：若字符串由同一个长度为 $d$ 的短串完整重复组成，则 $d\mid n$，可以只检查字符串长度的约数。注意一般意义下允许末尾不完整的“周期”不一定整除长度，例如 ababa 有周期 $2$，但 $2\nmid5$。

实现时还要检查：

1. $n=1$：约数只有 $1$，不能因为配对而输出两次。
2. $n$ 为质数：约数只有 $1,n$。
3. $n$ 为完全平方数：平方根只记录一次，例如 $36$ 的 $6$。
4. 只枚举正约数：不把 $0$ 当作除数，也不把 $n=0$ 套入本模板。
5. 使用整数除法：Python 配对约数用 n // d，不是得到浮点数的 n / d。

7 总结

找一个数的约数：枚举较小的一半，用 $n/d$ 找到配对的另一半。

找一批数的约数：枚举约数 $d$，把它送到每个倍数的列表里。

前者利用成对性减少候选，后者交换枚举方向复用整除关系。先确定需要处理多少个数、值域有多大、是否必须保存全部约数，再选择实现。

8 相关题解

暂无相关题解