欧几里得算法可视化

欧几里得算法原理

给定两个正整数 a 和 b (a ≥ b)，欧几里得算法通过以下步骤计算它们的最大公约数:

1. 将 a 除以 b，得到商 q 和余数 r: a = q × b + r
2. 如果 r = 0，则 b 是最大公约数
3. 如果 r ≠ 0，令 a = b，b = r，并返回步骤 1

通过连续的除法，余数会不断减小，直到其中一个余数为 0，此时前一个非零余数即为最大公约数。