Introduction
The greatest common denominator (GCD) of two or more numbers is the largest positive integer that divides those numbers without a remainder.
In this article, we will discuss the how to find GCD in JavaScript using recursion and a NodeJS library.
Method-1: Use recursion to find gcd in JavaScript
You can use a recursive function to calculate the GCD of two numbers using the Euclidean algorithm. Here is an example of how to do this:
function gcd(a, b) {
if (b === 0) {
return a;
} else {
return gcd(b, a % b);
}
}
let theGCD = gcd(12, 18);
console.log(theGCD);
Output
6
In this example, the gcd function is a recursive function that uses the Euclidean algorithm to find the GCD of two numbers. The function takes two numbers as its arguments, and it uses a if statement to check if the second number (b) is equal to 0. If it is, the function returns the first number (a) as the result, because the GCD of a number and 0 is always the first number.
If the second number is not equal to 0, the function calls itself recursively, passing the second number as the first argument and the result of the modulo operation (a % b) as the second argument. This continues until the second number is equal to 0, at which point the recursive calls unwind and the GCD is returned.
In the example, the gcd function is called with the numbers 12 and 18 as its arguments. The function calculates the GCD of those numbers using the Euclidean algorithm and returns the integer 6 as the result. The result is then logged to the console.
In addition to using a recursive function like this one, you can also use a loop to calculate the GCD of two or more numbers. For example:
function gcd(numbers) {
let result = numbers[0];
for (let i = 1; i < numbers.length; i++) {
result = gcdTwoNumbers(result, numbers[i]);
}
return result;
}
function gcdTwoNumbers(a, b) {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
let theGCD = gcd([12, 18, 24]);
console.log(theGCD); // 6
Output
6
In this example, the gcd function uses a loop to iteratively calculate the GCD of two or more numbers. The function takes an array of numbers as its argument, and it uses a for loop to iterate over the array. For each iteration of the loop, the function calls the gcdTwoNumbers helper function, passing the current result and the current array element as the arguments. The gcdTwoNumbers function uses a while loop to calculate the GCD of the two numbers using the Euclidean algorithm.
In the example, the gcd function is called with an array containing the numbers 12, 18, and 24 as its argument. The function calculates the GCD of those numbers by iteratively calling the gcdTwoNumbers function for each number in the array. The GCD of the numbers is calculated using the Euclidean algorithm and returned as the result of the gcd function. The result is then logged to the console.
Method-2: Use mathjs library to find gcd in JavaScript
If you have NodeJS, you can use the gcd method of the mathjs library to find the GCD of two or more numbers.
To use the gcd method, you first need to install the mathjs library by running the following command:
npm install mathjs
Once the library is installed, you can import it into your JavaScript code and use the gcd method as follows:
let math = require("mathjs");
let gcd = math.gcd(12, 18, 24);
console.log(gcd);
Output
6
In this example, the math.gcd method is used to find the GCD of the numbers 12, 18, and 24. The method is called with these numbers as its arguments, and it returns the integer 6 as the result. This is the largest positive integer that divides all of the input numbers without a remainder, so it is the GCD of those numbers. The result is then logged to the console.
Summary
There are several ways to find the GCD of two or more numbers in JavaScript. You can use the gcd method of the mathjs library, you can use a recursive function, or you can use a loop. Each approach has its own advantages and disadvantages, so it is up to you to decide which approach is best for your specific needs.
