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 of finding GCD using Euclidean’s algorithm
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.


C++14 : Euclidean algorithm implementation

#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

Copyright © 2019-2020, Algotree.org.
All rights reserved.