最大公约数和最小公倍数算法

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

假设求任意两个整数的最大公约数和最小公倍数，采用函数调用形式进行。

1、辗转相除法

辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理：

a b=0

gcd(a,b) =

gcd(b,a mod b) 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(a

while(b!=0) /*通过循环求两数的余数，直到余数为0*/ {

temp=a%b;

a=b; /*变量数值交换*/ b=temp; }

return (a); /*返回最大公约数到调用函数处*/ }

int multiple (int a,int b) /*自定义函数求两数的最小公倍数*/ {

int divisor (int a,int b); /*自定义函数返回值类型*/ int temp;

temp=divisor(a,b); /*再次调用自定义函数，求出最大公约数*/ return (a*b/temp); /*返回最小公倍数到主调函数处进行输出*/ }

#include \ /*输入输出类头文件*/ main() {

int m,n,t1,t2; /*定义整型变量*/

printf(\*提示输入两个整数*/ scanf(\ /*通过终端输入两个数*/ t1=divisor(m,n); /*自定义主调函数*/ t2=multiple(m,n); /*自定义主调函数*/

printf(\higest common divisor is %d\\n\ /*输出最大公约数*/ printf(\ t2); /*输出最小公倍数*/ }

②、函数递归调用

int gcd (int a,int b) { if(a%b==0)

return b;

else

return gcd(b,a%b); }

#include \main() {

int m,n,t1;

printf(\ scanf(\t1=gcd(m,n);

printf(\/*最大公约数*/ printf(\/*最小公倍数*/ }

启示：采用递归调用法要注意递归终止条件的描述，只有找到递归变化的规律，才能有效地解决问题。

2、穷举法（利用数学定义）

穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。

①、定义1：对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被

a和b所整除，则temp即为最大公约数。

代码为：

int divisor (int a,int b) /*自定义函数求两数的最大公约数*/ {

int temp; /*定义义整型变量*/

temp=(a>b)?b:a; /*采种条件运算表达式求出两个数中的最小值*/ while(temp>0) {

if (a%temp==0&&b%temp==0) /*只要找到一个数能同时被a,b所整除，则中止循环*/ break;

temp--; /*如不满足if条件则变量自减，直到能被a,b所整除*/ }

return (temp); /*返回满足条件的数到主调函数处*/ }

#include \main() {

int m,n,t1;

printf(\ scanf(\ t1=divisor(m,n);

printf(\}

②、定义2：对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除，则该和数即为所求的最小公倍数。

代码为：

int multiple (int a,int b) {

int p,q,temp;

p=(a>b)?a:b; /*求两个数中的最大值*/ q=(a>b)?b:a; /*求两个数中的最小值*/

temp=p; /*最大值赋给p为变量自增作准备*/ while(1) /*利用循环语句来求满足条件的数值*/ {

if(p%q==0)

break; /*只要找到变量的和数能被a或b所整除，则中止循环*/ p+=temp; /*如果条件不满足则变量自身相加*/ }

return (p); }

#include \main() {

int m,n,t2;

printf(\ scanf(\ t2=multiple(m,n);

printf(\ }