关于素数、唯一分解等内容的详细讲解（从属于GESP五级）

本章内容

最大公约数和最小公倍数

素数、合数和其他数

一、最大公约数（GCD）

---

1 概念与性质

1. 1. 最大公约数（Greatest Common Divisor）
   给定两个正整数 ，它们的所有公共约数中最大的那个，称为它们的最大公约数，记作 。（唯一分解定理保证此定义的合理性）
2. 2. 基本性质

• • • （对称性）
  • • ；若 ，则 （辗转相除性质）
  • • 如果 ，且 ，，则 （化简性）

---

2 求最大公约数的方法

2.1 辗转相减法（Subtraction GCD）

思想：

• • 若 ，则 。
• • 否则将更大的数减去更小的数： 或 。
• • 重复此操作直到两数相等。

复杂度：
最坏情况下（当两个数相差 1 时）需进行多次减法，时间复杂度 ，通常不如辗转相除法高效。

代码示例：

#include <bits/stdc++.h>
using namespace std;
int subg(int a, int b) {if (a==b) return a;return a > b ? subg(a-b,b) : subg(a,b-a);
}
int main(){int x, y; cin >> x >> y;cout << subg(x, y) <<"\n";return 0;
}

---

2.2 二进制 GCD（Stein 算法）

思想：
利用二进制位操作替代除法［“若两数均为偶数，则 ；若一偶一奇，则去掉偶数的因子 2；否则相减并右移”］，将除法转换为移位和减法，大多数 CPU 中位运算比取模更快。

复杂度：
与辗转相除法同为 步，每步常数时间。

代码示例：

#include <bits/stdc++.h>
using namespace std;
int bgcd(int u, int v) {if (!u) return v;if (!v) return u;int sh = __builtin_ctz(u|v);    // 公共因子 2 的个数u >>= __builtin_ctz(u);do {v >>= __builtin_ctz(v);if (u > v) swap(u,v);v = v - u;} while (v);return u << sh;
}
int main(){int a, b; cin >> a >> b;cout << bgcd(a,b) <<"\n";return 0;
}

---

2.3 质因数分解法

思想：

• • 根据“唯一分解定理”，将 分别分解为质因子列表
• • 取公共质因子及其最小幂次乘积即为 GCD。

复杂度：
取决于分解复杂度，约 ，不适合非常大的数。

代码示例：

#include <bits/stdc++.h>
using namespace std;
int pgcd(int a, int b) {map<int, int> fa, fb;for (int i = 2; i*i <= a; i++)while (a%i == 0) { fa[i]++; a /= i; }if (a > 1) fa[a]++;for (int i = 2; i*i <= b; i++)while (b%i == 0) { fb[i]++; b/=i; }if (b > 1) fb[b]++;int g = 1;for (auto &p:fa) {int d = min(p.second, fb[p.first]);while (d--) g *= p.first;}return g;
}
int main(){int x, y; cin >> x >> y;cout << pgcd(x,y) <<"\n";return 0;
}

---

2.4 扩展欧几里得算法（Extended Euclidean Algorithm）

思想：
不仅求出 ，还计算满足 的整数对 ，常用于求逆元。

复杂度：
同辗转相除法 ，额外常数空间保存系数。

代码示例：

#include <bits/stdc++.h>
using namespace std;
int egcd(int a, int b, int &x, int &y) {if (!b) { x = 1; y = 0; return a; }int x1, y1;int d = egcd(b, a%b, x1, y1);x = y1;y = x1 - (a/b)*y1;return d;
}
int main(){int a,b; cin >> a >> b;int x,y;int d = egcd(a, b, x, y);cout << d <<"\n";  // 如果只需 GCD，输出 d 即可return 0;
}

---

3 小结

• • 辗转相除（Euclid）：经典、简单，。
• • 辗转相减：思路直观但最坏 。
• • 二进制 GCD：用移位替换除法，适合位运算密集环境。
• • 质因数分解：依赖分解效率，适合小规模。
• • 扩展欧几里得：同时得 Bézout 系数，常用于求逆元。

根据具体场景选择最合适的方法即可。

---

二、最小公倍数（LCM）

1 定义与性质

1. 1. 最小公倍数（Least Common Multiple）
   给定两个正整数 ，它们的公共倍数中最小的正整数称为它们的最小公倍数，记作 。
2. 2. 基本性质

• • • （对称性）
  • • 若 或 ，通常定义 。
  • • 与最大公约数的关系：

.

2 公式法

利用上面关系，有

只需先用欧几里得算法或其他 GCD 方法求得 ，再按上述公式计算即可，时间复杂度仍为 。

3 代码示例

#include <bits/stdc++.h>
using namespace std;// 递归版欧几里得算法
int gcd(int a, int b) {return b==0 ? a : gcd(b, a%b);
}
// 最小公倍数
int lcm(int a, int b) {if (a==0 || b==0) return 0;return a / gcd(a, b) * b;
}int main() {int x, y;cin >> x >> y;cout << lcm(x, y) << "\n";return 0;
}

如果要对多于两个数的集合求 LCM，可依次两两使用上述 lcm 函数累积：

int arrN;             // 数组长度
vector<int> v(arrN);  // 存放待求数
int res = v[0];
for (int i = 1; i < arrN; i++) {res = lcm(res, v[i]);
}
// 此时 res 即为整个数组的最小公倍数

三、素数、合数和其他数

---

1 基本概念

概念	定义与要点
素数 (prime)	大于 1、仅有 1 和其本身两个正因数的整数
合数 (composite)	大于 1、除了 1 和本身外还有其他因数的整数
偶数 / 奇数	能被 2 整除为偶数，不能被 2 整除为奇数；符号检查可用 n & 1
因数	能整除给定整数 n （余数为 0）的整数
倍数	形如 k × n (k 为整数) 的数是 n 的倍数
唯一分解定理	每个 >1 的整数可唯一写成按大小排序的质数乘积

---

2. 素数 / 合数判定

2.1 试除法（√n 上界）

1. 1. 若 n ≤ 1 →非素数。
2. 2. 若 n = 2 或 3 →素数。
3. 3. 若 n 能被 2 或 3 整除 →合数。
4. 4. 枚举 i = 5, 7, 11…到 √n，若 n % i == 0 →合数，否则素数。

试除上界 √n 来源于若 n = a·b，必有一因子 ≤ √n。

复杂度 O(√n)。

#include <bits/stdc++.h>
using namespace std;
bool ispr(long long n){if(n < 2) return 0;if(n < 4) return 1;          // 2,3if(n%2 == 0||n%3 == 0) return 0;for(long long i = 5; i*i <= n; i += 6)    //仔细观察if(n%i == 0||n%(i+2) == 0) return 0;return 1;
}
int main(){long long n; cin >> n;cout<<(ispr(n) ? "prime":"composite") << "\n";return 0;
}

2.2 埃拉托斯特尼筛

1 思路速览

1. 1. 建一张长度 n 的布尔表 vis，初始全 0（假设皆为素数）。
2. 2. 从 2 开始遍历到 √n：若 i 仍为 0，则把所有 i², i²+i, i²+2i … ≤ n 标成 1。
3. 3. 未被标记的全是素数。

时间 O(n log log n)、空间 O(n)；简单易背，在 GESP 真题常要求补全循环。

2 完整代码

#include <bits/stdc++.h>
using namespace std;// 返: 0..n 的素数表
vector<int> sv(int n) {vector<char> vis(n + 1, 0);   // 标记表vector<int> prm;              // 存素数for (int i = 2; 1LL * i * i <= n; i++)if (!vis[i])for (int j = i * i; j <= n; j += i)vis[j] = 1;       // 标合数for (int i = 2; i <= n; ++i)if (!vis[i]) prm.push_back(i);return prm;
}int main() {int n; cin >> n;              // 输入上界auto p = sv(n);cout << p.size() << "\n";     // 输出素数个数（示例）return 0;
}

---

2.3 线性筛（欧拉筛 / 最小质因子筛）

1 思路速览

• • 维护一个素数表 prm 和与之同长的遍历指针；
• • 每个合数只被“它的最小质因子”筛一次 ⇒ 整体 O(n)；
• • 关键循环：

for i = 2..n:if minp[i] == 0  →  i 为素数，存入 prm，minp[i] = ifor p ∈ prm 且 p ≤ minp[i] 且 i*p ≤ n:minp[i*p] = pif p == minp[i]  break

2 完整代码

#include <bits/stdc++.h>
using namespace std;// 返: 0..n 的素数表；可顺便得到最小质因子 minp
vector<int> ls(int n, vector<int>& mp) {mp.assign(n + 1, 0);vector<int> prm;for (int i = 2; i <= n; i++) {if (!mp[i]) {          // i 是新素数mp[i] = i;prm.push_back(i);}for (int p : prm) {if (1LL * i * p > n) break;mp[i * p] = p;     // 标记最小质因子if (p == mp[i]) break;   // 保障线性}}return prm;
}int main() {int n; cin >> n;vector<int> mp;            // 最小质因子表auto p = ls(n, mp);cout << p.size() << "\n";  // 素数个数（示例）return 0;
}

---

3 利用 mp 拓展操作

// 分解任意 x ≤ n
vector<int> dec(int x, const vector<int>& mp) {vector<int> fac;while (x > 1) {fac.push_back(mp[x]);x /= mp[x];}return fac;
}

这样 O(∣分解因子数∣) 时间即可得到质因数序列。

---

2.4 两种筛法对比

属性	埃氏筛	线性筛
最差时间复杂度	O(n log log n)	O(n)
实际常数	很小	稍大（多维护 mp 与两层循环）
是否给出最小质因子	否（需额外数组）	是（天然维护）
编码难度	初学者友好	稍高，需要“break”控制线性性
适合考点	手补标记循环/整型溢出等	手填 break 条件或求分解应用

两实现都必须熟练掌握：

• • 小范围或只需判素时写埃氏即可；
• • 需要质因数分解、函数个数/和、莫比乌斯、欧拉 φ 等高级操作时优选线性筛。

3 奇偶性判定

3.1 思想

• • 按 2 取模：n % 2 == 0 为偶数，反之奇数。
• • 按位运算：最低二进制位决定奇偶，n & 1 更快。

3.2 代码示例

#include <bits/stdc++.h>
using namespace std;
bool isev(long long n){ return (n&1) == 0; // 偶数判定
}  
int main(){long long x; ci n>> x;cout << (isev(x)?"even":"odd") <<"\n";return 0;
}

复杂度 O(1)。

---

4 因数与倍数操作

4.1 判定因数 / 倍数关系

• • a % b == 0 → b 是 a 因数，或 a 是 b 倍数。
• • 若要判断「因数 / 倍数」双向关系，只需单次取模。

4.2 枚举所有因数

• • 枚举 i = 1…√n，若 n % i == 0 则 i 和 n/i 是成对因数。
• • 时间 O(√n)。

#include <bits/stdc++.h>
using namespace std;
vector<long long> fact(long long n){vector<long long> v;for(long long i = 1; i*i <= n; i++)if(n%i == 0){v.push_back(i);if(i*i != n) v.push_back(n/i);}sort(v.begin(), v.end());return v;
}
int main(){long long n; cin >> n;auto f = fact(n);for(auto x:f) cout << x<<" ";return 0;
}

4.3 因数个数 & 因数和

1. 1. 先用试除或线性筛求质因数分解：
   .
2. 2. 因数个数：.
3. 3. 因数和：.

---

5 唯一分解

---

5.1 定理表述

唯一分解定理（Fundamental Theorem of Arithmetic）
任何大于 1 的整数 都可唯一地写成按质数从小到大的乘积

， .

“唯一”指的是质数及其幂次的集合唯一（不计排列次序）。

意义

• • 为 因数个数/和公式、欧拉 φ、莫比乌斯 μ 等函数提供理论基础。
• • 使“最大公约数—最小公倍数”公式、线性筛最小质因子表等结论成立。

---

5.2 算法设计

试除分解（√n 上界）

1. 1. 令 。
2. 2. 枚举 ：若 ，计数幂次并除尽。
3. 3. 枚举结束后若 ，则剩下的 本身是质数。

复杂度：，足以应付五级数据范围（ 级）。

利用最小质因子表 mp（线性筛结果）

若已用线性筛求得 mp[i] = i 当且仅当 i 为素数：

while (x > 1):p = mp[x]计数 ex /= p

复杂度：与质因子个数同阶，近乎 。

---

5.3 完整代码

下面给出 (A) 试除法版 与 (B) 线性筛＋最小质因子版，两段互不依赖，可任选其一在考场书写。

(A) 试除法分解

#include <bits/stdc++.h>
using namespace std;vector<pair<long long,int>> fac(long long n){   // 返: (质因子,幂次)vector<pair<long long, int> > v;for(long long i = 2; i*i <= n; i++){if(n%i == 0){int c = 0;while(n%i == 0){n /= i;++c; }v.push_back({i, c});}}if(n > 1) v.push_back({n, 1});return v;
}int main(){long long n; cin >> n;auto f = fac(n);for(auto &t:f) cout << t.first <<"^"<< t.second <<" ";return 0;
}

(B) 线性筛 + 最小质因子分解

#include <bits/stdc++.h>
using namespace std;// 线性筛
vector<int> ls(int n, vector<int>& mp){mp.assign(n+1, 0);vector<int> prm;for(int i = 2; i <= n; i++){if(!mp[i]){ mp[i] = i; prm.push_back(i); }for(int p : prm){if(1LL*i*p > n) break;mp[i*p] = p;if(p == mp[i]) break;}}return prm;
}vector<pair<int, int> > fd(int x,const vector<int>& mp){vector<pair<int, int> > v;while(x > 1){int p = mp[x], c=0;while(x%p == 0){x /= p; ++c; }v.push_back({p, c});}return v;
}int main(){int n; cin >> n;vector<int> mp;ls(n, mp);                 // 预筛 2..nauto f = fd(n, mp);for(auto &t:f) cout << t.first <<"^"<< t.second <<" ";return 0;
}

---

唯一性证明（简要）

1. 1. 存在性：
   用数学归纳法或反复取最小质因子，必能终止于 1，因每步将数减小。
2. 2. 唯一性：

，

取最小质因子 min = min。min 必整除左右两端且为质数，故它等于 ，去掉同幂次后用归纳完成。

---

应用示范

• • 因数个数：若分解得 ，则因数个数 。
• • 最大公约数：两数分解后取公共质因子最小幂次数乘积。
• • 欧拉 φ：。

---

四、试题举例

【选择题】

✅ 1.用辗转相除法求的第一步等价于计算
A.
B.
C.
D.

答案 B
解析 84÷30 余 24，故变为 。

---

✅ 2.若，则正确的快速公式是
A.
B.
C.
D.

答案 C
解析 最小公倍数与最大公约数满足 。

---

✅ 3. 以下哪个数是素数？
A. 91 B. 97 C. 121 D. 143

答案 B
解析 97 只能被 1 和 97 整除；其余含非平凡因数。

---

✅ 4. 60 的正因数个数是
A. 8 B. 10 C. 12 D. 16

答案 B
解析 ，个数

---

✅ 5. 下面四个数对中，哪一对互为倍数关系？
A. (45, 28) B. (64, 48) C. (42, 210) D. (81, 54)

答案 C
解析 210 = 42 × 5；其它选项两数都无法整除对方。

---

【判断题】

✅ 1.

答案：√
解析：交换律。

✅ 2. 若 ，则

答案：√
解析：互质时公式化为乘积。

✅ 3. 任意奇数加偶数必得奇数。

答案：√
解析：奇 (2k + 1) + 偶 (2m) = 2(k+m)+1，仍奇。

✅ 4. 若整数 n 的所有正因数共有 4 个，则 n 必为合数。

答案：√
解析：素数因数只 2 个；4 个因数说明至少两种质因子或一个质因子平方。

✅ 5. 任何大于 1 的合数都可以写成两个互质整数的乘积。

答案：×
解析：例如 4 = 2×2，两个乘数不互质。

---

【程序阅读题】

✅ 题干

输入读取两正整数，先输出它们的最大公约数，再输出最小公倍数，并判断第一个数是否为素数，是素数输出 prime，是合数则输出 comp。

思路分析

1. 1. 以 42 和 70 为例， 计算步骤

14
210
comp

• • • gcd(42,70)：70%42=28 → gcd(42,28)=14。 求最大公约数
  • • lcm：42/14 = 3，再乘 70 = 210。 求最小公倍数
  • • prm(42)：42 可被 2 整除，故为合数（输出 "comp"）。 判断素数
    输出

1. 2. 若直接用 a*b，对 32 位或 64 位整型，大数相乘可能溢出。先除后乘保证中间结果，远小于原乘积，安全且不影响结果。

参考代码

#include <bits/stdc++.h>
using namespace std;int gcd(int a, int b){           // 欧几里得算法return b ? gcd(b, a%b) : a;
}bool prm(int n){                // 试除到 √n 判断素数if(n < 2) return 0;if(n%2 == 0) return n == 2;for(int i = 3; i*i <= n; i+=2)if(n%i == 0) return 0;return 1;
}long long lcm(int a, int b){     // 先除后乘避免溢出return 1LL*a/gcd(a,b)*b;
}int main(){int x,y;cin >> x >> y;                  // 样例输入： 42 70cout << gcd(x,y) <<"\n";cout << lcm(x,y) <<"\n";cout << (prm(x) ? "prime" : "comp") <<"\n";return 0;
}