問(wèn)題描述
求任意兩個(gè)正整數(shù)的最大公約數(shù)（GCD）。
問(wèn)題分析
如果有一個(gè)自然數(shù)a能被自然數(shù)b整除，則稱(chēng)a為b的倍數(shù)，b為a的約數(shù)。幾個(gè)自然數(shù)公有的約數(shù)，叫做這幾個(gè)自然數(shù)的公約數(shù)。公約數(shù)中最大的一個(gè)公約數(shù)，稱(chēng)為這幾個(gè)自然數(shù)的最大公約數(shù)。

根據(jù)約數(shù)的定義可知，某個(gè)數(shù)的所有約數(shù)必不大于這個(gè)數(shù)本身，幾個(gè)自然數(shù)的最大公約數(shù)必不大于其中任何一個(gè)數(shù)。要求任意兩個(gè)正整數(shù)的最大公約數(shù)即求出一個(gè)不大于其中兩者中的任何一個(gè)，但又能同時(shí)整除兩個(gè)整數(shù)的最大自然數(shù)。

算法設(shè)計(jì)
思路有兩種：第一種，采用窮舉法按從小到大（初值為1，最大值為兩個(gè)整數(shù)當(dāng)中較小的數(shù)）的順序?qū)⑺�有滿(mǎn)足條件的公約數(shù)列出，輸出其中最大的一個(gè)；第二種，按照從大（兩個(gè)整數(shù)中較小的數(shù)）到�。ǖ阶钚〉恼麛�(shù)1）的順序求出第一個(gè)能同時(shí)整除兩個(gè)整數(shù)的自然數(shù)，即為所求。

下面對(duì)第二種思路進(jìn)行詳細(xì)說(shuō)明。


兩個(gè)數(shù)的最大公約數(shù)有可能是其中的小數(shù)，所以在按從大到小順序找尋最大公約數(shù)時(shí)，循環(huán)變量i的初值從小數(shù)n開(kāi)始依次遞減，去尋找第一個(gè)能同時(shí)整除兩整數(shù)的自然數(shù)，并將其輸出。需要注意的是，雖然判定條件是i>0，但在找到第一個(gè)滿(mǎn)足條件的i值后，循環(huán)沒(méi)必要繼續(xù)下去，如，25和15，最大公約數(shù)是5，對(duì)于后面的4、3、2、1沒(méi)必要再去執(zhí)行，但此時(shí)判定條件仍然成立，要結(jié)束循環(huán)只能借助break語(yǔ)句。

程序流程圖：
下面是完整的代碼：

#include<stdio.h>
int main()
{
    int m, n, temp, i;
    printf("Input m & n:");
    scanf("%d%d", &m, &n);
    if(m<n) *比較大小，使得m中存儲(chǔ)大數(shù)，n中存儲(chǔ)小數(shù)*="" {="" *交換m和n的值*="" temp="m;" m="n;" n="temp;" }="" for(i="n;" i="">0; i--)  /*按照從大到小的順序?qū)ふ覞M(mǎn)足條件的自然數(shù)*/
        if(m%i==0 && n%i==0)
        {/*輸出滿(mǎn)足條件的自然數(shù)并結(jié)束循環(huán)*/
            printf("The GCD of %d and %d is: %d\n", m, n, i);
            break;
        }
    
    return 0;
}</n)></stdio.h>
運(yùn)行結(jié)果：
Input m & n:100 125
The GCD of 125 and 100 is: 25