【欧几里得算法】欧几里得算法，又称辗转相除法，是求两个正整数的最大公约数（GCD）的一种经典方法。该算法最早由古希腊数学家欧几里得在其著作《几何原本》中提出，至今仍是计算机科学和数论中的重要工具。
该算法的核心思想是：如果a和b是两个正整数，且a > b，则gcd(a, b) = gcd(b, a % b)，直到其中一个数为0时，另一个数即为最大公约数。
欧几里得算法总结
| 项目 | 内容 |
| 名称 | 欧几里得算法 / 辗转相除法 |
| 提出者 | 欧几里得（古希腊数学家） |
| 提出时间 | 约公元前300年 |
| 用途 | 计算两个正整数的最大公约数（GCD） |
| 原理 | 若a > b，则gcd(a, b) = gcd(b, a % b)，重复此过程直到余数为0 |
| 关键步骤 | 1. 输入两个正整数a和b 2. 计算a ÷ b的余数r 3. 将b作为新的a，r作为新的b 4. 重复步骤2-3，直到r = 0，此时的b即为GCD |
| 优点 | 算法简单、效率高，适用于大数计算 |
| 应用场景 | 数论、密码学、分数化简、计算机程序设计等 |
示例说明
以求1071和462的最大公约数为例：
1. 1071 ÷ 462 = 2 余 147 → gcd(462, 147)
2. 462 ÷ 147 = 3 余 21 → gcd(147, 21)
3. 147 ÷ 21 = 7 余 0 → gcd(21, 0)
最终结果为21，即gcd(1071, 462) = 21。
总结
欧几里得算法是一种高效、简洁的数学工具，广泛应用于多个领域。其核心思想通过不断取余的方式逐步缩小问题规模，最终得到结果。该算法不仅在理论研究中有重要意义，在实际编程中也常被用来优化计算效率。
