java - 如何在一组数字上找到 GCD、LCM

Question

在一组数字上计算最大公约数和最小公倍数的最简单方法是什么？可以使用哪些数学函数来查找此信息？

Answer 1

我用过Euclid's algorithm求两个数的最大公约数；可以通过迭代得到更大数字集的 GCD。

private static long gcd(long a, long b)
{
    while (b > 0)
    {
        long temp = b;
        b = a % b; // % is remainder
        a = temp;
    }
    return a;
}

private static long gcd(long[] input)
{
    long result = input[0];
    for(int i = 1; i < input.length; i++) result = gcd(result, input[i]);
    return result;
}

最小公倍数有点棘手，但最好的方法可能是reduction by the GCD ，可以类似地迭代:

private static long lcm(long a, long b)
{
    return a * (b / gcd(a, b));
}

private static long lcm(long[] input)
{
    long result = input[0];
    for(int i = 1; i < input.length; i++) result = lcm(result, input[i]);
    return result;
}