gcd/lcm + 素数判断与筛法

一、最大公约数 gcd

1. 定义与性质

最大公约数gcd(a,b)，是两个数公共约数中最大的一个。常用性质：

• gcd(a, 0) = a
• gcd(a, b) = gcd(b, a mod b)
• 多个数的 gcd 可递推：gcd(a,b,c) = gcd(gcd(a,b), c)

2. 欧几里得算法（辗转相除法）

原理：利用gcd(a,b) = gcd(b, a mod b)不断缩小问题规模，直到余数为 0，此时除数即为答案。

int gcd(int a, int b) { while (b != 0) { int temp = a % b; a = b; b = temp; } return a; }

递归版

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

二、最小公倍数 lcm

公式与防溢出写法

由唯一分解定理可得：

lcm(a,b)=gcd(a,b)a×b​

直接a*b容易溢出 int，因此改为：

lcm(a,b)=a/gcd(a,b)∗b

int lcm(int a, int b) { return a / gcd(a, b) * b; }

三、埃拉托斯特尼筛法（埃氏筛）

用于批量预处理 1~n 内所有素数，时间复杂度O(n log log n)。

1. 初始假设所有数都是素数
2. 从 2 开始，将每个素数的所有倍数标记为合数
3. 最终未被标记的即为素数

const int MAXN = 1e6 + 5; bool is_prime[MAXN]; void sieve(int n) { for (int i = 0; i <= n; ++i) is_prime[i] = true; is_prime[0] = is_prime[1] = false; for (int i = 2; i * i <= n; ++i) { if (is_prime[i]) { for (int j = i * i; j <= n; j += i) is_prime[j] = false; } } }

四、欧拉筛（线性筛）

埃氏筛会重复标记合数，欧拉筛保证每个合数只被最小质因子筛一次，达到严格线性复杂度O(n)，是大规模筛素数的最优写法。

const int MAXN = 1e6 + 5; bool is_prime[MAXN]; int prime[MAXN], cnt; void euler_sieve(int n) { for (int i = 2; i <= n; ++i) { if (!is_prime[i]) prime[cnt++] = i; for (int j = 0; j < cnt && i * prime[j] <= n; ++j) { is_prime[i * prime[j]] = true; if (i % prime[j] == 0) break; } } }

注意事项

1. gcd/lcm

   • 常用于分数约分、最简式、同余问题
   • 大数务必开long long避免溢出

2. 筛法选择

   • 数据范围n ≤ 1e7：埃氏筛足够
   • n ≥ 1e7或需要最小质因子信息：优先欧拉筛