如何求两个数的最大公约数和最小公倍数

两个正整数A和B的最大公约数为p，记为：(A，B)=p；最小公倍数为q，记为[a，b]=Q。

例1。求24和30的最大公约数和最小公倍数。

解法：对于比较简单的数，可以直接观察到它们的公因式，适用于短除法：

1)将24和30两个数分别除以24和30的公因数2，得到商数12和15；

2)用12和15的公因数3除12和15，得到商数4和5；

3) 4和5没有大于1的公因数，短除法结束。

因为两个公因数2和3的乘积是：2*3=6，所以24和30的最大公约数是：(24，30)=6。

而且因为所有公因子和最终商的乘积是：2*3*4*5=120，

所以24和30的最小公倍数是：[24，30]=120。

例2。求221和493的最大公约数和最小公倍数。

解决方法：对于公因数不容易观察到的数字，可以通过辗转相除：

用较大的数除以较小的数，求余数：493/221=2，余数为51；以上述除数为被除数，余数为除数，然后求余数：221/51=4，余数为17；以上述除数为除数，余数为除数，余数为51/17=3，余数为0。当余数为0时，倒数第二个余数就是这两个数的最大公约数。所以221和493的最大公约数是：(221，493)=17。

而且因为两个数A和B的最大公约数P和最小公倍数Q的乘积pq等于这两个数的乘积ab。所以q=(ab)/p。

所以221余数493的最小公倍数是：[221，493]=221*493/17=6409。

用C语言编程如下：

//求两个数A和b的最大公约数P和最小公倍数Q。

#包含stdio.h

Int main () //注：两个数的最大公约数和最小公倍数的乘积=这两个数的乘积，即pq=ab，所以Q=AB/P。

{ int gys(int，int)；//函数原型：求最大公约数

int a，b，p；

printf(& amp；#039;请输入两个整数：a b(两个数字用空格隔开):& amp#039;);scanf(& amp；#039;% d % d & amp#039;a，b)；

p=gys(a，b)；//调用函数求A和b的最大公约数p。

printf(& amp；#039;(%d，%d)=%d。#039;a，b，p)；//输出最大公约数

printf(& amp；#039;[%d，% d]=% d & amp；#039;a，b，a * b/p)；//输出最小公倍数(q=ab/p因为pq=ab)

}

//求最大公约数函数：

Int gys(int x，int y) //函数头行，其中x和y是形参。

{ int r=1；//使r不为0

while(r！=0) //折腾分：

{ r=x % y；//求余数

x=y；y=r；//辗转反侧

}

return(x)；//返回最大公约数x

}

两个数的最大公约数和最小公倍数求最大公约数和最小公倍数练习。