---
title: "初等数论"
description: "整除、质数、最大公约数、取模、筛法与快速幂。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 初等数论

![](https://img.dailyup.xyz/optimized/8207672300505-292d65f8-54e6-4641-b04f-262b8741760b.jpg)

数论是 CSP-J 复赛和 GESP 五级的常客。它有个特点：题目往往只有一两行，但里面藏着一个整除性质或者一个取模技巧，想通了代码很短，想不通就只能暴力。

本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。

| 考试 | 大纲要求 | 本章位置 |
| --- | --- | --- |
| GESP C++ 五级 | 考点 1：初等数论（素数与合数、最大公约数与最小公倍数、同余与模运算、约数与倍数、质因数分解、奇偶性）；考点 4：辗转相除法、埃氏筛法与线性筛法、唯一分解定理 | 全章 |
| NOI 入门级 | 1.5.3 初等数论 | 全章 |
| CSP-J/S 入门级 | 5.3 初等数论 | 全章 |

## 整除、因数与倍数

若整数 $a$ 除以整数 $b$（$b \neq 0$）的余数为 0，就说 $b$ 整除 $a$，记作 $b \mid a$。此时 $b$ 是 $a$ 的因数（约数），$a$ 是 $b$ 的倍数。

几条常用性质：

- 若 $a \mid b$ 且 $b \mid c$，则 $a \mid c$。
- 若 $a \mid b$ 且 $a \mid c$，则 $a \mid (bx + cy)$，其中 $x$、$y$ 是任意整数。
- 若 $a \mid b$ 且 $b \mid a$，则 $a = b$ 或 $a = -b$。

## 质数与合数

只有 1 和它本身两个正因数的正整数叫**质数**（素数），否则叫**合数**。

两个容易考的点：

- **1 既不是质数也不是合数。** 它只有一个正因数。
- **2 是最小的质数，也是唯一的偶质数。** 其它偶数都能被 2 整除，都是合数。

判断单个数是不是质数，试除到 $\sqrt n$ 就够了。如果 $n$ 有大于 $\sqrt n$ 的因数，那必然有一个小于 $\sqrt n$ 的对应因数，早就被发现了。

```cpp
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) { // 写成 i * i <= n 避免浮点误差
        if (n % i == 0) return false;
    }
    return true;
}

试除法判断单个数是 $O(\sqrt n)$。$n$ 到 $10^{12}$ 时大约是 $10^6$ 次运算，完全够用。但要用它判断 $1$ 到 $n$ 的每一个数，总复杂度是 $O(n\sqrt n)$，$n = 10^6$ 就超时了，这时要换成筛法。

## 质因数分解与唯一分解定理

**唯一分解定理**（算术基本定理）：任何一个大于 1 的整数，都能唯一地分解成若干质数的乘积。

$$n = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}$$

分解的方法是从小到大试除，除得动就一直除，直到商为 1。

```cpp
// n 最大可达 10^12，超过 int 范围，参数要用 long long
void factorize(long long n) {
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            cout << i << "^" << cnt << endl; // 质因数 i 出现了 cnt 次
        }
    }
    if (n > 1) cout << n << "^1" << endl; // 剩下的就是最后一个质因数
}

复杂度是 $O(\sqrt n)$。最后那个 `if (n > 1)` 不能漏：如果原数本身是质数，或者分解到最后剩一个大于 $\sqrt n$ 的质因数，循环里抓不到它。

## 最大公约数与最小公倍数

$a$ 和 $b$ 的最大公约数记作 $\gcd(a, b)$，最小公倍数记作 $\operatorname{lcm}(a, b)$。

**辗转相除法**（欧几里得算法）利用一个性质：$\gcd(a, b) = \gcd(b, a \bmod b)$。反复用这个式子把两个数变小，直到其中一个变成 0，另一个就是答案。

```cpp
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

最小公倍数由最大公约数算出：

$$\operatorname{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$$

写成代码时要注意溢出。$a$、$b$ 都接近 $10^9$ 时，$a \times b$ 会到 $10^{18}$ 量级，直接写 `a * b / gcd(a, b)` 可能先溢出再除。**先除以 gcd 再乘**：

```cpp
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

这两个函数在《递归算法》里作为递归的例子也出现过，那里有更详细的推导。

## 取整与取模

C++ 的整数除法向零取整，`7 / 2` 是 3，`-7 / 2` 是 -3，不是 -4。需要向下取整时用 `floor()`，或者自己处理负数。

取模的结果符号跟着被除数走：

```cpp
cout << 7 % 3 << endl;   // 1
cout << -7 % 3 << endl;  // -1，不是 2

需要非负余数时，加上模数再取一次：

```cpp
int mod = ((x % m) + m) % m;

同余的记号是 $a \equiv b \pmod m$，表示 $a$ 和 $b$ 除以 $m$ 的余数相同。同余式可以相加、相减、相乘，但不能随便相除，这一条留到《数论进阶》再展开。

## 奇偶性

判断奇偶只看最低位：`x & 1` 为 1 就是奇数，为 0 就是偶数。比 `x % 2` 稍快，也更直接。

奇偶性的常见用处：

- 两个奇数的和是偶数，一奇一偶的和是奇数。
- 连续整数的乘积一定是偶数。
- 总和为奇数时，不可能把它平均分成若干对。

## 素数筛法

要预处理出 $1$ 到 $n$ 内所有质数，用筛法。

### 埃氏筛

从 2 开始，把每个质数的倍数标记成合数。

```cpp
const int MAXN = 10000005;
bool isPrime[MAXN];
vector<int> primes;

void sieve(int n) {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) { // 从 i*i 开始
                isPrime[j] = false;
            }
        }
    }
}

从 $i^2$ 开始标记是关键优化，因为 $2i$、$3i$ 这些更小的倍数已经被更小的质数标记过了。复杂度 $O(n \log \log n)$，接近线性，$n = 10^7$ 也能跑。

### 线性筛

线性筛保证每个合数只被它的最小质因数筛掉一次，复杂度是严格的 $O(n)$。

```cpp
const int MAXN = 10000005;
bool isPrime[MAXN];
vector<int> primes;

void linearSieve(int n) {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) primes.push_back(i);
        for (int j = 0; j < (int)primes.size() && i * primes[j] <= n; j++) {
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0) break; // 保证每个合数只被筛一次
        }
    }
}

`if (i % primes[j] == 0) break;` 这一行是核心。它保证 $i \times p_j$ 的最小质因数就是 $p_j$，所以每个合数只会在它最小质因数那一轮被标记。

需要质数表的时候，线性筛顺手就得到了，所以在数论题里更常用。

## 快速幂

计算 $a^b \bmod m$。直接循环乘 $b$ 次，$b = 10^9$ 时不可能跑完。快速幂把指数拆成二进制，每次把底数平方、指数减半，只需要 $O(\log b)$ 次乘法。

```cpp
long long fastPow(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod; // 这一位是 1，乘进去
        a = a * a % mod;                // 底数平方
        b >>= 1;                        // 指数右移一位
    }
    return res;
}

不用取模时把 `mod` 设成一个足够大的数即可。这个算法也叫「倍增」，本质和《倍增法》里的思路一样。

## 复杂度速查

| 操作 | 复杂度 | 适用规模 |
| --- | --- | --- |
| 试除判断单个数 | $O(\sqrt n)$ | $n \le 10^{12}$ |
| 质因数分解 | $O(\sqrt n)$ | $n \le 10^{12}$ |
| 辗转相除求 gcd | $O(\log n)$ | 任意 |
| 埃氏筛 | $O(n \log \log n)$ | $n \le 10^7$ |
| 线性筛 | $O(n)$ | $n \le 10^7$ |
| 快速幂 | $O(\log b)$ | 任意 |

## 初赛选择题精选

数论是 GESP 五级笔试的必考内容。下面 8 道题按考点分类编写，覆盖质数识别、约数个数、最大公约数、负数取模、快速幂、筛法复杂度、奇偶性与唯一分解定理这些高频考点。先自己做，再看答案与解析。

### 题 1（质数识别）

下列四个数中，是质数的是（　）。

A. 91　B. 87　C. 89　D. 93

**答案：C**

**解析**：$91 = 7 \times 13$，$87 = 3 \times 29$，$93 = 3 \times 31$，都能被更小的质数整除；只有 89 除不动 2、3、5、7（$\sqrt{89} < 10$），是质数。三个非质数都是「邻近 90 的合数」，这是选择题最爱的出题区间。

### 题 2（约数个数）

36 的正约数一共有多少个？

A. 6　B. 8　C. 9　D. 12

**答案：C**

**解析**：由唯一分解定理 $36 = 2^2 \times 3^2$，约数个数等于**每个质因数的指数加 1 再相乘**：$(2+1) \times (2+1) = 9$ 个。列出验证：1、2、3、4、6、9、12、18、36，正好 9 个。这条「指数加 1 相乘」的公式是数论笔试的常客。

### 题 3（最大公约数与最小公倍数）

两个正整数的最大公约数是 4，最小公倍数是 48，其中一个数是 16，另一个数是多少？

A. 8　B. 12　C. 24　D. 32

**答案：B**

**解析**：正整数有一条性质：**两数之积 = 最大公约数 × 最小公倍数**。所以另一个数是 $\frac{4 \times 48}{16} = 12$。验证：$\gcd(16, 12) = 4$，$\operatorname{lcm}(16, 12) = 48$，正确。

### 题 4（负数取模）

在 C++ 中，表达式 `-7 % 3` 的值是（　）。

A. -1　B. 1　C. -2　D. 2

**答案：A**

**解析**：C++ 的取模符号跟着被除数走，$-7 = 3 \times (-3) - 1$，余数是 -1。需要非负余数时，写成 `((x % m) + m) % m`，这是用取模实现循环下标时的必备写法。

### 题 5（快速幂的运算量）

用快速幂计算 $a^b \bmod p$，其中 $b = 10^9$。大约需要进行多少次乘法运算？

A. 约 $10^9$ 次　B. 约 $10^6$ 次　C. 约 60 次　D. 约 30 次

**答案：C**

**解析**：快速幂每轮把指数减半，$10^9 < 2^{30}$，所以递归（循环）只有约 30 层；每层一次平方，指数位为 1 时还要多乘一次底数，最多再加 30 次，总共约 60 次乘法。这正是快速幂把 $O(b)$ 降到 $O(\log b)$ 的含义。

### 题 6（筛法复杂度）

用埃氏筛法求出 $10^7$ 以内的所有质数，时间复杂度约为（ ）。

A. $O(n)$　B. $O(n \log n)$　C. $O(n \log \log n)$　D. $O(n^2)$

**答案：C**

**解析**：埃氏筛的总运算量是 $\sum_{p \le n} \frac{n}{p}$（对每个质数 $p$ 划掉它的倍数），而这个和约为 $n \ln \ln n$，即 $O(n \log \log n)$。

**和线性筛的区别**：线性筛（欧拉筛）是严格的 $O(n)$，每个合数只被它的最小质因数筛一次。$n = 10^7$ 时两者都能过，但线性筛常数更大，实际差距没有理论那么大。

### 题 7（奇偶性判断）

下列说法正确的是（ ）。

A. 两个奇数的和一定是奇数
B. 奇数个奇数相加的结果一定是奇数
C. 两个奇数的积一定是偶数
D. 偶数除以 2 一定是偶数

**答案：B**

**解析**：逐项分析：

- A 错：奇 + 奇 = 偶（如 $3 + 5 = 8$）。
- B 对：奇数个奇数相加，结果一定是奇数（如 $1+3+5 = 9$）。**奇数个**这个条件是关键。
- C 错：奇 × 奇 = 奇（如 $3 \times 5 = 15$）。
- D 错：如 $6 \div 2 = 3$，是奇数。

**记忆口诀**：奇偶性只看得数里的「奇数个数」——加法时奇数个数为奇数则和为奇数，乘法时只要有一个偶数结果就是偶数。

### 题 8（唯一分解定理）

$360$ 的正因数共有多少个？

A. 12　B. 20　C. 24　D. 36

**答案：C**

**解析**：先分解：$360 = 2^3 \times 3^2 \times 5^1$。由唯一分解定理，正因数个数等于各指数加 1 的乘积：

$$(3+1)(2+1)(1+1) = 4 \times 3 \times 2 = 24$$

**为什么是「指数 +1」相乘？** 因为因数 $2^a 3^b 5^c$ 中，$a$ 可以取 $0 \sim 3$ 共 4 种，$b$ 取 $0 \sim 2$ 共 3 种，$c$ 取 $0 \sim 1$ 共 2 种，组合起来就是 $4 \times 3 \times 2$。这是数论选择题的高频考点。

## 练习

### 练习 1：质因数分解

#### 题目描述

输入一个大于 1 的整数 $n$，按从小到大的顺序输出它的质因数分解式，格式为 `n=p1^e1*p2^e2*...`（每个质因数都要带指数，包括指数为 1 的）。

#### 输入格式

一个整数 $n$。

#### 输出格式

输出一行，表示质因数分解式。

#### 数据范围

- $2 \le n \le 10^{12}$。

#### 输入输出样例

输入

```
180

输出

```
180=2^2*3^2*5^1

输入

```
7

输出

```
7=7^1

#### 题目分析

正文质因数分解模板的直接落地，三个要点：一是 $n$ 用 `long long`（$10^{12}$ 超出 `int`）；二是试除到 $\sqrt n$；三是循环结束后如果 $n > 1$，剩下的一定是最后一个质因数（它可能就是 $n$ 本身，比如输入质数 7 时输出 `7=7^1`）。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/maths/number-theory/index.md

### 练习 2：第 n 个质数

#### 题目描述

质数从小到大依次是 2、3、5、7、11……求第 $n$ 个质数。

#### 输入格式

一个整数 $n$。

#### 输出格式

输出一个整数，表示第 $n$ 个质数。

#### 数据范围

- $1 \le n \le 100000$。

#### 输入输出样例

输入

```
100000

输出

```
1299709

#### 题目分析

批量找质数用**筛法**。筛到多大才够？由质数定理，第 $10^5$ 个质数大约是 $n \ln n \approx 10^5 \times 11.5 \approx 1.15 \times 10^6$，筛到 $1.3 \times 10^6$ 留足余量。

实现时把筛法和计数合在一个循环里：每发现一个新质数就计数加 1，数够 $n$ 个就可以停了。注意内层标记循环里 $i \times i$ 用 `long long` 防止溢出。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/maths/number-theory/index.md

埃氏筛的复杂度是 $O(M \log \log M)$，$M = 1.3 \times 10^6$ 时几十毫秒就能跑完，换成线性筛更快，但在这个规模下没有必要。

### 练习 3：快速幂

#### 题目描述

给定 $a$、$b$、$p$，计算 $a^b \bmod p$ 并输出。特别地，$b = 0$ 时输出 `1 % p`。

#### 输入格式

一行三个整数 $a$、$b$、$p$。

#### 输出格式

输出一个整数，表示 $a^b \bmod p$ 的结果。

#### 数据范围

- $0 \le a, b < 2^{31}$，$2 \le p \le 10^9$。

#### 输入输出样例

输入

```
2 10 1000

输出

```
24

说明：$2^{10} = 1024$，对 1000 取模得 24。

#### 题目分析

正文快速幂模板的直接落地。三个易错点再强调一遍：`res` 初始化为 `1 % p`（$p = 1$ 时任何数模 1 都是 0）；底数要先对 $p$ 取模；每步乘完都要取模，不能最后再取。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/maths/number-theory/index.md

$2^{10} = 1024$ 的验证：二进制 $10 = 1010_2$，共进行 4 次平方、2 次额外乘法，总共 6 次乘法，而不是暴力乘的 10 次。

## 常见易错点

- 忘记处理 1：它既不是质数也不是合数。
- 质因数分解最后剩下的 `n > 1` 漏掉，质数会被分解成「什么都没有」。
- `lcm` 直接写 `a * b / gcd` 会溢出，要先除后乘。
- 取模结果为负时忘记修正，用来做数组下标会崩。
- 线性筛的 `break` 条件写成其它形式，复杂度会退化，甚至筛错。
- 快速幂里底数要先取模，指数很大时也要注意类型。
## 小结

- 质数判断用试除到 $\sqrt n$，批量求质数用筛法。
- 唯一分解定理是数论的基石，分解方法是从小到大试除。
- 辗转相除法求最大公约数，$\operatorname{lcm}(a, b) = a / \gcd(a, b) \times b$。
- 辗转相除、埃氏筛、线性筛、快速幂是数论题的四大工具，都能背下来直接用。
- 会用「指数加 1 相乘」计算正整数的约数个数，会用「两数之积 = gcd × lcm」互算。
- 会写质因数分解、筛法找第 n 个质数、快速幂取模三个数论编程题。

Source: https://cppguide.xyz/maths/number-theory/index.mdx
