JS how to find the greatest common divisor
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
function egcd(a, b) {
if (a == 0)
return b;
while (b != 0) {
if (a > b)
a = a - b;
else
b = b - a;
}
return a;
}
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.