c語言求最大公約數

　　程式碼如下：

　　#include

　　int main()

　　{

　　int i,a,b,t;

　　scanf(%d%d,&a,&b);//輸入數a,b

　　if(a>b)//比較a,b大小，如果a>b則交換，結果為a= 2; i--)//以較小的a為基數，每內次i減小1迴圈求最大公容約數

　　{

　　if (a % i == 0 && b % i == 0)//如果兩數均能整除某數則該數為最大公約數

　　{

　　printf(最大公約數是：%dn,i);

　　break;//已得到最大公約數後跳出迴圈

　　}

　　}

　　if(i==1)//若迴圈到最後仍無最大公約數則i=1

　　printf(兩數只能同時被1整除！n);

　　return 0;

　　}

　　求最大公約數有多種方法，常見的有質因數分解法、短除法、輾轉相除法、更相減損法。如果有一個自然數a能被自然數b整除，則稱a為b的倍數，b為a的約數。幾個自然數公有的約數，叫做這幾個自然數的公約數。公約數中最大的一個公約數，稱為這幾個自然數的最大公約數。

　　輾轉相除法使用到的原理很聰明也很簡單，假設用f（x,y）表示x，y的最大公約數，取k=x/y，b=x%y，則x=ky+b，如果一個數能夠同時整除x和y，則必能同時整除b和y；而能夠同時整除b和y的數也必能同時整除x和y，即x和y的公約數與b和y的公約數是相同的，其最大公約數也是相同的，則有f（x,y）=f（y,x%y）（y>0），如此便可把原問題轉化為求兩個更小數的最大公約數，直到其中一個數為0，剩下的另外一個數就是兩者最大的公約數。

　　例如，12和30的公約數有：1、2、3、6，其中6就是12和30的最大公約數。

　　方法一：

　　質因數分解法：把幾個數先分別分解質因數，再把各數中的全部公有的質因數和獨有的質因數提取出來連乘，所得的積就是這幾個數的最小公倍數。

　　方法二：

　　短除法：先用這幾個數的公約數連續去除，一直除到所有的商互質為止，然後把所有的除數連乘起來，所得的積就是這幾個數的最大公約數。

　　方法三：

　　輾轉相除法：先求出其中任意兩個數的最大公約數，再求這個最大公約數與第三個數的最大公約數，依次求下去，直到最後一個數為止。最後所得的那個最大公約數，就是所有這