Menu
I would like to find the greatest common divisor using JavaScript.
Anyone done that before and willing to share?
969
The Euclidean Algorithm for finding GCD(A,B) is as follows: If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop. If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop. Write A in quotient remainder form (A = B⋅Q + R)
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.
107
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
