求最大公約數與最小公倍數?兩個正整數a,b的最大公約數為p，記作：(a,b)=p；最小公倍數為q，記作：[a,b]=q.，我來為大家科普一下關于求最大公約數與最小公倍數?以下内容希望對你有幫助!

求最大公約數與最小公倍數

兩個正整數a,b的最大公約數為p，記作：(a,b)=p；最小公倍數為q，記作：[a,b]=q.

例1.求24和30的最大公約數及最小公倍數。

解：對于比較簡單的數，可以直接觀察出它們的公因數，适合用短除法：

1） 先用24和30的公因數2分别去除兩個數24,30，得商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

#include <stdio.h>

int main () //注：兩個數的最大公約數與最小公倍數之積=這兩個數的乘積，即pq=ab，所以q=ab/p

{ int gys(int,int); //函數原型：求最大公約數

int a,b,p;

printf("請輸入兩個整數:a b（兩數用空格隔開）："); scanf("%d %d",&a,&b);

p=gys(a,b);//調用函數求a,b的最大公約數P

printf("(%d,%d)=%d，",a,b,p); //輸出最大公約數

printf("[%d,%d]=%d",a,b,a*b/p); //輸出最小公倍數(因pq=ab,所以q=ab/p)

}

//求最大公約數函數：

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

}

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!