Java 计算两个整数的最大公约数

辗转相除法

辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是 0 为止。

public int getVal(int a, int b) {
    int mid;
    while (b != 0) {
        mid = a % b;
        a = b;
        b = mid;
    }
    return a;
}

更相减损术

更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

原文是：

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

白话文译文：

（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用 2 来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。

更相减损术原理：两个正整数 a 和 b（a>b），它们的最大公约数等于 a-b 的差值 c 和较小数 b 的最大公约数。

public int getGCD(int m, int n) {
    while (m != n) {
        if (m > n) {
            m -= n;
        } else {
            n -= m;
        }
    }
    return m;
}