Euclidean Algorithm

Euclidean algorithm is used for calculating greatest common divisor of two given numbers.

Subtraction-based version:

Iteration version:

function gcd(a, b):
  while(a != b):
    if(a > b):
      a := a - b;
    else:
      b := b - a;
  return a;

Recursive version:

function gcd(a, b):
  if(a > b):
    return gcd(a - b, b);
  else if(a < b):
    return gcd(a, b - a);
  else:
    return a;

GCD of 27 and 15:

gcd(27, 15) = ?

          27           15
---------------------------
27 - 15 = 12           15
          12  15 - 12 = 3
  12 - 3 = 9            3
   9 - 3 = 6            3
   6 - 3 = 3            3
---------------------------
gcd(27, 15) = 3

 

Division-based version:

Iteration version:

function gcd(a, b):
  while(b != 0):
    t := b;
    b := a mod b;
    a := t;
  return a;

Recursive version:

function gcd(a, b):
  if(b = 0):
    return a;
  else:
    return gcd(b, a mod b);

GCD of 27 and 15:

gcd(27, 15) = ?

          27             15           t
----------------------------------------
          15  27 mod 15 = 6          15
           6   15 mod 6 = 3           6
           3    6 mod 3 = 0
----------------------------------------
gcd(27, 15) = 3

Python Implementation C++ Implementation Java Implementation C# Implementation