C語言求最大公約數

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

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

算法設計
思路有兩種：第一種，采用窮舉法按從小到大（初值為1，最大值為兩個整數當中較小的數）的順序將所有滿足條件的公約數列出，輸出其中最大的一個；第二種，按照從大（兩個整數中較小的數）到小（到最小的整數1）的順序求出第一個能同時整除兩個整數的自然數，即為所求。

下面對第二種思路進行詳細說明。


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

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

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