c语言求最大公约数和最小公倍数算法总结

《c语言求最大公约数和最小公倍数算法总结》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、C语言求最大公约数和最小公倍数可以说是C语言编程学习中一个重点和难点，它常常作为计算机专业学生参加各种考试必须要把握的内容。其算法方面除常用的辗转相除法外、还可以根据数学定义法、递归调用法等。前提：假设求任意两个整数的最大公约数和最小公倍数，采用函数调用形式进行。1、辗转相除法辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理： ab=0gcd(a,b) =gcd(b,a mod b)b!=0根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下：①、函数嵌套调用其算法过程

2、为： 前提：设两数为a,b设其中a做被除数,b做除数，temp为余数1、大数放a中、小数放b中；2、求a/b的余数；3、若temp=0则b为最大公约数；4、如果temp!=0则把b的值给a、temp的值给a；5、返回第第二步；代码：intdivisor(inta,intb)/*自定义函数求两数的最大公约数*/{inttemp;/*定义整型变量*/if(a

3、值交换*/b=temp;}return(a);/*返回最大公约数到调用函数处*/}intmultiple(inta,intb)/*自定义函数求两数的最小公倍数*/{intdivisor(inta,intb);/*自定义函数返回值类型*/inttemp;temp=divisor(a,b);/*再次调用自定义函数，求出最大公约数*/return(a*b/temp);/*返回最小公倍数到主调函数处进行输出*/}#include"stdio.h"/*输入输出类头文件*/main(){intm,n,t1,t2;/*定义整型变量*/printf("pleaseinputtwointeg

4、ernumber:");/*提示输入两个整数*/scanf("%d%d",&m,&n);/*通过终端输入两个数*/t1=divisor(m,n);/*自定义主调函数*/t2=multiple(m,n);/*自定义主调函数*/printf("Thehigestcommondivisoris%d",t1);/*输出最大公约数*/printf("Thelowestcommonmultipleis%d",t2);/*输出最小公倍数*/}启示：请注意算法中变量数值之间的相互交换方法、如何取模、怎样进行自定义函数及主调函数与被调函数间的相互关系，函数参数的定义及对应关系特点，利

5、用控制语句如何实现。②、函数递归调用intgcd(inta,intb){ if(a%b==0)    returnb;   else       returngcd(b,a%b);}#include"stdio.h"main(){intm,n,t1;printf("pleaseinputtwointegernumber:");scanf("%d%d",&m,&n);t1=gcd(m,n);printf("Thehighestcommondivisoris%d",t1);/*最大公约数*/printf("Theleastcommonmultipleis%d",m*n/

6、t1);/*最小公倍数*/getch();}启示：采用递归调用法要注意递归终止条件的描述，只有找到递归变化的规律，才能有效地解决问题。2、穷举法（利用数学定义）穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。①、定义1：对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。代码为：intdivisor(inta,intb)/*自定义函数求两数的最大公约数*/{inttemp;/*定义义整型变量*/te

7、mp=(a>b)?b:a;/*采种条件运算表达式求出两个数中的最小值*/while(temp>0){if(a%temp==0&&b%temp==0)/*只要找到一个数能同时被a,b所整除，则中止循环*/break;temp--;/*如不满足if条件则变量自减，直到能被a,b所整除*/}return(temp);/*返回满足条件的数到主调函数处*/}#include"stdio.h"main(){intm,n,t1;printf("pleaseinputtwointegernumber:");scanf("%d%d"