JS how to find the greatest common divisor [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions must demonstrate a minimal understanding of the problem being solved. Tell us what you've tried to do, why it didn't work, and how it should work. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

I would like to find the greatest common divisor using JavaScript.

Anyone done that before and willing to share?

Answer 1

Here is a recursive solution, using the Euclidean algorithm.

 var gcd = function(a, b) {
  if (!b) {
    return a;
  }

  return gcd(b, a % b);
}

Our base case is when b is equal to 0. In this case, we return a.

When we're recursing, we swap the input arguments but we pass the remainder of a / b as the second argument.

Answer 2

Taken from Wikipedia.

Recursive:

function gcd_rec(a, b) {
    if (b) {
        return gcd_rec(b, a % b);
    } else {
        return Math.abs(a);
    }
}

Iterative:

function gcd(a,b) {
    a = Math.abs(a);
    b = Math.abs(b);
    if (b > a) {var temp = a; a = b; b = temp;}
    while (true) {
        if (b == 0) return a;
        a %= b;
        if (a == 0) return b;
        b %= a;
    }
}

• EDITed per user's comment

Answer 3

function egcd(a, b) {
    if (a == 0)
        return b;

    while (b != 0) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }

    return a;
}