Program to Find GCD in Javascript

In this example, you will learn to write a program to find gcd in javascript.

But before going into the example, you must have knowledge of the following JavaScript topics:

The Greatest Common Divisor (GCD) or Highest Common Factor (HCF) of two or more integers is the largest positive integer that divides each of the integers. For Example,

GCD of 8 and 12 is 4.

// program to find gcd of two numbers using for loop
// take input
const a = prompt('Enter first number: ');
const b = prompt('Enter Second number: ');
let gcd;

// for loop 
for (let i = 1; i <= a && i <= b; i++) {
    if (a % i == 0 && b % i == 0) {
        gcd = i;
    }
}
// display the output
console.log(`GCD of ${a} and ${b} is ${gcd}`);

Output

GCD of 8 and 12 is 4

In the above program, we are taking inputs from the user for two positive integers using prompt().

1. The for loop is used to iterate from 1 to numbers a and b.

2. The if statement is used to find the GCD of both numbers.

3. Using the if condition, we are finding the highest value of i that can exactly divide both the integers a and b.

// Program to Find GCD Using Euclidean Algorithm
function gcd(a, b) {
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
// Test the function with some values
console.log(gcd(12, 8));
console.log(gcd(35, 10));
console.log(gcd(31, 2));

Output

4
5
1

In the above program, we have used a recursive function with the name gcd() that uses the Euclidean algorithm. The gcd() function takes in two integer arguments a and b.

Here is how the above program works:

1. If a = 0 then gcd(a, b) will return as GCD. 

2. If a is not 0, the function calls itself again with the arguments b%a and a. This is the recursive step of the algorithm, where the remainder of b divided by a is calculated and passed as the second argument.

3. The function continues to call itself until the remainder is 0, at which point it will return the gcd of the two numbers.

Suppose we want to find the gcd of 12 and 8. We would call the function like this:

First call gcd(12, 8);

Second call gcd(8, 12);

Third call gcd(4, 8);

Fourth call gcd(0, 4);

Return 4 as GCD.

// Arrow function to find the GCD of two numbers
const findGCD = (a, b) => {
  // Ensure that a is greater than b
  if (b > a) {
    let temp = a;
    a = b;
    b = temp;
  }
  
  // Iterate from a to 1, and find the first common divisor
  for (let i = a; i >= 1; i--) {
    if (a % i === 0 && b % i === 0) {
      return i;
    }
  }
}

// Test the function with some values
console.log(findGCD(15, 20));  
console.log(findGCD(21, 14));  
console.log(findGCD(81, 36)); 

Output

5
7
9

In the above program, we have defined an arrow function with the name findGCD() that takes two integers a and b as arguments.

1. The if statement inside the function is used to ensure that a is greater than b by swapping their values if necessary.

2. The for loop is used to iterate from a to 1 to find the GCD of both integers.

3. If we find the largest value of i that can perfectly divide both the integers a and b, we return that value as the GCD of two numbers.

// Program to find gcd of an array in javascript	
// Function using Euclidean Algorithm
function gcd(a, b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
// Function to find gcd of array
function gcdArray(arr) {
  // Find gcd of first two numbers
  let result = gcd(arr[0], arr[1]);
  // Find gcd of rest of the array
  for (let i = 2; i < arr.length; i++) {
    result = gcd(result, arr[i]);
  }

  return result;
}

// Test the function with some values
let arr1 = [12, 24, 36];
let arr2 = [16, 32, 48, 64];
let arr3 = [3, 5, 7, 9];

console.log(gcdArray(arr1));
console.log(gcdArray(arr2));
console.log(gcdArray(arr3));

Output

12
16
1

In the above program, we have used a function with the name gcdArray() that takes in an array of integers as the argument and returns the GCD of all the numbers in the array.

Here is how the gcdArray() function works:

1. The function takes an array arr of numbers as an argument.

2. The function calls the gcd() function to find the GCD of the first two numbers of the array.

3. The function declares a variable with the name result and initializes it with the result of the gcd() function call.

4. The function starts a for loop that will iterate over the rest of the numbers in the array, starting from the second index.

5. In each iteration of the for loop, the function calls the gcd() function, passing in the current result value and the current element of the array.

6. The return value of the gcd() function call is assigned to the result variable, replacing the previous value.

7. When the for loop ends, the result variable will contain the GCD of the entire array.

8. The function returns the value of the result variable.