質數

首先回顧「質數」的定義：若一個正整數無法被除了 1 ?和它自身之外的任何自然數整除，則稱該數為質數（或素數），否則稱該正整數為合數。

根據上述定義，我們可以得知常見的質數有 2、3、5 等。另外，在整個自然數集合中，質數的分布也比較稀疏，對于一個足夠大的整數 N，不超過 N 的質數大約有
$N/\ln (N)$ 個。

質數判定

常見的判定質數的方式是「試除法」，假設自然數 N 不是質數，則一定存在一對數
x, y ，使得下述條件成立：
$$\begin{gathered} N=x?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 Falsereturn 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] = Falsefor i in range(2, int(n**0.5) + 1):if primes[i]:for j in range(i * i, n + 1, i):primes[j] = Falsereturn [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 = 2factors = []while i * i <= n:print("i = ", i)print("n = ", n)if n % i:i += 1else:n //= ifactors.append(i)if n > 1:factors.append(n)return factorsprint("質因數分解-唯一分解定理")
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)$？」

此處需要引入「歐幾里得算法」，如下所示：
$$?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$。