C語言利用輾轉(zhuǎn)相除法求最大公約數(shù)

1. 首先要明確幾個概念

最大公約數(shù)： 也叫最大公因數(shù)，是指倆個或多個整數(shù)公有約數(shù)中最大的一個。

例如，18 和 24的最大公約數(shù)是 6

最小公倍數(shù)：除0以外最小的一個公倍數(shù)就叫作這幾個整數(shù)的最小公倍數(shù)

例如，18 和 24的最小公倍數(shù)是 72

2. 輾轉(zhuǎn)相除法

用除數(shù)和余數(shù)反復(fù)做除法運算，當(dāng)余數(shù)為0時，取當(dāng)前算式除數(shù)為最大公約數(shù)

例如：求 1997 和 615 倆個正整數(shù)的最大公約數(shù)

因為：

1997 % 615 = 152
615 % 152 = 7
152 % 7 = 5
7 % 5 = 2
5 % 2 = 1
2 % 1 = 0

所以，1997 和 615 的最大公約數(shù)為 1

3. C語言代碼實現(xiàn)

#include <stdio.h>
int main()
{
?? ?int data1 = 0, data2 = 0;
?? ?int m = 0; ? ? //該變量是中間變量，不能放在while函數(shù)的內(nèi)部
?? ?scanf_s("%d %d", &data1, &data2);
?? ?while ((m = data1 % data2) != 0)
?? ?{
?? ??? ?data1 = data2;
?? ??? ?data2 = m;
?? ?}
?? ?printf("最大公約數(shù)為%d\n", data2);
?? ?return 0;
}

注意點：

對于求模運算符%，若是分?jǐn)?shù)形式求余數(shù)的話，如果分子小于分母，則分子就是余數(shù)。

例如：2 % 5 = 0

而當(dāng)不是分?jǐn)?shù)形式求余數(shù)的話，即例如：18 % 24 時，可將 % 左邊的內(nèi)容看成是分子，而 % 右邊的內(nèi)容看成是分母。所以 18 % 24 = 18

這里有一個誤區(qū)，不能將18 與 24 在都約去 6 的情況下去求它們的余數(shù)，所以 18 % 24（3 % 8）= 3 是錯誤的

而不管是 18 % 24 ，還是24 % 18 。它們的余數(shù)均不會成為0

如果知道了倆個數(shù)的最大公約數(shù)，那么其最小公倍數(shù)可以根據(jù)公式來確定

即最小公倍數(shù) = 倆個數(shù)的乘積 / 最大公約數(shù)

C語言求最大公約數(shù)常見思路

輾轉(zhuǎn)相除法

輾轉(zhuǎn)相除法又稱為歐幾里得算法，用于求兩數(shù)的最大公約數(shù)gcd(全稱為greatest common divisor)

注意兩數(shù)必須為非負(fù)整數(shù)a,b。用法為：用兩數(shù)中較大的數(shù)（a1）除以較小的數(shù)（b1），得到余數(shù)（r1），再用b1除以r1得到余數(shù)r2，之后再用r1除以r2，反復(fù)進(jìn)行，直到最后余數(shù)是0為止。最大公約數(shù)就是最后式子中的除數(shù)。

請看如下舉例：

 若用函數(shù)gcd(a,b)來表示，即gcd(a,b)=gcd(b,a%b)，我們可以這樣理解:3887 2231和2231 1656的最大公約數(shù)是相等的，依次類推、重復(fù)操作。

用表達(dá)式可以這樣來表示:gcd(3887,2231)=gcd(2231,1656)=gcd(1656,575)，直到最后到底gcd(a,b)=gcd(c,0)，即gcd(3887,2231)=gcd(23,0)。

這里的c為a和b的最大公約數(shù)。

下面來看輾轉(zhuǎn)相除法的圖像說明

下面看算法實現(xiàn):

算法實現(xiàn)一

代碼中的a就相當(dāng)于上述gcd(a,b)=gcd(c,0)中的c。當(dāng)然還有利用此原理的其他寫法，不過是大同小異，這里就不一一列舉了。這里的if語句其實是多余的，因為通過輾轉(zhuǎn)相除完全可以實現(xiàn)兩數(shù)之間的互換。

算法實現(xiàn)二（函數(shù)遞歸法）

 對輾轉(zhuǎn)相除足夠熟悉后，可以采用遞歸的方式，如算法實現(xiàn)三

算法實現(xiàn)三(遞歸思想)

總之一句話：除數(shù)除以余數(shù)，直到余數(shù)為0為止。

更相減損之術(shù)

更相減損之術(shù)出自我國《九章算術(shù)》，原文是這樣的：

可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。以等數(shù)約之。

算法過程：大數(shù)減小數(shù)，得到的差用來替換之前的大數(shù)，如此反復(fù)，直到得出來的差與上次的減數(shù)相等。此時的這個差就是兩者的最大公約數(shù)。

以 36 24為例(如下圖)：

 可以這樣表示：gcd(36,24)=gcd(24,12),即36 24和24 12的最大公約數(shù)是相等的。

下面來看代碼實現(xiàn)

 總歸一句話：用大數(shù)減去小數(shù)，知道減數(shù)和差相等。

最后，當(dāng)處理較大的數(shù)時，輾轉(zhuǎn)相除法雖然在時間上有明顯優(yōu)勢。但是，即使是這樣，輾轉(zhuǎn)相除法也同樣存在缺陷，其在處理較大的素因數(shù)(也叫質(zhì)因數(shù)，就是說一個數(shù)是另一個數(shù)的因數(shù)，本身又是質(zhì)數(shù)，就叫做另一個數(shù)的素因數(shù))時，缺陷就會顯現(xiàn)出來。

當(dāng)然，實現(xiàn)求取最大公約數(shù)還有很多其他方法，這里只進(jìn)行了常見思路的講解。

總結(jié)

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論