前言

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

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

1.窮舉法

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

//函數(shù)功能：計(jì)算a和b的最大公約數(shù)，輸入負(fù)數(shù)時(shí)返回-1
int Gcd(int a, int b)
{
    int i, t;
    if (a <=0 || b <= 0)
        return -1;
    t = a < b ? a : b;
    for (i=t; i>0; i--)
    {
        if (a%i==0 && b%i==0)
            return i;
    }
    return 1;
}

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

2.歐幾里得算法（輾轉(zhuǎn)相除法）

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

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

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

//函數(shù)功能：計(jì)算a和b的最大公約數(shù)，輸入負(fù)數(shù)時(shí)返回-1
int Gcd(int a, int b)
{
    int r;
    if (a <= 0 || b <= 0)
        return -1;
    do{
        r = a % b;
        a = b;
        b = r;
    } while (r != 0);
    return a;
}

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

//函數(shù)功能：計(jì)算a和b的最大公約數(shù)，輸入負(fù)數(shù)時(shí)返回-1
int Gcd(int a, int b)
{
    if (a <= 0 || b <= 0)
        return -1;
    if (a % b == 0)
        return b;
    else
        return Gcd(b, a % b);
}

3.遞歸方法

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

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

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

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

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

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

//函數(shù)功能：計(jì)算a和b的最大公約數(shù)，輸入負(fù)數(shù)時(shí)返回-1
int Gcd(int a, int b)
{
    if (a <= 0 || b <= 0)
        return -1;
    while (a != b)
    {
        if (a > b)
            a = a - b;
        else if (b > a)
            b = b - a;
    }
    return a;
}

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

//函數(shù)功能：計(jì)算a和b的最大公約數(shù)，輸入負(fù)數(shù)時(shí)返回-1
int Gcd(int a, int b)
{
    if (a <= 0 || b <= 0)
        return -1;
    if (a == b)
        return a;
    else if (a > b)
        return Gcd(a-b, b);
    else
        return Gcd(a, b-a);
}

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

#include <stdio.h>
int Gcd(int a, int b);
int main(void)
{
    int a, b, c;
    printf("Input a,b:");
    scanf("%d,%d", &a, &b);
    c = Gcd(a,b);
    if (c != -1)
        printf("Greatest Common Divisor of %d and %d is %d\n", a, b, c);
    else
        printf("Input number should be positive!\n");
    return 0;
}

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

附：相減法

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

代碼如下：

#include<stdio.h>

int main()

{

	int m,n;

	printf("請(qǐng)輸入兩個(gè)正整數(shù):");

	scanf("%d %d",&m,&n);

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

    while(m!=n)

	{

		if(m>n)

		{

			m=m-n;

		}else

		{

			n=n-m;

		}	

	}

	printf("%d",n);

	return 0;

} 

參考文獻(xiàn)：

蘇小紅 王甜甜 趙玲玲 范江波 車萬翔 等編著 王宇穎 主審，C語言程序設(shè)計(jì)學(xué)習(xí)指導(dǎo)（第4版），高等教育出版社，P57-60.

總結(jié)