Online Ethical Hacking Course

Apply Now

Examples

JavaScript Program to Find HCF or GCD

The Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two or more integers is the largest integer that can divide each of the numbers without leaving a remainder. For example:

  • The HCF of 12 and 18 is 6 because 6 is the largest number that divides both 12 and 18 evenly.

In this program tutorial, we will explore various ways to calculate the HCF or GCD in JavaScript using loops, recursion, and the Euclidean algorithm.

JavaScript Programs to Find HCF or GCD Using while Loop

This program uses a while loop to find the HCF or GCD of two numbers.

Code

function findHCFUsingWhileLoop(a, b) {
    while (b !== 0) {
        const temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Test the function
const num1 = 12;
const num2 = 18;
console.log(`The HCF of ${num1} and ${num2} is:`, findHCFUsingWhileLoop(num1, num2));

Output

The HCF of 12 and 18 is: 6

Explanation

  • The program iteratively calculates the remainder of a / b and updates the values of a and b until b becomes 0.

  • The value of a at this point is the HCF.

JavaScript Programs to Find HCF or GCD Using Recursion

This program uses a recursive function to calculate the HCF or GCD.

Code

function findHCFUsingRecursion(a, b) {
    if (b === 0) {
        return a;
    }
    return findHCFUsingRecursion(b, a % b);
}

// Test the function
console.log(`The HCF of ${num1} and ${num2} is:`, findHCFUsingRecursion(num1, num2));

Output

The HCF of 12 and 18 is: 6

Explanation

  • The function keeps calling itself with updated values (b and a % b) until b becomes 0.

  • The base case (b === 0) returns the HCF.

JavaScript Programs to Find HCF or GCD Using Euclidean Algorithm

The Euclidean algorithm is a popular and efficient method to calculate the HCF or GCD of two numbers.

Code

function findHCFUsingEuclidean(a, b) {
    while (b) {
        [a, b] = [b, a % b];
    }
    return a;
}

// Test the function
console.log(`The HCF of ${num1} and ${num2} is:`, findHCFUsingEuclidean(num1, num2));

Output

The HCF of 12 and 18 is: 6

Explanation

  • The algorithm swaps the values of a and b using array destructuring until b becomes 0.

  • The value of a at the end is the HCF.

Find HCF or GCD in JavaScript Using for Loop

This program uses a for loop to find the HCF or GCD of two numbers.

Code

function findHCFUsingForLoop(a, b) {
    let hcf = 1;
    for (let i = 1; i <= Math.min(a, b); i++) {
        if (a % i === 0 && b % i === 0) {
            hcf = i;
        }
    }
    return hcf;
}

// Test the function
console.log(`The HCF of ${num1} and ${num2} is:`, findHCFUsingForLoop(num1, num2));

Output

The HCF of 12 and 18 is: 6

Explanation

  • The loop iterates from 1 to the smaller of the two numbers (a and b).

  • It checks if both numbers are divisible by the current value of i.

  • The largest value of i that satisfies this condition is the HCF.

Finding HCF or GCD of an Array of Numbers in JavaScript

This program finds the HCF or GCD for an array of numbers.

Code

function findHCFOfArray(numbers) {
    const hcf = (a, b) => {
        while (b) {
            [a, b] = [b, a % b];
        }
        return a;
    };

    return numbers.reduce((acc, num) => hcf(acc, num));
}

// Test the function
const numbers = [12, 18, 24];
console.log(`The HCF of [${numbers.join(", ")}] is:`, findHCFOfArray(numbers));

Output

The HCF of [12, 18, 24] is: 6

Explanation

  • The program uses the reduce method to iteratively apply the HCF calculation to the array elements.

  • The result is the HCF of all numbers in the array.

Concepts Used in Above Programs

Iteration

  • while and for loops are used to iteratively calculate the HCF by updating the values of a and b.

Recursion

  • A recursive function simplifies the calculation by breaking it into smaller subproblems.

Euclidean Algorithm

  • The Euclidean algorithm is an efficient and widely used method for finding the HCF or GCD.

Array Operations

  • The reduce method is used to find the HCF of multiple numbers in an array.