Euclid's Algorithm for Greatest Common Divisor

Euclid's algorithm finds the largest number that divides evenly into two numbers - the greatest common divisor (GCD). The Greek mathematician Euclid published the algorithm in his work, Elements in 300 BC.

The algorithm has three steps. Given 0 < n < m (zero is less than n and n is less than m):

If n is greater than m, swap m and n

Divide m by n leaving a remainder of r

If r == 0, the GCD is n

Else, set m to n, set n to r

Repeat steps 1 - 3

An interesting property of Euclid's Algorithm is that the greatest common divisor remains the same when you replace the larger number with the difference between the larger number and smaller number. For example, 7 is the greatest common divisor of 70 and 49. If you subtract 49 from 70 you get 21. 7 is still the greatest common divisor of 21 and 49. When the larger number is replaced with a smaller number, the process can be repeated, with successively smaller numbers until the larger and smaller numbers are equal - which will result in the greatest common divisor.

70, 49

 70 - 49 = 21

 21, 49

 49 - 21 = 28

 28, 21

 28 - 21 = 7

 21, 7

 21 - 7 = 14

 14, 7

 14 - 7 = 7

 7, 7

Euclid's Algorithm in JavaScript

/**
 * Euclid's algorithm for Greatest Common Divisor.
 * @param {int} m
 * @param {int} n
 * @returns {string|number}
 *
 * Given : 0 < n < m
 * Given : m / n = r
 *
 * 1. Divide m by n. If the remainder is 0, GCD is n.
 * 2. m <-- n, n <-- r
 * 3. Repeat until r == 0
 *
 * Big-O : O(log(min(x,y)))
 */
const euclidsAlgorithm = (m, n) => {
  /*
   * If `m` or `n` is not a positive integer, the test is invalid.
   */
  if (m <= 0 || n <= 0) return "`m` and `n` must be positive integers";

  /*
   * (1) If n > m, swap the numbers.
   */
  [m, n] = n > m ? [n, m] : [m, n];

  /*
   * (2) Divide m by n = r
   * m <-- n, n <-- r until r == 0
   */
  while (true) {
    // (3) If m / n is 0, n is the GCD
    if (m % n === 0) return n;
    // (4) Set m to n, n to r
    [m, n] = [n, m % n];
  }
};

var m = 50,
  n = 20;

log(`GCD of ${m} & ${n} is : ` + euclidsAlgorithm(50, 20));

You can grab the code from my Github repository for the 30 Days of Algorithms series. Feel free to leave feedback or ask questions in the comments below, or reach me via the Contact Page.