Find greatest common divisor (GCD) in JavaScript

The Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides given numbers without a remainder. In other words, we can say  GCD is the largest divisor of both the given numbers. For example, the GCD of 20 and 30 is 10.

In this article, we are going to discuss how to find Greatest Common Divisor (GCD) in JavaScript.

1. Find GCD using the Euclidean algorithm.
2. Find GCD using for loop.
3. Calculate Greatest Common Divisor(GCD) for a given integer array.

Find GCD using the Euclidean algorithm

The Euclidean algorithm or Euclid's algorithm is an efficient method for computing the greatest common divisor (GCD) of two numbers. It is an iterative method that starts with two numbers a and b, and continuously takes the difference. i.e we are subtracting the smaller number from the larger number until the two numbers are equal.

Let's take an example to find GCD for 20 and 30.

1. Start iteration from given two numbers 20 and 30, we subtract the smaller number (20) from the larger number (30), which leaves us with 10.
2. Then, we are going to subtract the smaller number (10) from the larger number (20), which leaves us with 10.
3. Since the two numbers are now equal, we take 10 as Greatest Common Divisor (GCD) for 20 and 30.

Let us implement this logic into our javascript code.

function gcd(a, b) {
  	while(a != b){
      	if(a > b) {
          	a -= b;
      	}
      	else {
          	b -= a;
      	}
  	}
  	return a;
}

var result = gcd(20, 30);
console.log(result); // output: 10

In the above code, on each iteration, the smaller integer is subtracted from the larger integer. And the result is assigned to a variable holding the larger integer. The while loop continues iteration until both the integers become equal.

Find GCD using for loop

In this example, we are using for loop that iterates from 1 to the given smallest number.

function gcd(a, b) {
  	var divisor;
  	// looping from 1 to a and b
  	for (let i = 1; i <= a && i <= b; i++) {

	
    	// check if is factor of both integers
    	if( a % i == 0 && b % i == 0) {
      		divisor = i;
    	}
  	}
  	return divisor;
}

var result = gcd(20, 30);
console.log(result);

In the above code, the for loop is used to iterate from 1 to the given smallest number(a or b). If both the given integers are divisible by i, then variable gcd is updated with the current iteration value i as the divisor. The loop continues to execute for checking the highest divisor that fulfills that condition is calculated. This highest divisor is taken as gcd.

Calculate Greatest Common Divisor(GCD) for a given integer array

In the given example, the function gcd_more_than_two_numbers accepts an array of numbers as the argument. Then, the given number array is iterated in for loop to find the GCD of two numbers individually using the function gcd_two_numbers.

function gcd_more_than_two_numbers(input) {
  	if (toString.call(input) !== "[object Array]")  
        return  false;  
  	var len, a, b;
	len = input.length;
	if ( !len ) {
		return null;
	}
	a = input[ 0 ];
	for ( var i = 1; i < len; i++ ) {
		b = input[ i ];
		a = gcd_two_numbers( a, b );
	}
	return a;
}

function gcd_two_numbers(x, y) {
  	if ((typeof x !== 'number') || (typeof y !== 'number')) 
    	return false;
  	x = Math.abs(x);
  	y = Math.abs(y);
  	while(y) {
    	var t = y;
    	y = x % y;
    	x = t;
  	}
  	return x;
}

var gcd = gcd_more_than_two_numbers([5, 15, 110]);
console.log(gcd); // output: 5