C语言求最大公约数和最小公倍数算法.doc

C语言求最大公约数和最小公倍数算法C语言求最大公约数和最小公倍数可以说是C语言编程学习中一个重点和难点，它常常作为计算机专业学生参加各种考试必须要把握的内容。其算法方面除常用的辗转相除法外、还可以根据数学定义法、递归调用法等。下面结合我学习以来的笔记整理、总结几种常用的方法进行比较，以便能够更好的理解、应用、共勉。前提：假设求任意两个整数的最大公约数和最小公倍数，采用函数调用形式进行。1、辗转相除法辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理： a b=0gcd(a,b)= gcd(b,amodb) b!=0根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下：、函数嵌套调用其算法过程为：前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数1、大数放a中、小数放b中；2、求a/b的余数；3、若temp=0则b为最大公约数；4、如果temp!=0则把b的值给a、temp的值给a；5、返回第第二步；代码：int divisor (int a,int b) /*自定义函数求两数的最大公约数*/ int temp; /*定义整型变量*/ if(ab)?b:a; /*采种条件运算表达式求出两个数中的最小值*/ while(temp0) if (a%temp=0&b%temp=0) /*只要找到一个数能同时被a,b所整除，则中止循环*/ break; temp-; /*如不满足if条件则变量自减，直到能被a,b所整除*/ return (temp); /*返回满足条件的数到主调函数处*/#include stdio.hmain() int m,n,t1;printf(please input two integer number:); scanf(%d%d,&m,&n); t1=divisor(m,n); printf(The higest common divisor is %dn,t1); getch();、定义2：对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除，则该和数即为所求的最小公倍数。代码为：int multiple (int a,int b) int p,q,temp; p=(ab)?a:b; /*求两个数中的最大值*/ q=(ab)?b:a; /*求两个数中的最小值*/ temp=p; /*最大值赋给p为变量自增作准备*/ while(1) /*利用循环语句来求满足条件的数值*/ if(p%q=0) break; /*只要找到变量的和数能被a或b所整除，则中止循环*/ p+=temp; /*如果条件不满足则变量自身相加*/ return (p);#include stdio.hmain() int m,n,t2; printf(please input two integer number:); scanf(%d%d,&m,&n); t2=multiple(m,n); printf(The least common multiple is %dn,t2); getch();启示：根据数学定义求任意两个正整数的最大公约数和最小公倍数，相对辗转相除法来说，易懂，容易被学习者接受，但也请读者注意强制退出循环过程的条件、变量的特点及