JavaScript: Greatest common divisor (gcd) of two integers

JavaScript Math: Exercise-8 with Solution

GCD of Two Numbers

Write a JavaScript function to get the greatest common divisor (GCD) of two integers.
Note:
According to Wikipedia - In mathematics, the greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.

Test Data :
console.log(gcd_two_numbers(12, 13));
console.log(gcd_two_numbers(9, 3));
Output :
1
3

Visual Presentation:

Sample Solution-1:

JavaScript Code:

// Define a function named gcd_two_numbers that calculates the greatest common divisor (GCD) of two numbers.
function gcd_two_numbers(x, y) {
    // Check if both x and y are of type number, if not, return false.
    if ((typeof x !== 'number') || (typeof y !== 'number')) 
        return false;
    
    // Take the absolute values of x and y to ensure positivity.
    x = Math.abs(x);
    y = Math.abs(y);
    
    // Iterate using the Euclidean algorithm to find the GCD.
    while(y) {
        // Store the value of y in a temporary variable t.
        var t = y;
        // Calculate the remainder of x divided by y and assign it to y.
        y = x % y;
        // Assign the value of t (previous value of y) to x.
        x = t;
    }
    // Return the GCD, which is stored in x after the loop.
    return x;
}

// Output the GCD of 12 and 13 to the console.
console.log(gcd_two_numbers(12, 13));
// Output the GCD of 9 and 3 to the console.
console.log(gcd_two_numbers(9, 3));

Output:

1
3

Flowchart:

Sample Solution-2:

Calculates the greatest common divisor between two or more numbers/arrays.

• The inner _gcd function uses recursion.
• Base case is when y equals 0. In this case, return x.
• Otherwise, return the GCD of y and the remainder of the division x/y.

JavaScript Code:

// Source: https://bit.ly/3hEZdCl
// Define a constant named gcd which calculates the greatest common divisor (GCD) of multiple numbers.
const gcd = (...arr) => {
    // Define an inner function _gcd to calculate the GCD of two numbers using the Euclidean algorithm.
    const _gcd = (x, y) => (!y ? x : gcd(y, x % y));
    // Reduce the array of numbers to find the GCD of all numbers.
    return [...arr].reduce((a, b) => _gcd(a, b));
};

// Output the GCD of 12 and 13 to the console.
console.log(gcd(12, 13));
// Output the GCD of 9 and 3 to the console.
console.log(gcd(9, 3));
// Output the GCD of 8 and 36 to the console.
console.log(gcd(8, 36));
// Output the GCD of 12, 8, and 32 using the spread operator to pass the array elements individually.
console.log(gcd(...[12, 8, 32]));

Output:

1
3
4
4

Flowchart:

Live Demo:

See the Pen javascript-math-exercise-8 by w3resource (@w3resource) on CodePen.

For more Practice: Solve these Related Problems:

• Write a JavaScript function that calculates the GCD of two numbers recursively using the Euclidean algorithm.
• Write a JavaScript function that finds the GCD of two numbers using an iterative approach without recursion.
• Write a JavaScript function that implements the subtraction-based method for calculating the GCD of two numbers.
• Write a JavaScript function that computes the GCD while handling edge cases such as zero or negative inputs.

Improve this sample solution and post your code through Disqus.

Previous: Write a JavaScript function to find the lowest value in an array.
Next: Write a JavaScript function to find the GCD (greatest common divisor) of more than 2 integers.