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 ~b & 1:
        return gcd(a, b >> 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 ~b & 1:
        return gcd(a, b >> 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的辗转相除法非常容易实现，可以使用递归或循环的方式，也可以结合位移运算和公共因子来提高计算效率。应用广泛，具有很高的实用性。