最大公约数

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

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.

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

Jakarta Commons Math has exactly that.

ArithmeticUtils.gcd(int p, int q)

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

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

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

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

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

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

Unless I have Guava, I define like this:

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

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

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

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!

Is it somewhere else?

Apache! - 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).

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.