Find greatest common divisor (GCD) in JavaScript

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

 

Related Blogs

Cannot read property of undefined in JavaScript

Cannot read property of undefined in JavaScript

The TypeError: Cannot read property of undefined occurs when we try to read a property on an undefined variable or when we try to access a property on a DOM element that doesn't exist.

How to Fix error:0308010C:digital envelope routines::unsupported

How to Fix error:0308010C:digital envelope routines::unsupported

To fix the error:0308010C:digital envelope routines::unsupported, enable the legacy provider for Node.js by passing --openssl-legacy-provider flag to webpack.

ckeditor

How to Integrate Custom Build CKEditor5 with React

Explains how to create a custom build CKEditor5 and integrate with react with sample code.

pm2 cluster

Scaling Node.js Applications With PM2 Clusters

Learn cluster modules in node js, install and configure PM2 in production, and implement PM2 clusters using the PM2 ecosystem without any modification in the current application code.

call-stack-in-javascript

What is Call Stack in JavaScript

JavaScript Call Stack is a mechanism to keep track of multiple function calls and manage execution context. This article describes how the call stack works with examples.

Factory Design Pattern in JavaScript

Factory Design Pattern in JavaScript

Factory allows you to handle all the object creation in a centralized location which helps the code clean, concise, and maintainable. Understand deeply with examples.

event loop and callback queue

Event Loop and Callback Queue in JavaScript

The event loop keeps monitoring the call stack and callback queue for executing callback functions. Read more about web APIs, callback queue, microtask queue, event loops, and starvation.

Objects Are Not Valid as a React Child

React objects are not valid as a react child

The React error "Objects are not valid as a React child" occurs when we render an object or an array in our JSX code. We can't use JavaScript objects as a child in React.

Can't Perform a React State Update on an Unmounted Component

Can't Perform a React State Update on an Unmounted Component

React Warning “Can't perform a react state update on an unmounted component” is caused when we try to update the state after the component was unmounted. Explains how to fix it.