第C語言求兩個正整數(shù)的最大公約數(shù)示例代碼目錄前言1.窮舉法2.歐幾里得算法（輾轉相除法）3.遞歸方法附：相減法總結

前言

兩個正整數(shù)的最大公約數(shù)（GreatestCommonDivisor,GCD）是能夠整除這兩個整數(shù)的最大整數(shù)。兩個正整數(shù)的最大公約數(shù)的求法有多種解答，本文就三種方法做詳細介紹：窮舉法、歐幾里得算法（輾轉相除法）、遞歸方法。

我們從一道問題來引入：編寫計算最大公約數(shù)的函數(shù)Gcd()，在主函數(shù)中調用該函數(shù)計算并輸出從鍵盤任意輸入的最大公約數(shù)。

1.窮舉法

根據(jù)最大公約數(shù)的定義，我們可以采用一種最簡單的方法——窮舉法來編寫代碼。由于a和b的最大公約數(shù)不可能比a和b中的較小者還大，否則一定不能整除它，因此，先找到a和b中的較小者t，然后從t開始逐次減1嘗試每種可能，即檢驗t到1之間的所有整數(shù)，第一個滿足公約數(shù)條件的t，就是a和b的最大公約數(shù)。據(jù)此我們可編寫函數(shù)Gcd()如下：

//函數(shù)功能：計算a和b的最大公約數(shù)，輸入負數(shù)時返回-1

intGcd(inta,intb)

inti,t;

if(a=0||b=0)

return-1;

t=aba:b;

for(i=t;ii--)

if(a%i==0b%i==0)

returni;

return1;

}

這種方法簡單暴力，思維量小，但效率較低，且當兩個正整數(shù)都較大，且最大公約數(shù)為1時，循環(huán)的次數(shù)為較小數(shù)的值，可想而知所需時間會很長。

2.歐幾里得算法（輾轉相除法）

下面介紹一種求最大公約數(shù)較常用的辦法：歐幾里得算法（輾轉相除法）。

忽略數(shù)學原理，我們有如下算法：對正整數(shù)a和b，連續(xù)進行求余運算，直到余數(shù)為0為止，此時非0的除數(shù)就是最大公約數(shù)。設r=amodb表示a除以b的余數(shù)，若r≠0，則將b作為新的a，r作為新的b，重復amodb運算，直到r=0為止，此時b為所求的最大公約數(shù)。例如，50和15的最大公約數(shù)的求解過程可表示為：Gcd(50,15)=Gcd(15,5)=Gcd(5,0)=5。

用這種算法可編寫函數(shù)Gcd()如下：

//函數(shù)功能：計算a和b的最大公約數(shù)，輸入負數(shù)時返回-1

intGcd(inta,intb)

intr;

if(a=0||b=0)

return-1;

r=a%b;

a=b;

b=r;

}while(r!=0);

returna;

}

我們也可以考慮使用遞歸實現(xiàn)如下：

//函數(shù)功能：計算a和b的最大公約數(shù)，輸入負數(shù)時返回-1

intGcd(inta,intb)

if(a=0||b=0)

return-1;

if(a%b==0)

returnb;

else

returnGcd(b,a%b);

}

3.遞歸方法

對于最大公約數(shù)，還有3條性質：

性質1如果ab，則a和b與a-b和b的最大公約數(shù)相同；

性質2如果ba，則a和b與a和b-a的最大公約數(shù)相同；

性質3如果a=b，則a和b的最大公約數(shù)與a值和b值相同。

對正整數(shù)a和b，當ab時，若a中含有與b相同的公約數(shù)，則a中去掉b后剩余的部分a-b中也應含有與b相同的公約數(shù)，對a-b和b計算公約數(shù)就相當于對a和b計算公約數(shù)。反復使用最大公約數(shù)的3條性質，直到a和b相等為止，這時，a或b就是它們的最大公約數(shù)。

這就是所謂的第三種方法：遞歸方法。雖然此法被稱為遞歸方法，但只是思想方法運用了遞歸的方法，并不代表只能使用遞歸實現(xiàn)。我們同樣可以通過非遞歸和遞歸兩種手段編寫函數(shù)Gcd()。非遞歸實現(xiàn)如下：

//函數(shù)功能：計算a和b的最大公約數(shù)，輸入負數(shù)時返回-1

intGcd(inta,intb)

if(a=0||b=0)

return-1;

while(a!=b)

if(ab)

a=a-b;

elseif(ba)

b=b-a;

returna;

}

編寫遞歸函數(shù)如下：

//函數(shù)功能：計算a和b的最大公約數(shù)，輸入負數(shù)時返回-1

intGcd(inta,intb)

if(a=0||b=0)

return-1;

if(a==b)

returna;

elseif(ab)

returnGcd(a-b,b);

else

returnGcd(a,b-a);

}

以上就是三種計算最大公約數(shù)的算法，可使用如下主函數(shù)來調用函數(shù)Gcd()，計算最大公約數(shù)：

#includestdio.h

intGcd(inta,intb);

intmain(void)

inta,b,c;

printf("Inputa,b:");

scanf("%d,%d",a,

c=Gcd(a,b);

if(c!=-1)

printf("GreatestCommonDivisorof%dand%dis%d\n",a,b,c);

else

printf("Inputnumbershouldbepositive!\n");

return0;

}

求兩個正整數(shù)的最大公約數(shù)的過程，實質上是使用最大公約數(shù)的定義及性質求解的過程，對此感興趣的伙伴們可以自己研究相關數(shù)學原理與證明。

附：相減法

這種方法比較易于理解，原理是先判斷兩個正整數(shù)大小，并將較大數(shù)與較小數(shù)的差值賦給較大數(shù)，循環(huán)此步驟直到兩數(shù)相等，此時得出最大公約數(shù)。

代碼如下：

#includestdio.h

intmain()

intm,n;

printf("請輸入兩個正整數(shù):");

scanf("%d%d",m,

printf("%d%和%d的最大公約數(shù)是",m,n);

while(m!=n)

if(mn)

m=m-