Java: get greatest common divisor

JavaGreatest Common-Divisor

Java Problem Overview

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

(Don't confuse this question with "how do I implement this myself", please!)

Java Solutions

Solution 1 - Java

As far as I know, there isn't any built-in method for primitives. But something as simple as 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 one-line it if you're into that sort of thing:

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 the two as they compile to the same byte code.

Solution 2 - Java

For int and long, as primitives, not really. For Integer, it is possible 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 a BigInteger, do the 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();
}

Solution 3 - Java

Or the Euclidean algorithm for calculating the 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;
}

Solution 4 - Java

Unless I have Guava, I define like this:

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

Solution 5 - Java

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

Solution 6 - Java

Jakarta Commons Math has exactly that.

ArithmeticUtils.gcd(int p, int q)

Solution 7 - Java

You can use this implementation of 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((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));
}

}

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

Solution 8 - Java

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

So an absolute value should be returned, something like

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

Solution 9 - Java

we can use recursive function for find 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(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));
    }
}

Solution 10 - Java

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 Euclid’s algorithm to get the "Greatest Common Divisor" of two integers. It receives two integers and returns the gcd of them. just that easy!

Solution 11 - Java

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

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

Solution 12 - Java

> Is it somewhere else?

[Apache!](http://commons.apache.org/proper/commons-math/javadocs/api-3.6/org/apache/commons/math3/util/ArithmeticUtils.html "Rejoice - it's there!") - it has both gcd and lcm, so cool!

However, due to profoundness of their implementation, it's slower compared to simple hand-written version (if it matters).

Solution 13 - Java

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

Solution 14 - Java

I used this method that 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;
    }

Solution 15 - Java

Those GCD functions provided by Commons-Math and Guava have some differences.

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

Solution 16 - Java

The % going to give us the gcd Between two numbers, it means:- % or mod of big_number/small_number are =gcd, and we write it on java like this 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;
}
Categories
Recommended Java Solutions
Recommended Greatest Common-Divisor Solutions

Previous Solution:

Get a list of all the files in a directory (recursive)

FileGroovyDirectory Listing

Next Solution:

CSS: Top vs Margin-top

CssCss Position

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionAlbertView Question on Stackoverflow
Solution 1 - JavaMattView Answer on Stackoverflow
Solution 2 - JavaTony EnnisView Answer on Stackoverflow
Solution 3 - JavaXorlevView Answer on Stackoverflow
Solution 4 - JavaAlexeyView Answer on Stackoverflow
Solution 5 - JavaMoradView Answer on Stackoverflow
Solution 6 - JavaTom TuckerView Answer on Stackoverflow
Solution 7 - JavalinuxjavaView Answer on Stackoverflow
Solution 8 - JavaRobot MonkView Answer on Stackoverflow
Solution 9 - JavaEsann View Answer on Stackoverflow
Solution 10 - JavaSeyyed Mohsen MousaviView Answer on Stackoverflow
Solution 11 - JavaMT0View Answer on Stackoverflow
Solution 12 - JavaBoleslovas ŠvitrigailaView Answer on Stackoverflow
Solution 13 - JavaGitau HarrisonView Answer on Stackoverflow
Solution 14 - JavaJohn DoeView Answer on Stackoverflow
Solution 15 - JavaJin KwonView Answer on Stackoverflow
Solution 16 - JavaMr-Al7laweView Answer on Stackoverflow