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

Question

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

Answer 1

我用Euclid算法找到两个数的最大公约数; 可以迭代它以获得更大数字集的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 gcd(long[] input)
{
    long result = input[0];
    for(int i = 1; i < input.length; i++) result = lcm(result, input[i]);
    return result;
}

Answer 2

有一个Euclid的 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

它没有功能.您可以使用Euclid算法找到两个数字的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 4

如果你可以使用Java 8(实际上想要),你可以使用lambda表达式来解决这个问题:

private static int gcd(int x, int y) {
    return (y == 0) ? x : gcd(y, x % y);
}

public static int gcd(int... numbers) {
    return Arrays.stream(numbers).reduce(0, (x, y) -> gcd(x, y));
}

public static int lcm(int... numbers) {
    return Arrays.stream(numbers).reduce(1, (x, y) -> x * (y / gcd(x, y)));
}

我将自己定位于Jeffrey Hantin的答案,但是

• 从功能上计算了gcd
• 使用varargs-Syntax来获得更简单的API(我不确定重载是否能正常工作,但它确实在我的机器上运行)
• 将numbers-Array 的gcd 转换为功能语法,它更紧凑,IMO更易于阅读(至少如果您习惯于函数式编程)

由于额外的函数调用,这种方法可能稍微慢一些,但对于大多数用例而言,这可能根本不重要.