算法原理

辗转相除法基于以下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

具体步骤：

1. 用较大数除以较小数，得到余数
2. 用较小数除以余数，再得到新的余数
3. 重复这个过程，直到余数为0
4. 最后的除数即为最大公约数

Python实现

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

# 示例
num1 = 48
num2 = 18
print(f"{num1}和{num2}的最大公约数是: {gcd_euclidean(num1, num2)}")

优点：效率高，时间复杂度为O(log(min(a,b)))
缺点：依赖取模运算

算法原理

更相减损术是中国古代数学家的智慧结晶，出自《九章算术》。

具体步骤：

1. 如果两个数都是偶数，先用2约简
2. 用较大的数减去较小的数
3. 用差值和较小的数继续比较
4. 重复步骤2-3，直到两数相等
5. 最后的结果乘以约简的2的次方

Python实现

def gcd_subtraction(a, b):
    # 处理特殊情况
    if a == b:
        return a
    if a == 0 or b == 0:
        return max(a, b)
    
    # 约去2的因子
    k = 0
    while a % 2 == 0 and b % 2 == 0:
        a //= 2
        b //= 2
        k += 1
    
    # 更相减损术核心
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
            
    return a * (2 ** k)

# 示例
num1 = 98
num2 = 56
print(f"{num1}和{num2}的最大公约数是: {gcd_subtraction(num1, num2)}")

优点：不依赖取模运算
缺点：效率较低，特别是两数相差很大时

算法原理

穷举法是最直观的方法，通过遍历所有可能的公约数来找到最大的那个。

具体步骤：

1. 找到两个数中较小的那个数
2. 从该数开始递减遍历到1
3. 检查每个数是否同时整除两个输入数
4. 第一个满足条件的数即为最大公约数

Python实现

def gcd_brute_force(a, b):
    # 确保a是较小的数
    if a > b:
        a, b = b, a
    
    # 处理特殊情况
    if a == 0:
        return b
    
    # 从a开始向下遍历
    for i in range(a, 0, -1):
        if a % i == 0 and b % i == 0:
            return i

# 示例
num1 = 60
num2 = 48
print(f"{num1}和{num2}的最大公约数是: {gcd_brute_force(num1, num2)}")

优点：简单直观，容易理解
缺点：效率最低，时间复杂度为O(min(a,b))