辗转相除法到底是怎么算更大公约数的？

你是不是也遇到过这种问题——想算两个数的更大公约数，但试了半天各种 *** 都特别麻烦？就像新手如何快速涨粉一样，总想找个简单直接的办法。今天咱们就来聊聊这个流传了2000多年的数学神器：辗转相除法。

先来点灵魂拷问

假设现在要算119和34的更大公约数，你会怎么办？挨个试它们的约数？119的约数有1、7、17、119，34的约数有1、2、17、34...这样找共同约数确实可以，但数字大了怎么办？比如51425和13310？这时候就得请出我们的主角了。

这个算法到底是谁发明的

说出来你可能不信，这 *** 最早出现在《几何原本》里，但欧几里得可能只是整理者。更早的记载在中国《九章算术》就有类似 *** ，不过现在国际上还是管它叫欧几里得算法。想想看，两千多年前的人都在用的 *** ，能不好使吗？

核心原理其实特别简单

关键就一句话：两个数的更大公约数，等于其中较小的数和两数相除余数的更大公约数。比如算119和34：

1. 119 ÷ 34 = 3余17

2. 现在算34和17的更大公约数

3. 34 ÷ 17 = 2余0

4. 余数为0时，除数17就是 ***

等等，为什么可以这样？咱们用个生活例子来说：假设你有119颗糖和34个盒子，要平均分装且盒子全用完。先用34个盒子每盒装3颗，用了102颗剩下17颗。这时候发现17刚好能整除34（2盒），所以最终每盒装17颗就是更大分配方案。

常见问题自问自答

Q：为什么余数为0就结束了？

A：因为余数为0意味着能整除了呀！就像刚才糖盒子的例子，最后剩下的17颗刚好能把34个盒子分成每盒2颗，一点不剩当然就是更优化解。

Q：会不会算着算着死循环？

A：放心，余数肯定越来越小。你看119→34→17→0，数字是严格递减的，最后必定收敛到0。数学上叫"序原理"算法肯定能停。

Q：负数能用这 *** 吗？

A：可以！但建议先用绝对值，毕竟公约数都是正数。比如算|-45|和|30|，结果是15，符号根本不影响。

对比下其他 ***

看到没？这就是为什么程序员面试老考这个——既考数学思维又考代码实现。Python里 *** th. *** ()底层就是用辗转相除法实现的。

实际应用比想象的多

加密算法RSA知道吧？那个密钥生成就得靠这个。还有音乐节拍换算、屏幕分辨率设置、甚至LEGO积木的孔距设计...只要涉及比例简化的地方，背后可能都有它的身影。

有次我帮邻居大爷调电视分辨率，1 *** 0x1080和1280x720的更大公约数就是240，直接套公式秒出结果，大爷还以为我是电脑专家呢。其实啊，这就是数学的魅力——学一次能用在各种想不到的地方。

最后说个冷知识：这个算法的时间复杂度是O(log min(a,b))，比很多现代算法都高效。所以下次遇到大数求公约数，别犹豫，直接上辗转相除法准没错。