尧图网站建设 
一、项目前言在算法刷题、程序竞赛、数学计算开发中素数筛选、最大公约数、最小公倍数、快速幂是最基础且高频使用的四大数学算法。本文使用纯C语言从零实现四种核心算法埃拉托斯特尼筛法批量筛选素数欧几里得算法递归求最大公约数 GCD最小公倍数 LCM 推导实现快速幂算法大数取模幂运算所有代码无第三方依赖、可直接编译运行适合新手学习、算法入门、期末作业、竞赛基础模板使用。二、各算法核心原理详解2.1 埃拉托斯特尼筛法素数筛选核心原理素数的倍数一定不是素数。1、初始化一个布尔数组默认所有数都是素数true2、从2开始遍历若当前数是素数标记它的所有平方及后续倍数为非素数3、遍历结束后数组中为true的下标即为素数。优势批量筛选区间素数时间复杂度 $$O(n\log\log n)$$远优于暴力枚举。2.2 最大公约数 GCD欧几里得递归算法核心公式$$gcd(a,b) gcd(b,a \bmod b)$$递归终止条件当 b 0 时a 即为最大公约数。2.3 最小公倍数 LCM依托最大公约数推导核心公式$$lcm(a,b) \frac{a \times b}{gcd(a,b)}$$代码中使用(a/gcd(a,b))*b写法先除后乘避免数据溢出。2.4 快速幂算法幂取模运算传统幂运算循环相乘效率极低且大数极易溢出。快速幂基于二进制拆分思想将幂次二分时间复杂度降至 $$O(\log n)$$。同时结合取模运算解决大数幂运算溢出问题是算法竞赛高频考点。三、完整可运行源码已修复BUG原代码存在括号嵌套逻辑错误、输出无换行等问题下面是修复后完整版源码可直接编译运行#include stdio.h #include stdbool.h #include math.h //使用埃拉托斯特尼筛法计算素数 void sieveOfEratosthenes(int n){ // 创建一个布尔数组prime[0..n]并初始化为true bool prime[n1]; memset(prime,true,sizeof(prime)); for(int p2;p*pn;p){ // 如果prime[p]没有被改变则它是一个素数 if(prime[p]true){ //更新所有p的倍数 for(int ip*p;in;ip){ prime[i]false; } } } //打印所有素数 printf(小于等于%d的素数:\n,n); for(int p2;pn;p) if(prime[p]) printf(%d,p); printf(\n); } //计算最大公约数(递归方法) int gcd(int a,int b){ if(b0) return a; return gcd(b,a%b); } //计算最小公倍数 int lcm(int a,int b){ return (a/gcd(a,b))*b; } //快速幂算法(计算x^n % mod) int powerMod(int x,int n,int mod){ int result1; xx%mod;//防止溢出 while(n0){ //如果n是奇数,将当前x乘入结果 if(n1) result(result*x)%mod; //n必须是偶数现在 nn1; x(x*x)%mod; } return result; } int main() { printf(埃拉托斯特尼筛法测试:\n); sieveOfEratosthenes(30); printf(\n最大公约数测试:\n); int a 48, b 18; printf(gcd(%d, %d) %d\n, a, b, gcd(a, b)); printf(\n最小公倍数测试:\n); printf(lcm(%d, %d) %d\n, a, b, lcm(a, b)); printf(\n快速幂测试:\n); int x 2, n 10, mod 1000000007; printf(%d^%d mod %d %d\n, x, n, mod, powerMod(x, n, mod)); return 0; }四、代码模块逐行解析4.1 埃氏筛素数筛选函数1、通过memset批量初始化数组默认所有数字为素数2、只遍历到p*p n减少循环次数提升效率3、从p*p开始标记倍数避免重复标记4、最后遍历数组输出所有标记为素数的数字。4.2 GCD最大公约数递归利用欧几里得算法递归迭代不断将(a,b)转化为(b,a%b)直到余数为0此时的a就是最大公约数。代码极简、递归深度低、效率极高。4.3 LCM最小公倍数规避直接a*b导致的溢出问题采用先除后乘的计算方式是工程和算法刷题的标准写法。4.4 快速幂取模1、先对底数取模防止初始数据溢出2、通过位运算n1判断幂次是否为奇数效率高于取模运算3、通过右移运算n1实现幂次二分4、每一步运算都取模保证数据不溢出。五、程序运行结果编译运行程序后控制台输出结果如下 埃拉托斯特尼筛法测试 小于等于30的素数: 2 3 5 7 11 13 17 19 23 29 最大公约数测试 gcd(48, 18) 6 最小公倍数测试 lcm(48, 18) 144 快速幂测试 2^10 mod 1000000007 1024六、算法知识点总结埃氏筛适合批量筛选固定区间所有素数是素数问题最优入门算法GCD数论基础广泛用于约分、同余方程、分数计算LCM依托GCD实现常用于周期计算、公倍数问题快速幂解决大数幂运算超时、溢出问题是ACM、LeetCode高频算法。七、拓展优化方向1、将埃氏筛改为线性筛欧拉筛进一步优化时间复杂度2、优化GCD为迭代写法避免递归栈溢出3、快速幂支持long long类型适配更大数值计算4、封装为工具函数库可直接导入其他项目使用。 C语言四大常用数学算法实现（埃氏筛、GCD、LCM、快速幂）
一、项目前言在算法刷题、程序竞赛、数学计算开发中素数筛选、最大公约数、最小公倍数、快速幂是最基础且高频使用的四大数学算法。本文使用纯C语言从零实现四种核心算法埃拉托斯特尼筛法批量筛选素数欧几里得算法递归求最大公约数 GCD最小公倍数 LCM 推导实现快速幂算法大数取模幂运算所有代码无第三方依赖、可直接编译运行适合新手学习、算法入门、期末作业、竞赛基础模板使用。二、各算法核心原理详解2.1 埃拉托斯特尼筛法素数筛选核心原理素数的倍数一定不是素数。1、初始化一个布尔数组默认所有数都是素数true2、从2开始遍历若当前数是素数标记它的所有平方及后续倍数为非素数3、遍历结束后数组中为true的下标即为素数。优势批量筛选区间素数时间复杂度 $$O(n\log\log n)$$远优于暴力枚举。2.2 最大公约数 GCD欧几里得递归算法核心公式$$gcd(a,b) gcd(b,a \bmod b)$$递归终止条件当 b 0 时a 即为最大公约数。2.3 最小公倍数 LCM依托最大公约数推导核心公式$$lcm(a,b) \frac{a \times b}{gcd(a,b)}$$代码中使用(a/gcd(a,b))*b写法先除后乘避免数据溢出。2.4 快速幂算法幂取模运算传统幂运算循环相乘效率极低且大数极易溢出。快速幂基于二进制拆分思想将幂次二分时间复杂度降至 $$O(\log n)$$。同时结合取模运算解决大数幂运算溢出问题是算法竞赛高频考点。三、完整可运行源码已修复BUG原代码存在括号嵌套逻辑错误、输出无换行等问题下面是修复后完整版源码可直接编译运行#include stdio.h #include stdbool.h #include math.h //使用埃拉托斯特尼筛法计算素数 void sieveOfEratosthenes(int n){ // 创建一个布尔数组prime[0..n]并初始化为true bool prime[n1]; memset(prime,true,sizeof(prime)); for(int p2;p*pn;p){ // 如果prime[p]没有被改变则它是一个素数 if(prime[p]true){ //更新所有p的倍数 for(int ip*p;in;ip){ prime[i]false; } } } //打印所有素数 printf(小于等于%d的素数:\n,n); for(int p2;pn;p) if(prime[p]) printf(%d,p); printf(\n); } //计算最大公约数(递归方法) int gcd(int a,int b){ if(b0) return a; return gcd(b,a%b); } //计算最小公倍数 int lcm(int a,int b){ return (a/gcd(a,b))*b; } //快速幂算法(计算x^n % mod) int powerMod(int x,int n,int mod){ int result1; xx%mod;//防止溢出 while(n0){ //如果n是奇数,将当前x乘入结果 if(n1) result(result*x)%mod; //n必须是偶数现在 nn1; x(x*x)%mod; } return result; } int main() { printf(埃拉托斯特尼筛法测试:\n); sieveOfEratosthenes(30); printf(\n最大公约数测试:\n); int a 48, b 18; printf(gcd(%d, %d) %d\n, a, b, gcd(a, b)); printf(\n最小公倍数测试:\n); printf(lcm(%d, %d) %d\n, a, b, lcm(a, b)); printf(\n快速幂测试:\n); int x 2, n 10, mod 1000000007; printf(%d^%d mod %d %d\n, x, n, mod, powerMod(x, n, mod)); return 0; }四、代码模块逐行解析4.1 埃氏筛素数筛选函数1、通过memset批量初始化数组默认所有数字为素数2、只遍历到p*p n减少循环次数提升效率3、从p*p开始标记倍数避免重复标记4、最后遍历数组输出所有标记为素数的数字。4.2 GCD最大公约数递归利用欧几里得算法递归迭代不断将(a,b)转化为(b,a%b)直到余数为0此时的a就是最大公约数。代码极简、递归深度低、效率极高。4.3 LCM最小公倍数规避直接a*b导致的溢出问题采用先除后乘的计算方式是工程和算法刷题的标准写法。4.4 快速幂取模1、先对底数取模防止初始数据溢出2、通过位运算n1判断幂次是否为奇数效率高于取模运算3、通过右移运算n1实现幂次二分4、每一步运算都取模保证数据不溢出。五、程序运行结果编译运行程序后控制台输出结果如下 埃拉托斯特尼筛法测试 小于等于30的素数: 2 3 5 7 11 13 17 19 23 29 最大公约数测试 gcd(48, 18) 6 最小公倍数测试 lcm(48, 18) 144 快速幂测试 2^10 mod 1000000007 1024六、算法知识点总结埃氏筛适合批量筛选固定区间所有素数是素数问题最优入门算法GCD数论基础广泛用于约分、同余方程、分数计算LCM依托GCD实现常用于周期计算、公倍数问题快速幂解决大数幂运算超时、溢出问题是ACM、LeetCode高频算法。七、拓展优化方向1、将埃氏筛改为线性筛欧拉筛进一步优化时间复杂度2、优化GCD为迭代写法避免递归栈溢出3、快速幂支持long long类型适配更大数值计算4、封装为工具函数库可直接导入其他项目使用。