In this article, we are going to learn about finding the GCD or HCF of two numbers in JavaScript. GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is the largest positive integer that divides both numbers without leaving a remainder.
GCD ( a, b ) = [ |a.b| ] / [ lcm(a, b) ]
or,
HCF of factors = Product of the Numbers/ LCM of numbers
Example:
Input: a = 20, b = 28
Output: 4
Explanation: The factors of 20 are 1, 2, 4, 5, 10 and 20.
The factors of 28 are 1, 2, 4, 7, 14 and 28. Among these factors,
1, 2 and 4 are the common factors of both 20 and 28.
The greatest among the common factors is 4.
There are several methods that can be used to get the HCF of two numbers, which are listed below:
- Using for Loop
- Using the Recursive method
We will explore all the above methods along with their basic implementation with the help of examples.
JavaScript Program to Find GCD or HCF of Two Numbers using for Loop
In this approach we are using a loop to find GCD/HCF, iterating from 1 to the minimum of the two numbers. Update GCD when both numbers are divisible.
Syntax:
for ( variable of iterableObjectName) {
. . .
}
Example:
Javascript
function myFunction(a, b) { let smaller = Math.min(a, b); let hcf = 1; for (let i = 1; i <= smaller; i++) { if (a % i === 0 && b % i === 0) { hcf = i; } } return hcf; } const num1 = 20; const num2 = 12; console.log("GCD of the giving numbers(20,12) is:", myFunction(num1, num2)); |
GCD of the giving numbers(20,12) is: 4
JavaScript Program to Find GCD or HCF of Two Numbers using the Recursive method
In this approach, the recursive function myFunction calculates GCD using the Euclidean algorithm. If b=0, returns a; otherwise, recursively calls with b and remainder of a/b.
Syntax:
function myFunction(a, b) {
if ( b === 0 ) {
return a;
}
return myFunction(b, a % b);
}
Example: In this example, we are using the above-explained approach.
Javascript
function myFunction(a, b) { if (b === 0) { return a; } return myFunction(b, a % b); } let num1 = 12; let num2 = 18; let result = myFunction(num1, num2); console.log(`GCD of ${num1} and ${num2} is ${result}`); |
GCD of 12 and 18 is 6
