JavaScript Program to Find HCF or GCD

Introduction

High Common Factor (HCF) or Greatest Common Divisor (GCD) is the largest number that divides two or more numbers with no remainder. This basic concept in mathematics holds significant importance in programming, especially when dealing with calculations that need normalization or simplification of fractions. JavaScript, being a versatile language, allows various methods to compute the HCF or GCD effectively.

In this article, you will learn how to implement a JavaScript program to find the HCF or GCD of two numbers. Explore different techniques including the Euclidean algorithm, and understand their applications through practical examples.

Implementing GCD Using the Euclidean Algorithm

Step-by-step Example

The Euclidean algorithm is one of the most popular methods for finding the GCD of two integers. It is based on the principle that the GCD of two numbers also divides their difference.

1. Start by defining two numbers for which the GCD needs to be computed.

2. Implement a function using JavaScript that applies the Euclidean algorithm to these numbers.

   JAVASCRIPT

   Copy

   function findGCD(a, b) {
       while(b != 0){
           let t = b;
           b = a % b;
           a = t;
       }
       return a;
   }
   
   let num1 = 48;
   let num2 = 18;
   console.log("The GCD of", num1, "and", num2, "is", findGCD(num1, num2));

   Explain Code

   Powered by Vultr AgentBeta

   Initially, b becomes a's remainder when divided by b. Then, a takes the value of b, and b becomes the remainder until b becomes zero. The last non-zero value of a is the GCD.

Another Approach with Recursion

A recursive function can also implement the Euclidean algorithm elegantly. Recursion simplifies the swapping and updating of the numbers.

1. Define the recursive function to calculate GCD.

2. Ensure the base case and the recursive case are clearly defined to prevent infinite loops.

   JAVASCRIPT

   Copy

   function recursiveGCD(a, b) {
       if (b == 0) {
           return a;
       } else {
           return recursiveGCD(b, a % b);
       }
   }
   
   console.log("The GCD of 105 and 30 is", recursiveGCD(105, 30));

   Explain Code

   Powered by Vultr AgentBeta

   This function keeps calling itself with swapped parameters until b is zero, which then returns a as the GCD.

Conclusion

Finding the HCF or GCD of numbers is an essential operation, especially for operations involving ratios, proportions, and fractions in programming. JavaScript allows implementing this through various methods, including iterative and recursive versions of the Euclidean algorithm. Both techniques are efficient but choosing between them depends on personal or project-specific preferences regarding readability, performance, and complexity. By applying the explained methods, ensure your numerical calculations are optimized and accurate.