求最大公因数的方法

求最大公因数（GCD）的方法有多种，以下是常见的几种方法：

✅ 1. 分解质因数法

步骤：

1. 将两个数分解成质因数。
2. 找出两个数共有的质因数。
3. 将这些共有的质因数相乘，得到最大公因数。

示例：

• 48 = 2 × 2 × 2 × 3
• 18 = 2 × 3 × 3
• 公共质因数：2 × 3 = 6
• 所以 GCD(48, 18) = 6

✅ 2. Euclidean算法（辗转相除法）

步骤：

1. 用较大的数除以较小的数，得到余数。
2. 用较小的数除以余数，继续这个过程。
3. 当余数为0时，除数就是最大公因数。

示例：

• GCD(48, 18)
  • 48 ÷ 18 = 2 余 12
  • 18 ÷ 12 = 1 余 6
  • 12 ÷ 6 = 2 余 0
  • 所以 GCD(48, 18) = 6

✅ 3. 欧几里得算法（辗转相除法）的代码实现（Python）

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

print(gcd(48, 18))  # 输出 6

✅ 4. 试除法（适用于小数）

步骤：

1. 从2开始，试除到√n。
2. 找到能整除两个数的最大因数。

示例：

• GCD(48, 18)
  • 2 是因数，48 ÷ 2 = 24，18 ÷ 2 = 9
  • 3 是因数，48 ÷ 3 = 16，18 ÷ 3 = 6
  • 所以 GCD = 2 × 3 = 6

✅ 5. 线性筛法（适用于大数）

用于快速求多个数的GCD，适用于大数范围。

✅ 总结：