如何在一组数字上找到GCD，LCM

Question

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

Answer 1

它没有内置函数。你可以用欧几里得算法找到两个数字的GCD。

对于一组数字

GCD(a_1,a_2,a_3,...,a_n) = GCD( GCD(a_1, a_2), a_3, a_4,..., a_n )

递归地应用它。

LCM也一样：

LCM(a,b) = a * b / GCD(a,b)
LCM(a_1,a_2,a_3,...,a_n) = LCM( LCM(a_1, a_2), a_3, a_4,..., a_n )

Answer 2

GCD有一个欧几里德算法，

public int GCF(int a, int b) {
    if (b == 0) return a;
    else return (GCF (b, a % b));
}

顺便说一下，a和b应该大于或等于0，而LCM=|ab |/GCF（a，b）

Answer 3

我用欧几里德的算法找到两个数的最大公约数；它可以迭代以获得更大一组数字的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;
}

最小公倍数有点棘手，但最好的方法可能是通过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;
}