算法与数据结构：质数、互质判定和裴蜀定理

质数

首先回顾「质数」的定义：若一个正整数无法被除了 1 ​和它自身之外的任何自然数整除，则称该数为质数（或素数），否则称该正整数为合数。

根据上述定义，我们可以得知常见的质数有 2、3、5 等。另外，在整个自然数集合中，质数的分布也比较稀疏，对于一个足够大的整数 N，不超过 N 的质数大约有
$N/\ln (N)$ 个。

质数判定

常见的判定质数的方式是「试除法」，假设自然数 N 不是质数，则一定存在一对数
x, y ，使得下述条件成立：
$$\begin{gathered} N=x\cdot y \\ 1<x\le \sqrt{N}\le y<N \end{gathered}$$

因此我们可以在 $[2,\sqrt{N}]$ 的范围内枚举 x, 判断 x 是否存在。

如果 x 存在，则 N 为合数；否则 N 为质数。该算法时间复杂度为 $O(\sqrt{N})$
，具体代码如下所示：

// c语言
bool judgePrime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

def judgePrime(n):
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

质数筛选

对于一个正整数 N，一次性求出 1～N 之间所有的质数，即为质数筛选。

显然根据上述「质数判定」的内容，我们可以通过枚举 1～N 的所有数，再依次使用「试除法」来判定其是否为质数，从而完成质数的筛选。但此种方法的时间复杂度过高，为 $O(N\sqrt{N})$ 。

此处将介绍经典的「Eratosthenes 筛法」，也被称为「埃式筛」。该算法基于一个基本判断：任意质数 x 的倍数 ( 2x，3x，… ) 均不是质数。

根据该基本判断，我们得到如下算法过程：

• 将 2～N中所有数标记为 0
• 从质数 2 开始从小到大遍历2 ～ N中所有自然数
• 如果遍历到一个标记为 0 的数 x ,则将其 2～N 中 x 的所有倍数标记为 1

根据上述过程，不难发现如果一个数 x 的标记为 0​，则代表这个数不是 2～(x-1) 中任何数的倍数，即 x 为质数。

接下来我们以 2～10 为例，具体过程如下所示，最终标记为橙色的数为质数：

「Eratosthenes 筛法」的时间复杂度为 $O(N\log (\log (N)))$ ，并不是最快的素数筛法，但在绝大多数的「力扣数学题」中均已够用，且其实现代码较为简单，具体如下所示：

vector<int> primes, vis;
void get_primes(int n) {
    vis.resize(n + 1, 0);
    for(int i = 2; i <= n; i++) {
        if(vis[i] == 0) {
            primes.push_back(i);
            for(int j = i; j <= n; j += i) vis[j] = 1;
        }
    }
}

# Eratosthenes筛法

def get_primes(n):
    """获取n以内的所有素数"""
    if n < 2:
        return []
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i * i, n + 1, i):
                primes[j] = False
    return [i for i in range(n + 1) if primes[i]]

print(get_primes(100))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

质因数分解

根据「唯一分解定理」，任何一个大于 1 的正整数都能唯一分解为有限个质数的乘积：$N=p_1^{c_1}{p}_2^{c_2}\dots p_m^{c_m}$
其中 $c_i$ 均为正整数，而 $p_i$ 均为质数，且满足$p_1<p_2<\dots <p_m$ 。

根据上述定理，我们只需要求出所有的 $p_i,c_i$ ，即可完成对 N 的质因数分解。
那么如何求取 $p_i,c_i$ 呢？首先我们考虑如何求 $p_1$ 和 $c_1$ 。

由于 $p_1<p_2<\dots <p_m$ ，且 $p_1$ 为质数，因此不难发现， $p_1$ 是 N 所有因子中除 1 以外最小的数。

因此我们可以枚举 $2～\sqrt{N}$中的所有数 x，如果 N 是 x 的倍数，则 x 为 $p_1$。得到 $p_1$ 后，我们可以令 N 不断除以 $p_1$ 直至其不再为 $p_1$ 的倍数，则 $c_1$ 等于除以 $p_1$ 的总次数。

得到$p_1$ 和 $c_1$ 后，N 去除了所有的 $p_1$，因此 N 变为 $p_2^{c_2}\dots p_m^{c_m}$。又由于 $p_1<p_2$ ，因此我们继续枚举 x，如果再次出现 N 是 x 倍数的情况，则 x 为 $p_2$ 。

不断使用上述算法，直至循环结束。最后还需判断 N 是否为 1，如果 N 不为 1，则 $p_m=N,c_m=1$。

该算法的时间复杂度为 $O(log(N))$ ，具体代码如下所示，大家可以配合代码对该算法进行理解：

void divide(int n) {
	vector<int> p, c;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			p.push_back(i);
			int num = 0;
			while(n % i == 0) num++, n /= i;
			c.push_back(num);
		}
	}
	if (n > 1) {
		p.push_back(n);
		c.push_back(1);
	}
}

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

def divide(n):
    """质因数分解"""
    i = 2
    factors = []
    while i * i <= n:
        print("i = ", i)
        print("n = ", n)
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

print("质因数分解-唯一分解定理")
print(divide(100))  # [2, 2, 5, 5]

互质判定

首先介绍一下「最大公约数」的概念。如果自然数 c 同时是自然数 a 和 b 的约数，即 a 和 b 同时是 c 的倍数，则 c 为 a 和 b 的公约数。

「最大公约数」就是 a 和 b 的所有公约数中最大的那一个，通常记为 $gcd(a,b)$ 。

由此我们可以得到「互质」的判定条件，如果自然数 a，b 互质，则 $gcd(a,b)=1$ 。

于是问题变为「如何求 $gcd(a,b)$？」

此处需要引入「欧几里得算法」，如下所示：
$$\forall a,b\in N,b\ne 0,gcd(a,b)=gcd(b,amodb)$$

根据上述算法，可以得到如下代码，其时间复杂度为 $O(log(a,b))$：

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

裴蜀定理

若 $a,b,x,y,m$ 是整数，则 $ax+by=m$ 有解当且仅当 m 是 $gcd(a,b)$ 的倍数。

该定理有一个重要的推论：整数 a,b 互质的充要条件是存在整数 x,y 使 $ax+by=1$。