前言

在實現之前我們先來了解一下什么是最大公約數，以及我們常用的計算最大公約數的方法或者說數學方法。

概念

最大公約數，也稱最大公因數、最大公因子。他是一個能夠被若干整數同時整除的整數，如果一個整數同時是幾個整數的約數，則稱這個整數為他們的公約數，公約數中最大的數成為最大公約數，1是任意若干的正整數的公約數。比如：一個數既是數A的約數，又是數B的約數，稱為A,B的公約數，A,B的公約數中最大的一個（可以包括AB自身）稱為AB的最大公約數，a，b的最大公約數記為（a，b），同樣的，a，b，c的最大公約數記為（a，b，c），多個整數的最大公約數也有同樣的記號。這么一大段可以概括為：

最大公約數：指兩個或多個整數共有約數中最大的一個。

(資料圖片)

求最大公約數的方法

常見的有質因數分解法、短除法、輾轉相除法、更相減損法。與最大公約數相對應的概念是最小公倍數，a，b的最小公倍數記為[a，b]。（先埋個小彩蛋：下一篇文章我們可以接著探索一下最小公倍數的計算方法）

短除法和輾轉相除法是我們在數學解題中常用的兩種方法。而且短除法也是我們在求二進制數時常用的方法，輾轉相除法求可用來求解不定方程的一組整數解，這是它在數學中最常見的應用，輾轉相除法處理大數時非常高效，它需要的步驟不會超過較小數的位數(十進制下)的五倍（加百利·拉梅(GabrielLamé)于1844年證明了這點，開創了計算復雜性理論）。輾轉相除法的運算速度為 O(n)，其中 n 為輸入數值的位數。

求解流程

本文通過窮舉法和輾轉相除法這兩種個方法來尋找最大公約數。下面我們來看看兩種的方法的具體流程：

窮舉法流程圖

輾轉相除法流程圖

輾轉相除法終止條件是余數=0

除數是最小公約數

算法實現

窮舉法

步驟:

代碼如下:

def Findgcd(x,y):    if x < y:        min = y    else:        min = x    for i in range(1, min+1):        if((x % i == 0) and (y % i == 0)):            Flag = i    return Flagx = int(input("請輸入第一個整數:"))y = int(input("請輸入第二個整數:"))print(x,",", y, "的最大公約數為:", Findgcd(x,y))

執行結果如下:

輾轉相除法

x = int(input("請輸入第一個整數:"))y = int(input("請輸入第二個整數:"))if x < y: #如果x
執行結果如下:
輾轉相除法優化
1.遞歸
def gcd(x , y):    if y == 0:        return x    else:        return gcd(y, x%y)a = int(input("請輸入第一個整數:"))b = int(input("請輸入第二個整數:"))print(x,",", y1, "的最大公約數為:",gcd(a,b))
2.非遞歸
x = int(input("請輸入第一個整數:"))y = int(input("請輸入第二個整數:"))y1  = y;while y:    x,y=y,x%yprint(x,",", y1, "的最大公約數為:",x)