我想使用 JavaScript 找到最大公约数。
有谁以前做过并愿意分享吗？
JS如何找到最大公约数
IT技术
javascript
math
greatest-common-divisor
2021-03-04 19:10:36
3个回答
这是一个递归解决方案，使用欧几里得算法。
var gcd = function(a, b) {
if (!b) {
return a;
}
return gcd(b, a % b);
}
我们的基本情况是何时b等于0。在这种情况下，我们返回a。
当我们递归时，我们交换输入参数，但我们将 的其余部分a / b作为第二个参数传递。
摘自维基百科。
递归：
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;
}
}
- 根据用户的评论编辑
function egcd(a, b) {
if (a == 0)
return b;
while (b != 0) {
if (a > b)
a = a - b;
else
b = b - a;
}
return a;
}