数据结构-最大公约数计算

辗转相除法是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。这个和更相减损术有着异曲同工之处

原理

对于两个数 $(a,b)$，如果有最大公约数 $g$，那么 $(kb+a,b)$ 同样有最大公约数 $g$

因为对于 $(kb+a,b)$ ，同样也有

image-20220727101522543

所以求公约数可以通过上述的公式迭代进行，迭代的时候是两数相互取余

java代码如下

public int gcd(int a, int b) {
        int remainder = a % b;
        while(remainder != 0) {
            a = b;
            b = remainder;
            remainder = a % b;
        }
        return b;
    }
JAVA