什么叫做辗转相除法？ 辗转相除法，又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是： 用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。 示例： 123456 和 7890 的最大公因数是 6，这可由下列步骤（其中，“a mod b”是指取 a ÷ b 的余数）看出： 另一种求两数的最大公约数的方法是更相减损法。 扩展资料： 更相减损法与辗转相除法： 1、两者都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。 2、从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。 更相损减法在两数相差较大时，时间复杂度容易退化成O(N)，而辗转相除法可以稳定在O(logN)。但辗转相除法需要试商，这就使得在某些情况下，使用更相损减法比使用辗转相除法更加简单。而stein算法便由此出现。 本文来源：https://www.wddqw.com/doc/e0c84be2a65177232f60ddccda38376bae1fe03e.html