爪哇：得到最大的公约数

我已经看到BigInteger存在这样一个函数，即BigInteger#gcd 。 Java中是否还有其他函数（ int ， long或Integer ）？ 这似乎是有道理的java.lang.Math.gcd （与各种重载），但它不存在。 它在别的地方吗？

---

（请不要把这个问题与“我自己如何实现这个”混淆！）

Answer 1

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

鉴于BigInteger是int，Integer，long和Long（math/函数）的超集，如果您需要使用这些types，请将它们转换为BigInteger，执行GCD并将结果转换回来。

 private static int gcdThing(int a, int b) { BigInteger b1 = new BigInteger(""+a); // there's a better way to do this. I forget. BigInteger b2 = new BigInteger(""+b); BigInteger gcd = b1.gcd(b2); return gcd.intValue(); } 

更好的方法：

 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 2

据我所知，没有任何内置的基元方法。 但是这样简单的事情应该可以做到这一点：

 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 3

或欧几里德algorithm来计算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

雅加达下议院math正是这样。

ArithmeticUtils.gcd（int p，int q）

Answer 5

使用Guava LongMath.gcd()和IntMath.gcd()

Answer 6

如果两个数字都是负数，这里的一些实现不能正常工作。 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); } 

Answer 7

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

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

Answer 8

你可以使用二进制GCDalgorithm的这个实现

 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((pq) >> 1, q); // p and q odd, p < q else return gcd(p, (qp) >> 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 9

如果您使用的是Java 1.5或更高版本，那么这是一个迭代二进制GCDalgorithm，它使用Integer.numberOfTrailingZeros()来减less所需的检查次数和迭代次数。

 public class Utils { public static final int gcd( int a, int b ){ // Deal with the degenerate case where values are Integer.MIN_VALUE // since -Integer.MIN_VALUE = Integer.MAX_VALUE+1 if ( a == Integer.MIN_VALUE ) { if ( b == Integer.MIN_VALUE ) throw new IllegalArgumentException( "gcd() is greater than Integer.MAX_VALUE" ); return 1 << Integer.numberOfTrailingZeros( Math.abs(b) ); } if ( b == Integer.MIN_VALUE ) return 1 << Integer.numberOfTrailingZeros( Math.abs(a) ); a = Math.abs(a); b = Math.abs(b); if ( a == 0 ) return b; if ( b == 0 ) return a; int factorsOfTwoInA = Integer.numberOfTrailingZeros(a), factorsOfTwoInB = Integer.numberOfTrailingZeros(b), commonFactorsOfTwo = Math.min(factorsOfTwoInA,factorsOfTwoInB); a >>= factorsOfTwoInA; b >>= factorsOfTwoInB; while(a != b){ if ( a > b ) { a = (a - b); a >>= Integer.numberOfTrailingZeros( a ); } else { b = (b - a); b >>= Integer.numberOfTrailingZeros( b ); } } return a << commonFactorsOfTwo; } } 

unit testing：

 import java.math.BigInteger; import org.junit.Test; import static org.junit.Assert.*; public class UtilsTest { @Test public void gcdUpToOneThousand(){ for ( int x = -1000; x <= 1000; ++x ) for ( int y = -1000; y <= 1000; ++y ) { int gcd = Utils.gcd(x, y); int expected = BigInteger.valueOf(x).gcd(BigInteger.valueOf(y)).intValue(); assertEquals( expected, gcd ); } } @Test public void gcdMinValue(){ for ( int x = 0; x < Integer.SIZE-1; x++ ){ int gcd = Utils.gcd(Integer.MIN_VALUE,1<<x); int expected = BigInteger.valueOf(Integer.MIN_VALUE).gcd(BigInteger.valueOf(1<<x)).intValue(); assertEquals( expected, gcd ); } } } 

Answer 10

 /* import scanner and instantiate scanner class; declare your method with two parameters declare a third variable; set condition; swap the parameter values if condition is met; set second conditon based on result of first condition; divide and assign remainder to the third variable; swap the result; in the main method, allow for user input; Call the method; */ public class gcf { public static void main (String[]args){//start of main method Scanner input = new Scanner (System.in);//allow for user input System.out.println("Please enter the first integer: ");//prompt int a = input.nextInt();//initial user input System.out.println("Please enter a second interger: ");//prompt int b = input.nextInt();//second user input Divide(a,b);//call method } public static void Divide(int a, int b) {//start of your method int temp; // making a greater than b if (b > a) { temp = a; a = b; b = temp; } while (b !=0) { // gcd of b and a%b temp = a%b; // always make a greater than b a =b; b =temp; } System.out.println(a);//print to console } } 

Answer 11

我用了下面的方法。

 /** * @param args the command line arguments */ public static void main(String[] args) { // First number int n1 = 16; // Second number int n2 = 24; // Greatest Common Divisor int gdk = 0; for (int k = 2; k <= n1 && k <= n2; k++){ if(n1 % k == 0 && n2 % k == 0){ gdk = k; } } System.out.println(gdk); } 

Answer 12

 import java.util.*; public class BCD { public static void main(String[] args) { int k=1; Scanner in = new Scanner(System.in); int x = in.nextInt(); int y = in.nextInt(); for(int i=1;i<=Math.min(x,y);i++){ if(x%i==0 && y%i==0) k=i; } System.out.println("the biggest common divisor is " + k); } } 

Answer 13

 import java.util.*; public class Greatest_common_Divisor { public static void main (String[]args){ Scanner input = new Scanner(System.in); System.out.println("Enter two integers: "); int n1 = input.nextInt(); int n2 = input.nextInt(); int d = 0; int e=0; int temp = 0; //finds the lowest value if(n1 < n2) { temp = n1; n1 = n2; n2 = temp; } for(d = n2;(n2%d!=0 || n1%d!= 0);d--){ } System.out.println("The Greatest Common Divisor of " + n1 + " and " + n2 + " is " + d); } } 

Answer 14

％将给我们gcd在两个数字之间，这意味着： – big_number / small_number的％或mod是= gcd，我们把它写在像这样的big_number % small_number java上。

EX1：两个整数

  public static int gcd(int x1,int x2) { if(x1>x2) { if(x2!=0) { if(x1%x2==0) return x2; return x1%x2; } return x1; } else if(x1!=0) { if(x2%x1==0) return x1; return x2%x1; } return x2; } 

EX2：三个整数

 public static int gcd(int x1,int x2,int x3) { int m,t; if(x1>x2) t=x1; t=x2; if(t>x3) m=t; m=x3; for(int i=m;i>=1;i--) { if(x1%i==0 && x2%i==0 && x3%i==0) { return i; } } return 1; } 

Answer 15

 int n1 = 12; // you can make the user insert n1,n2 using Scanner or JOptionPane int n2 = 26; int gcd = 1; int k = 1; while ((k <= n1) && (k <= n2)) { if ((n1 % k == 0) && (n2 % k == 0)) { gcd = k; } k++; } System.out.print("The Greatest Common divisor of The Two numbers IS : " + gcd);