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.
- Find GCD using the Euclidean algorithm.
- Find GCD using for loop.
- 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.
- 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.
- Then, we are going to subtract the smaller number (10) from the larger number (20), which leaves us with 10.
- 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
On datainfinities.com, Read articles all around JavaScript, React, Node.js, PHP, Laravel, and Shopify.
Related Blogs
Cannot read property of undefined in JavaScript
What are Parameters, Arguments and Arguments Object in JavaScript
How to Fix error:0308010C:digital envelope routines::unsupported
How to fix npm ERR! Missing script: "start"
Remove an item from an array in JavaScript
node: --openssl-legacy-provider is not allowed in NODE_OPTIONS
ERESOLVE unable to resolve dependency tree error when installing npm packages
How to check internet connection(online or offline) in React
How to Solve TypeError: Cannot destructure property 'basename' of 'React2.useContext'
Explore All Blogs