质数与约数

质数

定义

质数与合数的定义：质数与合数是针对所有大于 $1$ 的自然数来定义的，也就是说所有小于等于 $1$ 的数字都不属于质数和合数的范围。
在大于 $1$ 的整数中，如果只包含 $1$ 和本身两个约数，就被称为质数（素数）；反之为合数。

线性判断质数

很容易可以想到，只需要枚举 $2 \sim n - 1$ 的所有数字，依次判断它们能否整除 $n$ ，只要有一个可以就是合数；而如果都不能整除，则是质数，由此可以得到代码：

bool is_prime(int n) {
	if (n < 2) return 0;
	for (int i=2; i<=n-1; i++) {
		if (n%i == 0) return 0;
	}
	return 1;
}

容易发现，上面这个代码的时间复杂度是 $O (n)$ 级别的，那么在面对 $n$ 较大或者判断次数比较多时，会有超时的风险。

$\sqrt{n}$ 判断质数

在学习这个方法前，我们需要知道一个性质：如果 $i$ 可以整除 $n$ ，那么 $n / i$ 必然也可以整除 $n$ 。
所以根据这个性质，我们只需要枚举完所有较小的数字即可，可以列出如下公式：

i \leq n / i \to i \times i \leq n \to i \leq \sqrt{n}

所以上面代码可以优化为：

bool is_prime(int n) {
	if (n < 2) return 0;
	for (int i=2; i<=n/i; i++) {  // 写 i<=sqrt(n)也可以，但是还需要算，比较慢。
		if (n%i == 0) return 0;
	}
	return 1;
}

这样代码的时间复杂度就变成了 $O (\sqrt{n})$ 。

分解质因数

分解质因数应该是很多同学都熟悉的数学题，要把一个合数分解成多个质数相乘的结果。容易想到一个解法，枚举所有可能的质数，然后让这个质数一直去除 $n$ ，直到不能整除为止。

这样做确实可以，但其实我们没有必要去枚举质数，直接枚举 $2 \sim n - 1$ 然后一直除就可以了，不用管这个数字是否是质数，为什么呢？可以思考一下。

证明过程

假设当前枚举的数 $i$ 是合数，那么前面必然已经枚举过 $i$ 的质因子了，所以在前面已经通过不断的除使得质因子无法整除 $n$ 了，既然质因子都无法整除，作为合数的 $i$ 必然也不可能整除，所以合数 $i$ 并不会影响程序的结果，也就不需要去判断质数合数。

那么可以得到如下代码：

void divide(int n) {
	// 对数字 n 进行分解质因数
	for (int i=2; i<=n-1; i++) {
		if (n%i == 0) {
			int cnt = 0;
			while (n%i == 0) {
				n /= i;
				cnt++;
			}
			printf("%d %d\n", i, cnt);
		}
	}
}

同样的，这个代码也是 $O (n)$ 级别的时间复杂度，能否让算法更快一点呢？很容易能想到，大于 $n / i$ 的质因子最多只会有 $1$ 个，否则如果有两个的话，它俩乘起来就比 $n$ 大了，这肯定不可能。

所以，我们枚举的范围同样可以只到 $n / i$ ，而如果最后计算完后 $n! = 1$ 的话，那现在它里面的数字一定就是那个最后的质因子，代码成功优化为了 $O (\sqrt{n})$ 的时间复杂度(最好情况是 $O (l o g n)$ )。

void divide(int n) {
	// 对数字 n 进行分解质因数
	for (int i=2; i<=n/i; i++) {
		if (n%i == 0) {
			int cnt = 0;
			while (n%i == 0) {
				n /= i;
				cnt++;
			}
			printf("%d %d\n", i, cnt);
		}
	}
	if (n > 1) printf("%d %d\n", n, 1);
}

质数筛

在需要多次判断质数的场景，比如统计某个区间内的所有质数时， $O (\sqrt{n})$ 的速度还是太慢了，能否更快呢？这时候就要用到质数筛法了，常见的筛法有朴素筛、埃氏筛和欧拉筛。

朴素筛

筛法的思想很简单，数字的倍数一定不是质数。那么在选到一个数字时，把这个数字的所有倍数全部筛掉，这样过一轮之后，所有的质数也就被筛选出来了。
如果要用STL实现，就把 primes 数组替换为 vector<int>

const int N = 1e6+5;
int primes[N], cnt;  // primes用来存储质数，cnt是对应数组的下标
bool st[N];  // st[i]标记数字是否被筛掉

void get_primes(int n) {
	// 筛选 2~n中的所有质数
	for (int i=2; i<=n; i++) {
			if (!st[i]) {
				primes[++cnt] = i;  // 质数存到数组中
		}
		for (int j=i+i; j<=n; j+=i) st[j] = 1;  // 筛掉数字的倍数
	}
	// 这样过完之后，所有的质数就存到了primes数组中
	// 同时 st 中标记了每个数字是否是质数。
}

这段代码的时间复杂度约为 $O (n \log_{e} n)$ ，略快于 $O (n \log_{2} n)$ ，空间复杂度为 $O (n)$ 。

埃氏筛

可以发现，其实没必要把所有的数字的倍数都遍历一遍，因为如果数字是一个合数，它的倍数肯定也被之前的质数筛掉了，所以只需要遍历质数的倍数；这也是筛法的核心思想：质数的倍数一定不是质数。

const int N = 1e6+5;
int primes[N], cnt;  // primes用来存储质数，cnt是对应数组的下标
bool st[N];  // st[i]标记数字是否被筛掉

void get_primes(int n) {
	// 筛选 2~n中的所有质数
	for (int i=2; i<=n; i++) {
		if (!st[i]) {
			primes[++cnt] = i;  // 质数存到数组中
			for (int j=i+i; j<=n; j+=i) st[j] = 1;  // 筛掉质数的倍数
		}
	}
	// 这样过完之后，所有的质数就存到了primes数组中
	// 同时 st 中标记了每个数字是否是质数。
}

这段代码的时间复杂度约为 $O (n \log_{2} (\log_{2} n))$ ，空间复杂度为 $O (n)$ 。

欧拉筛(线性筛)

在埃氏筛中，为什么代码会耗时呢，是因为在遍历质数的倍数时，会重复标记很多数字，例如数字 $12$ ，既是 $2$ 的倍数，也是 $3$ 的倍数，那不管我们是扫描 $2$ 还是扫描 $3$ ，一定都会把 $12$ 去重复筛掉。
有什么办法可以让每个数字都只被筛一次呢？先来看下面这段代码：

void get_primes(int n) {
	// 筛选 2~n中的所有质数
	for (int i=2; i<=n; i++) {
		if (!st[i]) primes[++cnt] = i;  // 质数存到数组中
			// primes[j] <= n/i 理解为 primes[j]*i <= n，即只筛n范围内的数字
			for (int j=1; primes[j]<=n/i; j++) {
				st[primes[j]*i] = 1;  // 筛掉i的素数倍数
				if (i%primes[j] == 0) break;  // 线性复杂度的关键
			}
	}
}

这段代码乍一看很莫名其妙，感觉既不能筛掉所有的合数，也没法保证 $O (n)$ 的时间复杂度，但是数学就是如此的神奇，让我们往下看。

这个算法称为欧拉筛法，其核心思想是每个合数都可以分解为一个最小质因数乘以另一个数的形式，即合数 = 最小质因数 * 自然数，在上述代码中，st[primes[j]*i] = 1 做的工作就是把以 primes[j] 为最小质因数的数字给筛掉，来看一段表格：

i	primes	筛掉的数字
2	2	4
3	2,3	6,9
4	2,3	8
5	2,3,5	10,15,25
6	2,3,5	12
7	2,3,5,7	14,21,35,49
8	2,3,5,7	16
9	2,3,5,7	18,27
10	2,3,5,7	20
首先可以发现，每个数字都是被自己的最小质因子筛掉的，比如 $4$ 是被 $2$ 筛掉的， $12$ 是被 $2$ 筛掉的，如何证明这一点呢？

被最小质因子筛证明

这还要基于 if (i%primes[j]==0) break; 这段代码来证明，根据这个条件，我们代码中会有两种情况：

情况一：i % primes[j] == 0，那么 primes[j] 一定是 i 的最小质因子，否则肯定已经 break 了；因此 primes[j]*i 的最小质因子也必然是 primes[j] 。

情况二：i % primes[j] != 0 ，那么 primes[j] 一定小于 i 的最小质因子，否则在前面肯定已经 break 了；因此 primes[j]*i 的最小质因子必然是 primes[j] 。

因为每个数字都会被最小质因子筛掉，所以每个数字实际都只会被标记依次，那么时间复杂度就接近 $O (n)$ 了。
可能同学们还会有一个疑问，就是这样写代码不会漏掉一些数字么？当然不会，请看下面：

欧拉筛正确性证明

假设现在要筛掉合数 $a$ ，并且 $a$ 的最小质因数为 $b$ ，令 $a = p_{1} \times b$ ；在遇到 $a$ 的时候， $b$ 必然已经在 primes 数组中了，而 $p_{1}$ 这个数字显然一定在 $b \sim a$ 这个范围内，所以在遇到 $a$ 之前， $a$ 这个数字肯定已经被筛掉了。

以上便是关于欧拉筛的模板与证明，欧拉筛的时间复杂度为 $O (n)$ ，当 $n$ 达到 $1 e 7$ 时，埃氏筛与欧拉筛的性能差一倍左右。在一般情况下，进行质数筛时我们都可以选用欧拉筛法，而埃氏筛的思想也是很重要的。

约数

定义

约数的概念很简单，如果 $a$ 能够整除 $b$ ，那么 $a$ 是 $b$ 的约数， $b$ 是 $a$ 的倍数。

线性枚举约数

容易想到，枚举 $1 \sim n$ 的数字，然后依次判断并加到数组中即可，代码如下所示：

const int N = 1e5+5;
int res[N], cnt;

void get_divisors(int n) {
	for (int i=1; i<=n; i++) {
		if (n%i == 0) res[++cnt] = i;
	}
}

显然，这样做的时间复杂度是 $O (n)$ 级别的，能否更快呢？

$\sqrt{n}$ 枚举约数

还是质数时讲过的性质：如果 $i$ 可以整除 $n$ ，那么 $n / i$ 必然也可以整除 $n$ 。所以我们枚举的时候，可以只枚举到 $n / i$ ，然后当 $i$ 可以整除 $n$ 时，把 $i$ 和 $n / i$ 都加入到数组中即可，这样代码的时间复杂度就到了 $O (\sqrt{n})$

const int N = 1e5+5;
int res[N], cnt;

void get_divisors(int n) {
	for (int i=1; i<=n/i; i++) {
		if (n%i == 0) {
			res[++cnt] = i;
			if (i != n/i) res[++cnt] = n/i;  // 这个判断是防止加两次 n/i 进去
		}
	}
	sort(res+1, res+1+cnt);  // 如果不要求排序，也可以不用。
	// 另外，也可以用两个数组，一个存前半部分一个存后半部分，最后合并，比排序更快。
}

例题-约数个数

一个数的约数个数可以通过其质因数分解来确定。具体来说，如果一个数 $n$ 可以被分解为质因数的乘积，即 $n = p_{1}^{x_{1}} \times p_{2}^{x_{2}} \times \dots \times p_{k}^{x_{k}}$ ，那么 $n$ 的约数个数 $r$ 可以通过以下公式计算：

r = (x_{1} + 1) \times (x_{2} + 1) \times \dots \times (x_{k} + 1)

例如，数字 $378000$ 可以被分解为 $2^{4} \times 3^{3} \times 5^{3} \times 7^{1}$ )，因此它的约数个数为：

(4 + 1) \times (3 + 1) \times (3 + 1) \times (1 + 1) = 160

定理简证

容易发现， $p_{1}^{x_{1}}$ 的约数有： $p_{1}^{0}, p_{1}^{1}, p_{1}^{2} \dots p_{1}^{x_{1}}$ ，共 $x_{1} + 1$ 个；同理可得 $p_{2}^{x_{2}}$ 的约数有 $x_{2} + 1$ 个；一直到 $p_{k}^{x_{k}}$ 的约数有 $x_{k} + 1$ 个，根据乘法原理可知， $n$ 的约数个数就是 $(x_{1} + 1) \times (x_{2} + 2) \times . . . \times (x_{k} + 1)$ 。

来看例题：

题目描述

给定 $n$ 个正整数 $a_{i}$ ，请你输出这些数的乘积的约数个数，答案对 $10^{9} + 7$ 取模。

输入格式

第一行包含整数 $n$ 。
接下来 $n$ 行，每行包含一个整数 $a_{i}$ 。

输出格式

输出一个整数，表示所给正整数的乘积的约数个数，答案需对 $10^{9} + 7$ 取模。

样例输入

样例输出

题目分析

根据上述公式可得，我们只需要对每个 $a_{i}$ 进行质因数分解，统计所有质因子的指数，然后求和即可，因为数字范围比较大，所以可以使用 unordered_map 来记录每个质因子的出现次数。

示例代码

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

unordered_map<int, int> mp;

void get_cnt(int n) {
	for (int i=2; i<=n/i; i++) {  // 分解质因数
		while (n%i == 0) {
			n /= i;
			mp[i]++;  // 统计这个质因数的指数
		}
	}
	if (n > 1) mp[n]++;  // 单独处理比 n/i 大的质因子
}

int main() {
	int n, x;
	long long res = 1;
	cin >> n;
	for (int i=1; i<=n; i++) {
		cin >> x;
		get_cnt(x);
	}
	for (auto i:mp) res = res*(i.second+1) % MOD;  // 计算结果
	cout << res;
	return 0;
}

约数之和

题目描述

给定 $n$ 个正整数 $a_{i}$ ，请你输出这些数的乘积的约数之和，答案对 $10^{9} + 7$ 取模。

输入格式

第一行包含整数 $n$ 。

接下来 $n$ 行，每行包含一个整数 $a_{i}$ 。

输出格式

输出一个整数，表示所给正整数的乘积的约数之和，答案需对 $10^{9} + 7$ 取模。

样例输入

样例输出

题目分析

还是基于分解质因数的公式来计算。如果 $n = p_{1}^{x_{1}} \times p_{2}^{x_{2}} \times \dots \times p_{k}^{x_{k}}$ ，那么来显然 $p_{1}^{x_{1}}$ 的约数有 $p_{1}^{0}, p_{1}^{1}, \dots, p_{1}^{x_{1}}$ ，同理可得， $p_{k}^{x_{k}}$ 的约数有 $p_{k}^{0}, p_{k}^{1}, \dots p_{k}^{x_{k}}$ 。

我们来用实际的数字进行推导， $8$ 分解质因数后是 $2^{3}$ ，它的约数有 $2^{0}, 2^{1}, 2^{2}, 2^{3}$ ，那显然可得它的约数之和是 $2^{0} + 2^{1} + 2^{2} + 2^{3}$ 。
那 $72$ 分解质因数后是 $2^{3} \times 3^{2}$ ，它的约数除了上述 $8$ 的约数之外，还会有 $2^{0} \times 3^{1}, 2^{1} \times 3^{1}, 2^{2} \times 3^{1}, 2^{3} \times 3^{1}, 2^{0} \times 3^{2}, 2^{1} \times 3^{2}, 2^{2} \times 3^{2}, 2^{3} \times 3^{2}$ 。

假设 $m = 2^{0} + 2^{1} + 2^{2} + 2^{3}$ ，那么可得 $72$ 的因数之和为：

2^{0} + 2^{1} + 2^{2} + 2^{3} + 2^{0} \times 3^{1} + 2^{1} \times 3^{1} + 2^{2} \times 3^{1} + 2^{3} \times 3^{1} + 2^{0} \times 3^{2} + 2^{1} \times 3^{2} + 2^{2} \times 3^{2} + 2^{3} \times 3^{2}

即：

m + m \times 3^{1} + m \times 3^{2} \to m \times (3^{0} + 3^{1} + 3^{2}) \to (2^{0} + 2^{1} + 2^{2} + 2^{3}) \times (3^{0} + 3^{1} + 3^{2})

聪明的你再往下推一步，如果是 $360$ 分解质因数，得到的是 $2^{3} \times 3^{2} \times 5^{1}$ ，那么它的因数之和是多少呢？

揭晓答案，应该是：

(2^{0} + 2^{1} + 2^{2} + 2^{3}) \times (3^{0} + 3^{1} + 3^{2}) \times (5^{0} + 5^{1})

所以，根据数学归纳法可得，当 $n = p_{1}^{x_{1}} \times p_{2}^{x_{2}} \times \dots \times p_{k}^{x_{k}}$ 时，其约数和为：

s = (p_{1}^{0} + p_{1}^{1} + \dots + p_{1}^{x_{1}}) \times (p_{2}^{0} + p_{2}^{1} + \dots + p_{2}^{x_{2}}) \times \dots \times (p_{k}^{0} + p_{k}^{1} + \dots + p_{k}^{x_{k}})

根据上面的公式，来求出这个代码吧！

提示

如何计算 $p^{0} + p^{1} + \dots + p^{n}$ 呢？

$1 \times n + 1 = n + 1$

$(1 \times n + 1) \times n + 1 = n^{2} + n + 1$

...

示例代码

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
unordered_map<int, int> mp;

void get_cnt(int n) {
	// 此处实现同上段代码，不再演示
}

int main() {
	int n, x;
	long long res = 1;
	
	cin >> n;
	for (int i=1; i<=n; i++) {  // 求出所有质因子的指数
		cin >> x;
		get_cnt(x);
	}

	for (auto i:mp) {
		long long sum=1, a=i.first, b=i.second;
		while (b--) {  // 求解的关键，写法很多，也可以再来个变量，一项一项算然后求和。
			sum = (sum*a+1) % MOD;
		}
		res = res*sum % MOD;  // 一定要记得边算边模，否则数据会溢出
	}
	cout << res;
    return 0;
}

最大公约数

定义

最大公约数(GCD)，指两个或多个整数共有的约数中最大的一个，例如 $12$ 和 $16$ 的公约数由 $1, 2, 4$ ，其中最大的一个是 $4$ ，所以 $4$ 是 $12$ 和 $16$ 的最大公约数， $a$ 和 $b$ 的最大公约数记为 $g c d (a, b)$ ，最大公约数在数论问题中是特别重要的概念。

线性找最大公约数

很容易想到，如果要求 $a$ 和 $b$ 的最大公约数，我们只需要把 $m i n (a, b) \sim 1$ 的数字列出来，然后找到第一个能同时整除 $a$ 和 $b$ 的数字，就是最大公约数了，代码如下：

int gcd(int a, int b) {
	// 为什么是 min(a,b) 呢？因为约数的范围不会超过这个数字。
	for (int i=min(a,b); i>=1; i--) {
		if (a%i==0 and b%i==0) return i;
	}
}

显然，这个代码的时间复杂度是 $O (n)$ 级别的。

辗转相除法

欧几里得算法又称辗转相除法，原理为 $g c d (a, b) = g c d (b, a % b), (a >= b, a % b! = 0)$ 。

证明过程

令 $a = k \times b + r$ ，即 $r = a % b$ （ $a, b, k, r$ 均为正整数）。

设 $d$ 为 $a, b$ 的任意一个公约数，而根据上式可得 $r = a - k \times b$ ，两边同时除以 $d$ ，可得 $r / d = a / d - k \times b / d$ 。

因为 $a / d - k \times b / d$ 必然是一个整数，所以 $r / d$ 也是整数，也就意味着 $d$ 也是 $r$ 的约数，又因 $r = a % b$ ，所以 $a, b$ 和 $b, a % b$ 的公约数是一样的，所以最大公约数必然也一样，得证 $g c d (a, b) = g c d (b, a % b)$ 。

辗转相除法便是利用这个原理不断往下计算，直到 $a % b$ 为 $0$ 时，时间复杂度约为 $O (\log n)$ ，尝试自己实现下这个代码吧！

示例代码

int gcd(int a, int b) {
	// 可以简写为 return b ? gcd(b, a%b) : a;
	if (a%b == 0) return b;
	else return gcd(b, a%b);
}

质数与约数

质数

定义

线性判断质数

n 判断质数

分解质因数

质数筛

朴素筛

埃氏筛

欧拉筛(线性筛)

约数

定义

线性枚举约数

n 枚举约数

例题-约数个数

题目描述

输入格式

输出格式

样例输入

样例输出

题目分析

示例代码

约数之和

题目描述

输入格式

输出格式

样例输入

样例输出

题目分析

示例代码

最大公约数

定义

线性找最大公约数

辗转相除法

示例代码

$\sqrt{n}$ 判断质数

$\sqrt{n}$ 枚举约数