辗转相除法 欧几里得算法
反复用余数替换求最大公约数的经典方法。
辗转相除法是求两个整数最大公约数的经典办法，因为最早记载于欧几里得的著作，也叫欧几里得算法。它的核心是一个事实：两个数的最大公约数，等于其中较小的数和「大数除以小数的余数」这两者的最大公约数。
具体做法很简单：用大数除以小数，得到余数；再用刚才的小数去除这个余数，得到新余数；这样反复替换，直到余数变成 0，此时最后一个不为零的除数就是最大公约数。举例求 48 和 36：48÷36 余 12，36÷12 余 0，于是最大公约数是 12。
它比逐个列约数或分解质因数都快得多，尤其对付大数字优势明显，是计算机里求公约数的标准算法。使用时注意别把余数和商弄混——每一步真正参与下一轮的是余数，不是商；一旦余数为 0 就立即停下。
关于辗转相除法的常见问答
辗转相除法比分解质因数好在哪？数字一大，分解质因数就很吃力，而辗转相除只需要连续做几次带余除法，步数少、速度快，计算机里普遍用它。
辗转相除法什么时候停？当某一步的余数变成 0 时停下，上一步用的那个除数（也就是最后一个非零余数）就是最大公约数。
辗转相除只能求最大公约数吗，能求最小公倍数吗？它直接求的是最大公约数。求出后用「两数乘积除以最大公约数」就能得到最小公倍数，一步到位。