Java：获取最大公约数

Question

我看到BigInteger已经有了这样的功能，即BigInteger#gcd。在Java中是否还有其他函数适用于其他类型（int、long或Integer）？似乎java.lang.Math.gcd（有各种重载）也能实现这个功能，但它并不存在。难道它在别处吗？

---

请不要把这个问题和“如何自己实现这个功能”混淆！

- Albert

---

为什么被接受的答案是告诉你如何自己实现它 - 虽然是包装一个现有的实现？=) - djjeck

我同意你的观点。GCD应该是一个类，其中包含一堆重载的静态方法，它们接受两个数字并给出它们的最大公约数。而且它应该是java.math包的一部分。 - anu

Answer 1

据我所知，对于基本数据类型来说，没有内置的方法。但是像这样简单的方法应该能解决问题：

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

如果你喜欢这种方式，也可以将其一行化：

public int gcd(int a, int b) { return b==0 ? a : gcd(b, a%b); }

需要注意的是，两者之间完全没有区别，因为它们编译成相同的字节码。

- Matt

---

这是欧几里得算法...非常古老而且已被证明正确。http://zh.wikipedia.org/wiki/欧几里得算法 - Rekin

@Albert，你可以尝试使用通用类型来测试一下是否可行。我不确定，这只是一个想法，但是算法可以供你进行实验。至于标准库或类，我从未见过。但是，你仍然需要在创建对象时指定它是int、long等类型。 - Matt

@Albert，虽然Matt提供了一种实现方式，但你自己也可以按照你所说的“更通用”的方式来使其工作，不是吗？ :) - Bart Kiers

@Albert，是的，我误解了你的问题，似乎你也误解了我的回答：我知道你没有问如何实现这个。但是，为了回答你的问题，这是否在Java中实现：它没有（至少不是你所要求的方式）。 - Bart Kiers

非常重要的免责声明 - 如果您有负数，它可能会返回一个负的最大公约数！= \ 除此之外，它是有效的。=） - HoldOffHunger

Answer 2

对于int和long这些基本类型，实际上没有。但是对于Integer，有可能有人编写了一个。

考虑到BigInteger是int、Integer、long和Long的（数学/功能）超集，如果你需要使用这些类型，将它们转换为BigInteger，执行GCD操作，然后将结果转换回去即可。

private static int gcdThing(int a, int b) {
    BigInteger b1 = BigInteger.valueOf(a);
    BigInteger b2 = BigInteger.valueOf(b);
    BigInteger gcd = b1.gcd(b2);
    return gcd.intValue();
}

- Tony Ennis

---

BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).intValue() 更好。 - Albert

一些基准测试：https://dev59.com/inzaa4cB1Zd3GeqPLyHU - jcsahnwaldt Reinstate Monica

如果这个函数经常被调用（例如数百万次），你就不应该将 int 或 long 转换为 BigInteger。仅使用原始值的函数可能会快上一个数量级。请查看其他答案。 - jcsahnwaldt Reinstate Monica

@Bhanu Pratap Singh 为了避免强制转换或截断，最好使用分别适用于int和long的方法。我已相应地编辑了答案。 - jcsahnwaldt Reinstate Monica

这不仅没有回答问题（Java中int或long的gcd在哪里），而且所提出的实现方法相当低效。 这不应该成为接受的答案。 据我所知，Java运行时库没有它，但第三方库中存在。 - Florian F

Answer 3

或者使用欧几里得算法来计算最大公约数(GCD)...

public int egcd(int a, int b) {
    if (a == 0)
        return b;

    while (b != 0) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }

    return a;
}

- Xorlev

---

澄清一下：这绝对不是我所要求的内容。 - Albert

在这种情况下，你没有说明你不需要备选方案，因为并不存在。只有后来你编辑了你的帖子，不再寻求实现。我相信其他人已经充分回答了“否定”的问题。 - Xorlev

如果a非常大而b很小，这种方法会很慢。使用“%”的解决方案将更快。 - Bruce Feist

即使a和b之间的差异很小，这也会变慢。我现在使用a = Long.MAX_VALUE和b = Long.MAX_VALUE - 3进行测试，并等待几分钟以获取结果。 - Zhenyria

Answer 4

除非我有番石榴，否则我会这样定义:

int gcd(int a, int b) {
  return a == 0 ? b : gcd(b % a, a);
}

- Alexey

Answer 5

使用Guava LongMath.gcd()和IntMath.gcd()计算最大公约数。

- Morad

---

有趣的是，Guava并没有使用欧几里得“模”方法，而是采用了二进制GCD算法，他们声称这种方法比欧几里得算法快40%。可以肯定的是，它非常高效且经过充分测试。 - Florian F

这些链接现在已经失效了，似乎新的文档存放在 https://guava.dev/releases/30.1.1-jre/api/docs/com/google/common/math/package-summary.html。 - Aly

Answer 6

Jakarta Commons Math已经提供了这个功能。

ArithmeticUtils.gcd(int p, int q)

- Tom Tucker

Answer 7

您可以使用这个 二进制 GCD 算法 的实现

public class BinaryGCD {

public static int gcd(int p, int q) {
    if (q == 0) return p;
    if (p == 0) return q;

    // p and q even
    if ((p & 1) == 0 && (q & 1) == 0) return gcd(p >> 1, q >> 1) << 1;

    // p is even, q is odd
    else if ((p & 1) == 0) return gcd(p >> 1, q);

    // p is odd, q is even
    else if ((q & 1) == 0) return gcd(p, q >> 1);

    // p and q odd, p >= q
    else if (p >= q) return gcd((p-q) >> 1, q);

    // p and q odd, p < q
    else return gcd(p, (q-p) >> 1);
}

public static void main(String[] args) {
    int p = Integer.parseInt(args[0]);
    int q = Integer.parseInt(args[1]);
    System.out.println("gcd(" + p + ", " + q + ") = " + gcd(p, q));
}

}

来自 http://introcs.cs.princeton.edu/java/23recursion/BinaryGCD.java.html 的代码

- linuxjava

---

这是斯坦算法的变体，利用了在大多数计算机上，移位是一种相对便宜的操作。这是一个标准算法。 - Bastian J

Answer 8

如果两个数字都是负数，一些实现在这里可能无法正常工作。gcd(-12, -18) 应该是 6，而不是 -6。

因此，应该返回一个绝对值，例如

public static int gcd(int a, int b) {
    if (b == 0) {
        return Math.abs(a);
    }
    return gcd(b, a % b);
}

- Robot Monk

---

一个特殊情况是当a和b都是Integer.MIN_VALUE时，结果会返回Integer.MIN_VALUE，这是一个负数。这可能是可以接受的。问题在于gcd(-2^31, -2^31)=2^31，但2^31不能表示为整数。 - Michael Anderson

我也建议使用 if(a==0 || b==0) return Math.abs(a+b); 以便对于零参数行为是真正对称的。 - Michael Anderson

Answer 9

我们可以使用递归函数来寻找最大公约数。

public class Test
{
 static int gcd(int a, int b)
    {
        // Everything divides 0 
        if (a == 0 || b == 0)
           return 0;

        // base case
        if (a == b)
            return a;

        // a is greater
        if (a > b)
            return gcd(a-b, b);
        return gcd(a, b-a);
    }

    // Driver method
    public static void main(String[] args) 
    {
        int a = 98, b = 56;
        System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b));
    }
}

- Esann

Answer 10

public int gcd(int num1, int num2) { 
    int max = Math.abs(num1);
    int min = Math.abs(num2);

    while (max > 0) {
        if (max < min) {
            int x = max;
            max = min;
            min = x;
        }
        max %= min;
    }

    return min;
}

这个方法使用欧几里得算法来获取两个整数的“最大公约数”。它接收两个整数并返回它们的gcd。就是这么简单！

- Seyyed Mohsen Mousavi