Euclid's GCD Algorithm

Before turning our head to Euclid's algorithm for calculating GCD, let's cover the more fundamental approach to calculate GCD.

GCD (Greatest Common Divisor)

GCD of two integers A and B is the largest integer that divides them both without a remainder. It is also known as GCF(Greatest Common Factor), HCF(Highest Common Factor) and GCM(Greatest Common Measure).

So GCD(A, B) will be between 1 and min(A, B), both inclusive. So it can be implemented as shown below:

 public int gcd(int a, int b) {

   for (int i = Math.min(a, b); i > 1; i--) {

     if (a % i == 0 && b % i == 0) {

       return i;

     }

   }

   return 1;

 }

Euclid's Algorithm

Above algorithm is not very efficient, as in worst case it can end up doing min(a,b) modulo operations. Euclid's or Euclidian algorithm is an efficient algorithm for calculating GCD of two numbers. And due to its efficiency and simplicity, it is one of the oldest numerical algorithms which is still in use. This algorithm iterates over the two numbers until the remainder is 0. 

To calculate GCD,

Express first in terms of the second number i.e. A = B*K + C

Now repeat the operation for K and C (until C is 0)

The last non-zero remainder is GCD. 

GCD(18,12) => 18 = 12*1 + 6

GCD(6,1)    =>  6 = 1*6 + 0

GCD = 6

Recurrence relation would be:

GCD(A,0) = A

GCD(A,B) = GCD(B, A mod B), for B>0

Implementation

Recursive implementation is quite trivial:

public int euclidGcd(int a, int b){

  if(b ==0 ) return a;

  return euclidGcd(b, a%b);

}

--
keep coding !!!