題目描述

求任意兩個正整數的最大公約數

問題分析

最大公因數，也稱最大公約數、最大公因子，指兩個或多個整數共有約數中最大的一個。a，b的最大公約數記為（a，b），同樣的，a，b，c的最大公約數記為（a，b，c），多個整數的最大公約數也有同樣的記號。求最大公約數有多種方法，常見的有質因數分解法、短除法、輾轉相除法、更相減損法。與最大公約數相對應的概念是最小公倍數，a，b的最小公倍數記為[a，b]。

——百度百科

最大公因數的求法有不少，本文我將采用窮舉法、輾轉相除法、更相減損法三種方法，求兩個正整數的最大公約數（最大公因數）。

代碼實現

方法一：窮舉法

窮舉法（列舉法），是最簡單最直觀的一種方法。

具體步驟為：先求出兩個數的最小值min（最大公約數一定小于等于兩個數的最小值），接著從最小值min遞減遍歷（循環結束條件為i > 0），如果遇到一個數同時為這兩個整數的因數，則使用break退出遍歷（退出循環），這時的遍歷值i即為兩個正整數的最大公約數。

#include <stdio.h>

/**
 * @brief 獲取兩個正整數的最大公因數（窮舉法）
 * @param num1  第一個正整數
 * @param num2  第二個正整數
 * @return      最大公因數
 */
int Get_Max_Comm_Divisor(int num1, int num2)
{
    int i = 0;
    //獲取兩個整數的最小值
    int min = num1 < num2 ? num1 : num2;

    //從兩個數的最小值開始遞減遍歷
    for(i = min; i > 0; i--)
    {
        //i為num1和num2的公倍數
        if(num1 % i == 0 && num2 % i == 0)
            break;
    }
    return i;
}

int main()
{
    int num1 = 0, num2 = 0;
    puts("請輸入兩個正整數.");
    scanf("%d%d", &num1, &num2);
    printf("最大公約數為%d.\n", Get_Max_Comm_Divisor(num1, num2));
    return 0;
}

運行結果

方法二：輾轉相除法

輾轉相除法又稱歐幾里得算法，是指用于計算兩個非負整數a，b的最大公約數。應用領域有數學和計算機兩個方面。計算公式gcd(a,b) = gcd(b,a mod b)。

.歐幾里得算法是用來求兩個正整數最大公約數的算法。古希臘數學家歐幾里得在其著作《The Elements》中最早描述了這種算法,所以被命名為歐幾里得算法。

擴展歐幾里得算法可用于RSA加密等領域。

舉例：

假如需要求 1997 和 615 兩個正整數的最大公約數,用歐幾里得算法，是這樣進行的：

1997 / 615 = 3 (余 152)

615 / 152 = 4(余7)

152 / 7 = 21(余5)

7 / 5 = 1 (余2)

5 / 2 = 2 (余1)

2 / 1 = 2 (余0)

至此，最大公約數為1

以除數和余數反復做除法運算，當余數為 0 時，取當前算式除數為最大公約數，所以就得出了 1997 和 615 的最大公約數 1。

——百度百科

數學學渣的我覺得這個小算法特別神奇，但我并不想深入研究（為什么能用輾轉相除求最大公因數呢），假如你想證明，可以自己試著簡單地證明一下，我就直接選擇強記了，嘿嘿。

雖然算法不好理解，但實現過程并不算難，按照輾轉相除的概念，轉換成代碼即可。

具體步驟：先求出兩個數num1和num2的余數remainder。然后將num2賦值給num1，讓上次取余時的除數num2作為下次取余時的被除數。同時將當前的余數remainder作為下次取余的除數。這樣一直地輾轉相除，直到余數為0，這時的除數num2就是我們要求的最大公因數。

一開始兩個數不需要區分大小，因為如果num1比num2小，那么取余的結果還是num1，這樣下次取余就變成了num2 % num1，即大的值在左邊，作為被除數）

#include <stdio.h>

/**
 * @brief 獲取兩個正整數的最大公因數（輾轉相除法）
 * @param num1  第一個正整數
 * @param num2  第二個正整數
 * @return      最大公因數
 */
int Get_Max_Comm_Divisor(int num1, int num2)
{
    int remainder = num1 % num2;  //余數

    while(remainder != 0)
    {
        num1 = num2;      //更新被除數
        num2 = remainder; //更新除數
        remainder = num1 % num2; //更新余數
    }
    return num2;  //最后的除數即為最大公因數
}

int main()
{
    int num1 = 0, num2 = 0;
    puts("請輸入兩個正整數.");
    scanf("%d%d", &num1, &num2);
    printf("最大公約數為%d.\n", Get_Max_Comm_Divisor(num1, num2));
    return 0;
}

運行結果

方法三：更相減損法

《九章算術》是中國古代的數學專著，其中的“更相減損術”可以用來求兩個數的最大公約數，原文是：

可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。

白話文譯文：

（如果需要對分數進行約分，那么）可以折半的話，就折半（也就是用2來約分）。如果不可以折半的話，那么就比較分母和分子的大小，用大數減去小數，互相減來減去，一直到減數與差相等為止，用這個相等的數字來約分。

——百度百科

還有一種叫輾轉相減的方法，好像和更相減損法相同，至少原理是一樣的。

輾轉相減法（求最大公約數），即尼考曼徹斯法，其特色是做一系列減法，從而求得最大公約數。例如 ：兩個自然數35和14，用大數減去小數，(35,14)->(21,14)->(7,14)，此時，7小于14，要做一次交換，把14作為被減數，即(14,7)->(7,7)，再做一次相減，結果為0，這樣也就求出了最大公約數7。

——百度百科

剛才的輾轉相除已經讓我很吃驚了，沒想到相減的方法。不過還是老規矩，直接用代碼去實現這個方法，而不去證明。

不同于輾轉相除法，更相減損法是需要考慮兩個數的大小的，只能用大的數作為被減數，小的作為減數。

實現步驟：首先求出兩個正整數num1和num2的差值diff，然后將num2賦值給num1，讓上次相減時的減數num2作為下次相減時的被減數。同時將當前的差值diff作為下次相減的減數。這樣一直地輾轉相減，直到差值為0，這時的除數num2就是我們要求的最大公因數。

#include <stdio.h>

/**
 * @brief 獲取兩個正整數的最大公因數（更相減損法）
 * @param num1  第一個正整數
 * @param num2  第二個正整數
 * @return      最大公因數
 */
int Get_Max_Comm_Divisor(int num1, int num2)
{
    //兩數相減的結果（取正值）
    int diff = num1 > num2 ? num1 - num2 : num2 - num1;

    while(diff != 0)
    {
        num1 = num2;   //更新被減數
        num2 = diff; //更新減數
        diff = num1 > num2 ? num1 - num2\
               : num2 - num1; //更新兩數相減的結果（取正值）
    }
    return num2;  //最后的減數即為最大公因數
}

int main()
{
    int num1 = 0, num2 = 0;
    puts("請輸入兩個正整數.");
    scanf("%d%d", &num1, &num2);
    printf("最大公約數為%d.\n", Get_Max_Comm_Divisor(num1, num2));
    return 0;
}

運行結果

至于哪種方法效率更高，感興趣的朋友可以去算算，我只知道窮舉是效率最低的。