【欧几里得算法】欧几里得算法，又称辗转相除法，是求两个正整数最大公约数（GCD）的一种经典算法。该算法最早出现在古希腊数学家欧几里得的《几何原本》中，至今仍是计算机科学和数论中的重要工具。
该算法的核心思想是：用较大的数除以较小的数，然后用余数替换较大的数，重复这一过程，直到余数为零，此时的除数即为这两个数的最大公约数。
欧几里得算法总结
| 步骤 | 操作 | 说明 |
| 1 | 输入两个正整数a和b，假设a > b | 确保a大于b以便于计算 |
| 2 | 计算a ÷ b的余数r | r = a % b |
| 3 | 将a设为b，b设为r | 进入下一轮循环 |
| 4 | 重复步骤2和3，直到r = 0 | 当余数为0时停止 |
| 5 | 最后一个非零的除数即为GCD | 得到最终结果 |
示例演示
以求105和30的最大公约数为例：
1. 105 ÷ 30 = 3 余15 → r = 15
2. 30 ÷ 15 = 2 余0 → r = 0
3. 余数为0，算法结束，此时的除数15即为GCD。
应用场景
- 密码学中用于生成公钥和私钥
- 分数化简（将分子分母同时除以GCD）
- 数论研究中用于分析整数性质
- 编程中常用于快速计算最大公约数
优点与局限性
| 优点 | 局限性 |
| 算法简单，易于实现 | 仅适用于正整数 |
| 计算效率高，时间复杂度低 | 不能直接处理负数或0 |
| 被广泛应用于多个领域 | 需要确保输入为正整数 |
通过欧几里得算法，我们可以高效地找到两个整数的最大公约数，这在数学和编程中都具有重要意义。掌握这一算法有助于理解更复杂的数论问题，并提升编程能力。
