JS如何找到最大公约数

Question

我希望使用JavaScript来寻找最大公约数。

是否有人之前做过并愿意分享？

- bboy

Answer 1

这里是一个使用欧几里得算法的递归解决方案。

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

  return gcd(b, a % b);
}

我们的基本情况是当b等于0时。在这种情况下，我们返回a。

当我们进行递归时，我们交换输入参数，但将a/b的余数作为第二个参数传递。

- alex

---

递归不是最快的。 - Florian F

好的，谢谢您的要求。我明白了。原文意思是：“好的，谢谢您的提醒。我没有看到楼主要求尽可能快地解决问题。”我会尽力保持原意并简化翻译。 - alex

他没有问。我想警告人们不要在实际程序中使用这种方法。 - Florian F

这段代码可以用一行来写，方法是这样的：var gcd = function(a,b) { return (!b)?a:gcd(b,a%b); };。顺便说一句，这是一个不错的解决方案，点赞。 - user4174706

@FlorianF：现在 ES2015（又称ES6）规范要求尾调用优化，一旦引擎达到规范，递归就不再是递归了。 :-) - T.J. Crowder

Answer 2

来自维基百科。

递归：

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

迭代:

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;
    }
}

• 根据用户评论进行编辑

- Yannis

---

如果 (a < 0) a = -a; 您也可以使用 a = Math.abs(a);（下一行同样适用） - user2428118

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;
}

- Amani

---

请添加您代码的解释。 - Nirvana