【C語言程式設計】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;

}      

運作結果：

Input m & n:100 125

The GCD of 125 and 100 is: 25

不管你是轉行也好，初學也罷，進階也可，如果你想學程式設計，進階程式員~

【值得關注】我的 程式設計學習交流俱樂部 ！【點選進入】

全棧程式員正在等你加入~