Python輾轉相除法求最大公約數

一、什麼是輾轉相除法

輾轉相除法也被稱為歐幾里得算法，是一種求最大公約數的算法。它的基本思想就是利用兩個數的餘數相等可以得到這兩個數的最大公約數。

舉個例子，有兩個正整數a、b（a>b），用a除以b，得到商q和餘數r，即：

a = bq + r

如果r=0，則b就是最大公約數；否則，用b除以r，再得到商、餘數，如此重複，直到餘數為0為止。

二、算法實現

Python中的實現可以使用遞歸或者循環的方式。

1.遞歸實現

def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

遞歸實現的思路比較清晰，一直遞歸直到b=0為止。但是遞歸對於大數來說，會佔用大量的棧空間，導致棧溢出。

2.循環實現

def gcd(a, b):
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a

循環實現的思路是不斷對a、b進行求餘數，直到餘數為0，此時a的值即為最大公約數。循環實現的方式避免了遞歸的棧溢出問題，對於大數來說更加穩定。

三、算法優化

對於輾轉相除法來說，還有一些優化的方法可以提高算法效率。

1.輾轉相除法配合位移運算

def gcd(a, b):
    if a == b:
        return a
    if a == 0:
        return b
    if b == 0:
        return a
    if ~a & 1:
        if b & 1:
            return gcd(a >> 1, b)
        else:
            return gcd(a >> 1, b >> 1) <> 1)
    if a > b:
        return gcd((a - b) >> 1, b)
    else:
        return gcd((b - a) >> 1, a)

這種方法是將輾轉相除法和位移運算配合使用，可以大幅提高算法性能。對於較大的數來說，使用位移運算可以避免大量的除法運算，從而提高效率。

2.相鄰兩數的公約數

如果a、b中間有一個數c，使得a是c的倍數，b也是c的倍數，那麼c即為a、b的公約數。因此，可以先求出a、b的公共因子d，再求d的公共因子，直到無法再求出公共因子為止。

def gcd(a, b):
    if a == b:
        return a
    if a == 0:
        return b
    if b == 0:
        return a
    if ~a & 1:
        if b & 1:
            return gcd(a >> 1, b)
        else:
            return gcd(a >> 1, b >> 1) <> 1)
    if a > b:
        return gcd((a - b) >> 1, b)
    else:
        return gcd((b - a) >> 1, a)

def gcd_list(array):
    while len(array) > 1:
        a = array.pop()
        b = array.pop()
        c = gcd(a, b)
        array.append(c)
    return array[0]

這種方法可以提高算法效率，但是對於較大的數，可能需要先排除一些小的公共因子，以免出現內存溢出的情況。

四、算法應用

輾轉相除法是一個非常常用的算法，可以用來解決很多問題，比如計算兩個數的最大公約數、判斷一個數是否為質數等。

五、總結

Python的輾轉相除法非常容易實現，可以使用遞歸或循環的方式，也可以結合位移運算和公共因子來提高計算效率。應用廣泛，具有很高的實用性。