欧几里得算法求最大公约数（GCD）

判断两个数是否为非互质数的计算原理基于 最大公约数 (GCD)。这个方法的核心是使用 欧几里得算法，它能高效地计算出两个数的最大公约数。通过最大公约数判断，如果 GCD 大于 1，则两个数是非互质数；如果 GCD 为 1，则它们是互质数。

原理

欧几里得算法的基本思想是通过递归地将两个数的较大数减小，直到找到两个数的最大公约数。欧几里得算法的关键定理是：

两个数的最大公约数等于较小数和两者之差的最大公约数，即：
gcd(a, b) = gcd(b, a % b)
这个递归过程会继续，直到其中一个数为 0，此时另一个数就是最大公约数。

步骤

• 初始条件：给定两个数 a 和 b。
• 取余运算：计算 a % b，即用 a 除以 b 的余数。
• 递归替换：用 b 和 a % b 继续递归计算。重复这个过程，直到其中一个数为 0。
• 终止条件：当余数为 0 时，较大的数就是它们的最大公约数 GCD(a, b)。
• 判断互质性：如果 GCD(a, b) == 1，则它们是互质数；如果 GCD(a, b) > 1，则它们是非互质数。

代码

private int check(int a, int b) {
    int max = Math.max(a, b);
    int min = Math.min(a, b);

    if(min == 0) return max;

    int t = max % min;
    return check(min, t);
}

最小公倍数LCM

LCM = a * b / GCD(a, b)