Tags

, , , , ,

We know that in Mathematics, the greatest common divisor or GCD of two or more integers (provided they are not zero), is the largest positive integer that can divide each of the integers.

There might be many other positive integers that can divide the two numbers, however, the GCD will always be the largest among them. After the GCD there will not be any integer left that can divide the two integers.

You have heard of Euclidean Algorithm, that uses division method. But there are a few more, and they might look interesting to you.
package fun.sanjibsinha.gcd;

public class FindGCD {

static int numOne = 0;
static int numTwo = 0;
static int remain = 0;

static int divisionBased(int num1, int num2){
int temp;
while (num2 != 0){
temp = num2;
num2 = num1 % num2;
num1 = temp;
}
return num1;
}

//this is Euclid's original version
static int subtractionBased(int num1, int num2){
int temp;
while (num1 != num2){
if(num1 > num2)
num1 = num1 - num2;
else
num2 = num2 - num1;
}
return num1;
}

static int recursiveBased(int num1, int num2){
if(num2 == 0){
return num1;
} else {
int temp;
temp = num1 % num2;
return recursiveBased(num2, temp);
}
}

public static void main(String[] args) throws ArithmeticException {

System.out.println(recursiveBased(1071, 462));
//output 21

}
}