如何求兩個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)

兩個(gè)正整數(shù)A和B的最大公約數(shù)為p，記為：(A，B)=p；最小公倍數(shù)為q，記為[a，b]=Q。

例1。求24和30的最大公約數(shù)和最小公倍數(shù)。

解法：對(duì)于比較簡(jiǎn)單的數(shù)，可以直接觀察到它們的公因式，適用于短除法：

1)將24和30兩個(gè)數(shù)分別除以24和30的公因數(shù)2，得到商數(shù)12和15；

2)用12和15的公因數(shù)3除12和15，得到商數(shù)4和5；

3) 4和5沒有大于1的公因數(shù)，短除法結(jié)束。

因?yàn)閮蓚€(gè)公因數(shù)2和3的乘積是：2*3=6，所以24和30的最大公約數(shù)是：(24，30)=6。

而且因?yàn)樗泄蜃雍妥罱K商的乘積是：2*3*4*5=120，

所以24和30的最小公倍數(shù)是：[24，30]=120。

例2。求221和493的最大公約數(shù)和最小公倍數(shù)。

解決方法：對(duì)于公因數(shù)不容易觀察到的數(shù)字，可以通過輾轉(zhuǎn)相除：

用較大的數(shù)除以較小的數(shù)，求余數(shù)：493/221=2，余數(shù)為51；以上述除數(shù)為被除數(shù)，余數(shù)為除數(shù)，然后求余數(shù)：221/51=4，余數(shù)為17；以上述除數(shù)為除數(shù)，余數(shù)為除數(shù)，余數(shù)為51/17=3，余數(shù)為0。當(dāng)余數(shù)為0時(shí)，倒數(shù)第二個(gè)余數(shù)就是這兩個(gè)數(shù)的最大公約數(shù)。所以221和493的最大公約數(shù)是：(221，493)=17。

而且因?yàn)閮蓚€(gè)數(shù)A和B的最大公約數(shù)P和最小公倍數(shù)Q的乘積pq等于這兩個(gè)數(shù)的乘積ab。所以q=(ab)/p。

所以221余數(shù)493的最小公倍數(shù)是：[221，493]=221*493/17=6409。

用C語言編程如下：

//求兩個(gè)數(shù)A和b的最大公約數(shù)P和最小公倍數(shù)Q。

#包含stdio.h

Int main () //注：兩個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)的乘積=這兩個(gè)數(shù)的乘積，即pq=ab，所以Q=AB/P。

{ int gys(int，int)；//函數(shù)原型：求最大公約數(shù)

int a，b，p；

printf(& amp；#039;請(qǐng)輸入兩個(gè)整數(shù)：a b(兩個(gè)數(shù)字用空格隔開):& amp#039;);scanf(& amp；#039;% d % d & amp#039;a，b)；

p=gys(a，b)；//調(diào)用函數(shù)求A和b的最大公約數(shù)p。

printf(& amp；#039;(%d，%d)=%d。#039;a，b，p)；//輸出最大公約數(shù)

printf(& amp；#039;[%d，% d]=% d & amp；#039;a，b，a * b/p)；//輸出最小公倍數(shù)(q=ab/p因?yàn)閜q=ab)

}

//求最大公約數(shù)函數(shù)：

Int gys(int x，int y) //函數(shù)頭行，其中x和y是形參。

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

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

{ r=x % y；//求余數(shù)

x=y；y=r；//輾轉(zhuǎn)反側(cè)

}

return(x)；//返回最大公約數(shù)x

}

兩個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)求最大公約數(shù)和最小公倍數(shù)練習(xí)。