我看到BigInteger
已经有了这样的功能,即BigInteger#gcd
。在Java中是否还有其他函数适用于其他类型(int
、long
或Integer
)?似乎java.lang.Math.gcd
(有各种重载)也能实现这个功能,但它并不存在。难道它在别处吗?
请不要把这个问题和“如何自己实现这个功能”混淆!
我看到BigInteger
已经有了这样的功能,即BigInteger#gcd
。在Java中是否还有其他函数适用于其他类型(int
、long
或Integer
)?似乎java.lang.Math.gcd
(有各种重载)也能实现这个功能,但它并不存在。难道它在别处吗?
请不要把这个问题和“如何自己实现这个功能”混淆!
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); }
需要注意的是,两者之间完全没有区别,因为它们编译成相同的字节码。
对于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();
}
BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).intValue()
更好。 - Albert或者使用欧几里得算法来计算最大公约数(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;
}
除非我有番石榴,否则我会这样定义:
int gcd(int a, int b) {
return a == 0 ? b : gcd(b % a, a);
}
使用Guava LongMath.gcd()
和IntMath.gcd()
计算最大公约数。
您可以使用这个 二进制 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 的代码
如果两个数字都是负数,一些实现在这里可能无法正常工作。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);
}
a
和b
都是Integer.MIN_VALUE
时,结果会返回Integer.MIN_VALUE
,这是一个负数。这可能是可以接受的。问题在于gcd(-2^31, -2^31)=2^31,但2^31不能表示为整数。 - Michael Andersonif(a==0 || b==0) return Math.abs(a+b);
以便对于零参数行为是真正对称的。 - Michael Andersonpublic 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));
}
}
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。就是这么简单!