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: %dn", m, n, i);
            break;
        }
   
    return 0;
}

執行結果：
Input m & n:100 125
The GCD of 125 and 100 is: 25