质数 | 数学知识

质数

定义

若一个正整数无法被除了 1 和它自身之外的任何自然数整除, 则称该数为质数 (或素数), 否则称该正整数为合数。

在整个自然数集合中, 质数的数量不多, 分布比较稀疏, 对于一个足够大的整数 $N$, 不超过 $N$ 的质数大约有 $N / \ln N$ 个, 即每 $\ln N$ 个数中大约有 1 个质数。

质数的判定

试除法

若一个正整数 $N$ 为合数, 则存在一个能整除 $N$ 的数 $T$, 其中 $2 \leq T \leq \sqrt{N}$ 。

证明: 由定义得, 因为 $N$ 是合数, 所以存在一个能整除 $N$ 的数 $M$, 其中 $2 \leq M \leq N-1$。
反证法： 假设命题不成立, 那么这样的数 $M$ 一定满足 $\sqrt{N}+1 \leq M \leq N-1$ 。因为 $M$ 能整除 $N$, 所以它们的商 $N / M$ 也能整除 $N$ 。而 $2 \leq N / M \leq \sqrt{N}$, 令 $T=$ $N / M$, 这与假设矛盾。故假设不成立, 原命题成立。

根据上述命题, 我们只需要扫描 $2 \sim \sqrt{N}$ 之间的所有整数, 依次检查它们能否整除
$N$, 若都不能整除, 则 $N$ 是质数, 否则 $N$ 是合数。试除法的时间复杂度为 $0(\sqrt{N})$ 。

当然, 我们需要特判 0 和 1 这两个整数, 它们既不是质数, 也不是合数。

bool isPrime(int n) {
	if (n < 2) return false;
	for (int i = 2; i <= n / i; ++i) {
		if (n % i == 0) return false;
	}
	return true;
}

“试除法” 作为最简单也最经典的确定性算法, 是我们在算法竟赛中通常会使用的方法。有一些效率更高的随机性算法, 例如 “Miller-Robbin” 等, 有较小的概率把合数错误判定为质数, 但多次判定合起来的错误概率趋近于零, 感兴趣的读者可以自行查阅并学习。

质数的筛选

给定一个整数 $N$, 求出 $1 \sim N$ 之间的所有质数, 称为质数的筛选问题。

Eratosthenes 筛法

Eratosthenes 筛分基于这样的想法: 任意整数 $x$ 的倍数 $2 x, 3 x, \cdots$ 都不是质数。根据质数的定义, 上述命题显然成立。

我们可以从 2 开始, 由小到大扫描每个数 $x$, 把它的倍数 $2 x, 3 x, \cdots,\lfloor N / x \rfloor * x$ 标记为合数。当扫描到一个数时, 若它尚未被标记, 则它不能被 $2 \sim x-1$ 之间的任何数整除, 该数就是质数。

Eratosthenes 筛法的进行过程如下:

另外, 我们可以发现, 2 和 3 都会把 6 标记为合数。实际上, 小于 $x^{2}$ 的 $x$ 的倍数在扫描更小的数时就已经被标记过了。因此, 我们可以对 Eratosthenes 筛法进行优化, 对于每个数 $x$, 我们只需要从 $x^{2}$ 开始, 把 $x^{2},(x+1) * x, \cdots,\lfloor N / x\rfloor * x$ 标记为合数即可。

void getPrimes(int n) {
	memset(notprime, 0, sizeof(notprime)); // 非质数，即合数标记
	for (int i = 2; i <= n; ++i) {
		if (notprime[i]) continue;
		cout << i << endl; // i 是质数
		for (int j = i; j <= n / i; ++j) notprime[i * j] = true;
	}
}

Eratosthenes 筛法的时间复杂度为 $O\left(\Sigma_{\text {质数 } p \leq N} \frac{N}{p}\right)=O(N \log \log N)$ 。该算法实现简单, 效率已经非常接近于线性, 是算法竞赛中最常用的质数筛法。

线性筛法

即使在优化后 (从 $x^{2}$ 开始), Eratosthenes 筛法仍然会重复标记合数。例如 12 既会被 2 又会被 3 标记, 在标记 2 的倍数时, $12=6 * 2$, 在标记 3 的倍数时, $12=4 * 3$ 。其根本原因是我们没有确定出唯一的产生 12 的方式。

线性筛法通过 “从大到小累积质因子” 的方式标记每个合数, 即让 12 只有 $3 * 2 * 2$ 一种产生方式。设数组 $v$ 记录每个数的最小质因子, 我们按照以下步骤维护 $v$ 。

1. 依次考虑 $2 \sim N$ 之间的每一个数 $i$ 。
2. 若 $v[i]=i$, 说明 $i$ 是质数, 把它保存下来。
3. 扫描不大于 $v[i]$ 的每个质数 $p$, 令 $v[i * p]=p$ 。也就是在 $i$ 的基础上累积一个质因子 $p$ 。因为 $p \leq v[i]$, 所以 $p$ 就是合数 $i * p$ 的最小质因子。

$$\begin{array}{c|l|l|l|l|l|l|l|l|l} i & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ p \leq v[i] & 2 & 2,3 & 2 & 2,3,5 & 2 & 2,3,5,7 & 2 & 2,3 & 2 \\ i * p & 4 & 6,9 & 8 & 10,15,25 & 12 & 14,21,35,49 & 16 & 18,27 & 20 \end{array}$$

每个合数 $i * p$ 只会被它的最小质因子 $p$ 筛一次, 时间复杂度为 $\mathrm{O}(N)$ 。

// 线性筛法
int v[MAX_N], prime[MAX_N];
void primes(int n) {
	memset(v, 0, sizeof(v)); // 最小质因子
	m = 0; // 质数数量
	for (int i = 2; i <= n; i++) {
		if (v[i] == 0) { // i是质数
			v[i] = i;
			prime[++m] = i;
		}
		// 给当前的数i乘上一个质因子
		for (int j = 1; j <= m; j++) {
			// i有比prime[j]更小的质因子，或者超出n的范围
			if (prime[j] > v[i] || prime[j] > n/i) break;
			// prime[j]是合数i*prime[j]的最小质因子
			v[i*prime[j]] = prime[j];
		}
	}
	for (int i = 1; i <= m; i++)
		cout << prime[i] << endl;
}

void getPrimes(int n) {
	vector<bool> notprime(n + 1);
	vector<int> prime;
	for (int i = 2; i <= n; ++i) {
		if (!notprime[i]) prime.push_back(i);
		for (auto p : prime) {
			if (p > n / i) break;
			notprime[i * p] = true;
			if (i % p == 0) break;
		}
	}
	for (auto p : prime) cout << p << endl;
}

质因数分解

算术基本定理

任何一个大于 1 的正整数都能唯一分解为有限个质数的乘积, 可写作:

$$N=p_{1}^{c_{1}} p_{2}^{c_{2}} \cdots p_{m}^{c_{m}}$$

其中 $c_{i}$ 都是正整数, $p_{i}$ 都是质数, 且满足 $p_{1}<p_{2}<\cdots<p_{m}$ 。

试除法

结合质数判定的 “试除法” 和质数筛选的 “Eratosthenes 筛法”, 我们可以扫描 $2 \sim|\sqrt{N}|$ 的每个数 $d$, 若 $d$ 能整除 $N$, 则从 $N$ 中除掉所有的因子 $d$, 同时累计除去的 $d$ 的个数。

因为一个合数的因子一定在扫描到这个合数之前就从 $N$ 中被除掉了, 所以在上述过程中能整除 $N$ 的一定是质数。最终就得到了质因数分解的结果, 易知时间复杂度为 $O(\sqrt{N})$ 。

特别地, 若 $N$ 没有被任何 $2 \sim \sqrt{N}$ 的数整除, 则 $N$ 是质数, 无需分解。

void divide(int n) {
	m = 0;
	for (int i = 2; i <= n / i; ++i) { 
		if (n % i == 0) { // i是质数，且 i 能整除 n
			p[++m] = i, c[m] = 0;
			while (n % i == 0) n /= i, c[m]++; // 除掉 n 中所有的 i
		} 
	}
	if (n > 1) p[++m] = n, c[m] = 1; // n 是质数
	for (int i = 1; i <= m; ++i) cout << p[i] << '^' << c[i] << endl;
}

“Pollard’s Rho” 算法是一个比 “试除法” 效率更高的质因数分解算法, 不过这超出了我们的探讨范围, 感兴趣的读者可以自行查阅并学习。

---

196. 质数距离

给定两个整数 $L$ 和 $U$，你需要在闭区间 $[L,U]$ 内找到距离最接近的两个相邻质数 $C_1$ 和 $C_2$（即 $C_2-C_1$ 是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。

同时，你还需要找到距离最远的两个相邻质数 $D_1$ 和 $D_2$（即 $D_1-D_2$ 是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。

输入格式

每行输入两个整数 $L$ 和 $U$，其中 $L$ 和 $U$ 的差值不会超过 $10^6$。

输出格式

对于每个 $L$ 和 $U$，输出一个结果，结果占一行。

结果包括距离最近的相邻质数对和距离最远的相邻质数对。（具体格式参照样例）

如果 $L$ 和 $U$ 之间不存在质数对，则输出 There are no adjacent primes.。

数据范围

$1 \le L < U \le 2^{31}-1$

输入样例：

2 17
14 17 

输出样例：

2,3 are closest, 7,11 are most distant.
There are no adjacent primes. 

算法分析

$L, R$ 的范围很大, 任何已知算法都无法在规定时间内生成 $[1, R]$ 中的所有质数。但是 $R-L$ 的值很小, 并且任何一个合数 $n$ 必定包含一个不超过 $\sqrt{n}$ 的质因子。

所以, 我们只需要用筛法求出 $2 \sim \sqrt{R}$ 之间的所有质数。对于每个质数 $p$, 把 $[L, R]$ 中能被 $p$ 整除的数标记, 即标记 $i * p\left(\lceil \frac{L}{p} \rceil \leq i \leq\lfloor \frac{R}{p}\rfloor \right)$ 为合数。

最终所有未被标记的数就是 $[L, R]$ 中的质数。对相邻的质数两两比较, 找出差最大的即可。

时间复杂度为 $O(\sum_{\text{质数}p\leq\sqrt{R}\frac{R-L}{p}})=O(\sqrt{R} \log \log \sqrt{R} + (R-L) \log \log R)$

Solution

---

197. 阶乘分解

给定整数 $N$，试把阶乘 $N!$ 分解质因数，按照算术基本定理的形式输出分解结果中的 $p_i$ 和 $c_i$ 即可。

输入格式

一个整数 $N$。

输出格式

$N!$ 分解质因数后的结果，共若干行，每行一对 $p_i, c_i$，表示含有 $p_i^{c_i}$ 项。按照 $p_i$ 从小到大的顺序输出。

数据范围

$3 \le N \le 10^6$

输入样例：

5 

输出样例：

2 3
3 1
5 1 

样例解释

$5! = 120 = 2^3 * 3 * 5$

算法分析

若把 $1 \sim N$ 每个数分别分解质因数, 再把结果合并, 时间复杂度过高, 为 $\mathrm{O}(N \sqrt{N})$ 。显然, $N !$ 的每个质因子都不会超过 $N$, 我们可以先筛选出 $1 \sim N$ 的每个质数 $p$, 然后 考虑阶乘 $N !$ 中一共包含多少个质因子 $p$ 。

$N !$ 中质因子 $p$ 的个数就等于 $1 \sim N$ 每个数包含质因子 $p$ 的个数之和。在 $1 \sim N$ 中, $p$ 的倍数, 即至少包含 1 个质因子 $p$ 的显然有 $\lfloor N / p \rfloor$ 个。而 $p^{2}$ 的倍数, 即至少包含 2 个质因子 $p$ 的有 $\lfloor N / p^{2}\rfloor$ 个。不过其中的 1 个质因子已经在 $[N / p]$ 里统计过, 所以只需要再统计第 2 个质因子, 即累加上 $\left[N / p^{2}\right]$, 而不是 $2 *\left\lfloor N / p^{2}\right\rfloor$ 。

综上所述, $N !$ 中质因子 $p$ 的个数为:

$$\left\lfloor\frac{N}{p}\right\rfloor+\left\lfloor\frac{N}{p^{2}}\right\rfloor+\left\lfloor\frac{N}{p^{3}}\right\rfloor+\cdots+\left\lfloor\frac{N}{p^{\lfloor\log_pN\rfloor}}\right\rfloor=\sum_{p^{k} \leq N}\left\lfloor\frac{N}{p^{k}}\right\rfloor$$

对于每个 $p$, 只需要 $O(\log N)$ 的时间计算上述和式。故对整个 $N !$ 分解质因数的时间复杂度为 $O(N \log N)$ 。

Solution

---