最大公约数（GCD）

最大公约数（Greatest Common Divisor，简称GCD）是指两个或多个整数共有约数中最大的一个。在算法题目中，求两个数的最大公约数是一个常见的题型。

思路

解决最大公约数问题，最经典的方法是辗转相除法（也称欧几里得算法）。辗转相除法的思想是：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。

Python代码示例

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

# 示例
result = gcd(60, 48)
print(result)  # 输出 12

扩展阅读

想要了解更多关于算法的题目，可以访问LeetCode算法题库。

Python