GCD (Greatest Common Divisor) : Algorithm and Implementation in Java

GCD of two Numbers is Biggest Number by which both Numbers are divide.
EX. GCD( 6 , 12 ) = 6
       6 = 2 * 3
       12 = 2 * 2 * 3
       So Comon pattern is 2 * 3 = 6

One Characteristic is GDC will always smaller or equal to smallest number between 2 numbers.

Some Important GCD

• GCD( X , 0 ) = X
• GCD( 0 , X ) = X
• GCD( X , 1 ) = 1

Simple Way comes in our mind is DIVIDE BOTH NUMBERS by

BRUTE FORCE Technique

Loop from i = 1 to min( A , B )       if A % i == 0 and B % i == 0            gcd = i print gcd

public int findGCD( int num1, int num2 ){

    int gcd = 1;

    for( int i = 1; i <= num1 && i <= num2; i++ ){
       if( num1 % i == 0 && num2 % i == 0 ){
          gcd = i;
       }
    }

       return gcd;
}

Complexity of this Algorithm is O(n) where n is min(num1,num2).
we can find minimum from 2 numbers by using Math.min().

This algorithm is good but We can reduce complexity of this algorithm by using other idea. And idea is simple we will do subtraction.

Euclid Algorithm

Euclidean Algorithm is based on the principle that the GCD of two numbers remains the same if the larger of the two numbers is replaced by its difference with the smaller number. This process keeps reducing the larger number until the number becomes equal to the smaller number. When this happens, we get the GCD.

public int gcd( int num1, int num2 ){

    if( num2 == 0 ){
       return num1;
    }

    return gcd( num2 , num1 % num2 );

}

Complexity of this Algorithm is O(log min(num1 , num2)).

Posted by : Denes Vaghani May 31, 2020 Tags : Algorithm

Subscribe by Email

Follow Updates Articles from This Blog via Email