題目描述

求任意兩個正整數(shù)的最大公約數(shù)

問題分析

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

——百度百科

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

代碼實現(xiàn)

方法一：窮舉法

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

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

#include <stdio.h>

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

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

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

運行結(jié)果

方法二：輾轉(zhuǎn)相除法

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

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

擴展歐幾里得算法可用于RSA加密等領(lǐng)域。

舉例：

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

1997 / 615 = 3 (余 152)

615 / 152 = 4(余7)

152 / 7 = 21(余5)

7 / 5 = 1 (余2)

5 / 2 = 2 (余1)

2 / 1 = 2 (余0)

至此，最大公約數(shù)為1

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

——百度百科

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

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

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

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

#include <stdio.h>

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

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

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

運行結(jié)果

方法三：更相減損法

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

可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。以等數(shù)約之。

白話文譯文：

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

——百度百科

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

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

——百度百科

剛才的輾轉(zhuǎn)相除已經(jīng)讓我很吃驚了，沒想到相減的方法。不過還是老規(guī)矩，直接用代碼去實現(xiàn)這個方法，而不去證明。

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

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

#include <stdio.h>

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

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

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

運行結(jié)果

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

以上就是C語言實現(xiàn)求最大公約數(shù)的三種方法的詳細內(nèi)容，更多關(guān)于C語言求最大公約數(shù)的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論