最大公约数

计算两个整数的最大公约数可以使用欧几里得算法（Euclidean algorithm），也称为辗转相除法。

欧几里得算法的基本原理是，两个整数a和b（假设a >= b）的最大公约数等于b和a mod b的最大公约数，其中mod是取余运算符。

def gcd(a, b):
    """
    时间复杂度：O(n)
    空间复杂度：O(1)

    :param a:
    :param b:
    :return:
    """
    if b == 0:
        return a
    return gcd(b, a % b)


def gcd2(a, b):
    """
    时间复杂度：O(n)
    空间复杂度：O(1)

    :param a:
    :param b:
    :return:
    """
    while b > 0:
        r = a % b
        a = b
        b = r
    return a


print(gcd(12, 16))
print(gcd2(12, 16))