辗转相除法求最大公约数 🔢🔍

辗转相除法，也称欧几里得算法，是求两个正整数最大公约数的一种经典方法。这种方法简单而高效，只需要重复做除法运算，直到余数为零为止。最后的非零余数就是这两个数的最大公约数。🔍🔢

例如，我们要找48和18的最大公约数：

- 用较大数除以较小数，即48 ÷ 18，得到余数12。

- 然后用上一步的除数（18）除以余数（12），得到余数6。

- 再次用上一步的除数（12）除以新的余数（6），这次没有余数了。

- 因此，6就是48和18的最大公约数。🎉

这个方法不仅适用于手工计算，也是计算机编程中求解最大公约数问题的基础。它体现了数学的简洁美，也展示了算法设计中的智慧。💡💻

通过辗转相除法，我们可以轻松解决许多与数论相关的问题，是学习算法和数论不可或缺的一部分。📖📚

数学之美 算法基础 辗转相除法