{{ message }}

Instantly share code, notes, and snippets.

# iconifyit/GreatestCommonDivisor.js

Last active Feb 15, 2020
30 Days of Algorithms : Euclid's Algorithm to find Greatest Common Divisor
 /** * Euclid's algorithm for Greatest Common Divisor. * @param {int} m * @param {int} n * @returns {string|number} * * Given : 0 < n < m * * 1. Divide m by n. If the remainder is 0, GCD is n. * 2. m <-- n, n <-- r * 3. Repeat until r == 0 */ const gcd = (m, n) => { if (m < 0 || n < 0) return '`m` and `n` must be positive integers'; m = Math.max(m, n); n = Math.min(m, n); while(true) { let r = m % n; if (r === 0) return n; m = n; n = r; } };

### iconifyit commented Feb 15, 2020 • edited

 There is a much more terse way to code this in ES6 but I wrote the above to make it easier to understand. Here is the more terse version: ```/** * Euclid's algorithm for Greatest Common Divisor. * @param {int} m * @param {int} n * @returns {string|number} * * Given : 0 < n < m * * 1. Divide m by n. If the remainder is 0, GCD is n. * 2. m <-- n, n <-- r * 3. Repeat until r == 0 */ 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'; /* * If n > m, swap the numbers. */ [m, n] = n > m ? [n, m] : [m, n] ; /* * Divide m by n = r * m <-- n, n <-- r until r == 0 */ while(true) { if (m % n === 0) return n; [m, n] = [n, m % n]; } };```