gcd/lcm + 素数判断与筛法

张开发
• 2026/4/20 0:36:20 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

gcd/lcm + 素数判断与筛法
一、最大公约数 gcd1. 定义与性质最大公约数gcd(a,b)是两个数公共约数中最大的一个。常用性质gcd(a, 0) agcd(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)∗bint lcm(int a, int b) { return a / gcd(a, b) * b; }三、埃拉托斯特尼筛法埃氏筛用于批量预处理 1~n 内所有素数时间复杂度O(n log log n)。初始假设所有数都是素数从 2 开始将每个素数的所有倍数标记为合数最终未被标记的即为素数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; } } }注意事项gcd/lcm常用于分数约分、最简式、同余问题大数务必开long long避免溢出筛法选择数据范围n ≤ 1e7埃氏筛足够n ≥ 1e7或需要最小质因子信息优先欧拉筛

更多文章