javascript JS如何求最大公约数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17445231/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
JS how to find the greatest common divisor
提问by bboy
I would like to find the greatest common divisor using JavaScript.
我想使用 JavaScript 找到最大公约数。
Anyone done that before and willing to share?
有谁以前做过并愿意分享吗？
回答by alex
Here is a recursive solution.
这是一个递归解决方案。
var gcd = function(a, b) {
if (!b) {
return a;
}
return gcd(b, a % b);
}
Our base case is when bis equal to 0. In this case, we return a.
我们的基本情况是何时b等于0。在这种情况下，我们返回a。
When we're recursing, we swap the input arguments but we pass the remainder of a / bas the second argument.
当我们递归时，我们交换输入参数，但我们将 的其余部分a / b作为第二个参数传递。
回答by Yannis
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
- 根据用户的评论编辑
回答by Amani
function egcd(a, b) {
if (a == 0)
return b;
while (b != 0) {
if (a > b)
a = a - b;
else
b = b - a;
}
return a;
}
