Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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

This comment has been minimized.

Copy link
Owner Author

@iconifyit iconifyit commented Feb 15, 2020

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];
    }
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.