Java: get the greatest common divisor

Question

I saw that such a function exists for BigInteger , i.e. BigInteger#gcd . Are there other functions in Java that also work for other types ( int , long or Integer )? It seems to make sense like java.lang.Math.gcd (with all kinds of overloads), but it is not there. Is it somewhere else?

---

(Do not confuse this question with the question "how can I implement this myself, please!"

Answer 1

For int and long, as primitives, not really. For Integer, maybe someone wrote one.

Given that BigInteger is a (mathematical / functional) superset of int, Integer, long and Long, if you need to use these types, convert them to BigInteger, execute GCD and convert the result back.

 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

As far as I know, there is no built-in method for primitives. But something simple like this should do the trick:

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

You can also do a single line if you go into such things:

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

It should be noted that there is absolutely no difference between them when compiling the same byte code.

Answer 3

Or the Euclidean algorithm for calculating 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 has just that.

ArithmeticUtils.gcd (int p, int q)

Answer 5

Use Guava LongMath.gcd() and IntMath.gcd()

Answer 6

If I have Guava, I define it like this:

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

Answer 7

You can use this implementation of the binary GCD algorithm

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

}

From http://introcs.cs.princeton.edu/java/23recursion/BinaryGCD.java.html

Answer 8

Some implementations here work incorrectly if both numbers are negative. gcd (-12, -18) is 6, not -6.

So, you need to return the absolute value, something like

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

Answer 9

If you are using Java 1.5 or later, it is an iterative binary GCD algorithm that uses Integer.numberOfTrailingZeros() to reduce the number of checks and required iterations.

 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 test:

 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

we can use a recursive function to search for GCD

 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(ab, b); return gcd(a, ba); } // 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)); } } 

Answer 11

 /* 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 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

I used the following method.

 /** * @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 14

 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 15

I used this method, which I created when I was 14 years old.

  public static int gcd (int a, int b) { int s = 1; int ia = Math.abs(a);//<-- turns to absolute value int ib = Math.abs(b); if (a == b) { s = a; }else { while (ib != ia) { if (ib > ia) { s = ib - ia; ib = s; }else { s = ia - ib; ia = s; } } } return s; } 

Answer 16

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

This method uses the Euclidean algorithm to obtain the “Greatest Common Divisor” of two integers. It gets two integers and returns them gcd. just so simple!

Answer 17

Is it somewhere else?

Apache! - he has both gcd and lcm, so cool!

However, due to the depth of their implementation, it is slower compared to a simple handwritten version (if that matters).

Answer 18

These GCD features provided by Commons-Math and Guava have some differences.

• Commons-Math throws ArithematicException.class only for Integer.MIN_VALUE or Long.MIN_VALUE .
  • Otherwise, it processes the value as an absolute value.
• Guava throws IllegalArgumentException.class for any negative values.

Answer 19

 import java.io.*; import java.util.*; public class CandidateCode { public static void main(String args[] ) throws Exception { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc. nextInt(); int g = 1; for (int i = 1 ; i <= m && i <= n ; i++) { if((m%i==0)&&(n%i==0)) g= i; } System.out.println(g); } } 

Answer 20

% giving us gcd Between two numbers, this means: -% or the big_number / small_number = gcd mode, and we write it in java, like big_number % small_number .

EX1: for two integers

  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: for three integers

 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 21

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