Java:得到最大的公约数

Question

我已经看到这样的功能存在BigInteger,即BigInteger#gcd.Java中是否还有其他函数适用于其他类型(int,long或Integer)？这似乎是有意义的java.lang.Math.gcd(有各种各样的重载),但它不存在.它在别的地方吗？

---

(请不要将此问题与"我如何自己实施"这一问题混淆,请!)

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); }

应该注意的是,两者之间完全没有区别,因为它们编译为相同的字节代码.

Answer 2

对于int和long,作为原语,不是真的.对于整数,有可能有人写了一个.

鉴于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();
}

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;
}

Answer 4

Jakarta Commons Math就是这样.

ArithmeticUtils.gcd(int p,int q)

Answer 5

使用番石榴LongMath.gcd()和IntMath.gcd()

Answer 6

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

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

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

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);
}