Algotree > Algorithms > Numeric > Euclidean algorithm

Euclidean algorithm

Euclidean algorithm for finding the greatest common divisor (GCD) of two numbers.

The GCD of two numbers is the largest number that divides both the numbers without leaving a remainder (i.e the remainder is 0).
This idea behind this algorithm is the fact that the GCD of two numbers remains the same if the larger number is replaced by its difference with the smaller number. This way of finding the GCD of two numbers was proposed by a Greek mathematician Euclid.

Example
GCD (90, 54) = GCD (90-54, 54) = GCD (54, 36) = GCD (36, 18) = GCD (18, 18) = GCD (18, 0) = 18
GCD (84, 60) = GCD (60, 24) = GCD (36, 24) = GCD (24, 12) = GCD (12, 12) = GCD (12, 0) = 12

Euclid_GCD

Time complexity of Euclid’s algorithm : O (log (a + b)), where a and b are the numbers whose GCD needs to be calculated.

Eucild’s GCD Implementation

def EuclidGCD_Recursive (a,b):

    if ( b==0 ):
        return a
    else:
        return (EuclidGCD_Recursive(b,a%b))

def EuclidGCD (a,b):

    if (a < b): 
        # Swap a with b
        a, b = b, a
    while (b > 0): 
        a = a-b 
        if (a < b): 
            # Swap a with b
            a, b = b, a

    return a

def main():

    a = 90
    b = 54
    print("Using Recursion, GCD of (" + str(a) + "," + str(b) + ") = " + str(EuclidGCD_Recursive(a,b)))
    print("Using Iteration, GCD of (" + str(a) + "," + str(b) + ") = " + str(EuclidGCD(a,b))+"\n")
  
    a = 60
    b = 84
    print("Using Recursion, GCD of (" + str(a) + "," + str(b) + ") = " + str(EuclidGCD_Recursive(a,b)))
    print("Using Iteration, GCD of (" + str(a) + "," + str(b) + ") = " + str(EuclidGCD(a,b))+"\n")
  
    a = 53
    b = 97
    print("Using Recursion, GCD of (" + str(a) + "," + str(b) + ") = " + str(EuclidGCD_Recursive(a,b)))
    print("Using Iteration, GCD of (" + str(a) + "," + str(b) + ") = " + str(EuclidGCD(a,b)))

if __name__ == "__main__":
    main()

Output

Using Recursion, GCD of (90,54) = 18
Using Iteration, GCD of (90,54) = 18

Using Recursion, GCD of (60,84) = 12
Using Iteration, GCD of (60,84) = 12

Using Recursion, GCD of (53,97) = 1
Using Iteration, GCD of (53,97) = 1

#include<iostream>
#include<algorithm>

using namespace std;

int EuclidGCD_Recursive (int a, int b) { 

    if(b == 0)
       return a;
    else
       return EuclidGCD_Recursive(b, a%b);
}

int EuclidGCD (int a, int b) { 
    
    if (a < b) {
       swap(a, b); 
    }   
    while (b > 0) { 
      // GCD of two numbers remains the same if the larger number 
      // is replaced by its difference with the smaller number.
      a = a - b;
      if (a < b) {
         swap(a, b); 
      }   
    }   
    return a;
}

int main()
{
   int a = 90, b = 54; 
   cout << "Using Recursion, GCD of (" << a << "," << b << ") = " << EuclidGCD_Recursive (a,b) << endl;
   cout << "Using Iteration, GCD of (" << a << "," << b << ") = " << EuclidGCD (a,b) << endl << endl;
   a = 60, b = 84; 
   cout << "Using Recursion, GCD of (" << a << "," << b << ") = " << EuclidGCD_Recursive (a,b) << endl;
   cout << "Using Iteration, GCD of (" << a << "," << b << ") = " << EuclidGCD (a,b) << endl << endl;
   a = 53, b = 97; 
   cout << "Using Recursion, GCD of (" << a << "," << b << ") = " << EuclidGCD_Recursive (a,b) << endl;
   cout << "Using Iteration, GCD of (" << a << "," << b << ") = " << EuclidGCD (a,b) << endl;
   return 0;
}

Output

Using Recursion, GCD of (90,54) = 18
Using Iteration, GCD of (90,54) = 18

Using Recursion, GCD of (60,84) = 12
Using Iteration, GCD of (60,84) = 12

Using Recursion, GCD of (53,97) = 1
Using Iteration, GCD of (53,97) = 1

class GCD {

    public static int EuclidGCD_Recursive (int a, int b) {
        if (b==0) 
          return a;
        else 
          return(EuclidGCD_Recursive(b,a%b));
    }
  
    public static int EuclidGCD (int a, int b) {
  
        if (a < b) {
            int temp = a;
            a = b;
            b = temp;
        }

        while (b > 0) {
            // GCD of two numbers remains the same if the larger number 
            // is replaced by its difference with the smaller number.
            a = a-b;
            if (a < b) {
                int temp = a;
                a = b;
                b = temp;
            }
        }
        return a;
    }

    public static void main (String[] args) {

      int a = 90;int b = 54;

      System.out.println("Using Recursion, GCD of (" + a + "," + b + ") = " + EuclidGCD_Recursive(a,b));
      System.out.println("Using Iteration, GCD of (" + a + "," + b + ") = " + EuclidGCD(a,b));
      System.out.println();
      
      a = 60; b = 84;

      System.out.println("Using Recursion, GCD of (" + a + "," + b + ") = " + EuclidGCD_Recursive(a,b));
      System.out.println("Using Iteration, GCD of (" + a + "," + b + ") = " + EuclidGCD(a,b));
      System.out.println();
  
      a = 53; b = 97;
  
      System.out.println("Using Recursion, GCD of (" + a + "," + b + ") = " + EuclidGCD_Recursive(a,b));
      System.out.println("Using Iteration, GCD of (" + a + "," + b + ") = " + EuclidGCD(a,b));   
    }
}

Output

Using Recursion, GCD of (90,54) = 18
Using Iteration, GCD of (90,54) = 18

Using Recursion, GCD of (60,84) = 12
Using Iteration, GCD of (60,84) = 12

Using Recursion, GCD of (53,97) = 1
Using Iteration, GCD of (53,97) = 1