How To Find The GCD Of Two Integers In Javascript

I am writing this as a follow-up to two previous articles I wrote on how to find the gcd of two integers in Python and how to find the gcd of two numbers in PHP. The gcd of two integers is the largest integer that divides evenly into both integers with no remainder. This article describes how to write the JavasScript code, and then you can use it in a Firefox or Google Chrome console to calculate the gcd of the two integers.

Calculate The GCD OF Two Integers With User Input In The Developer Console

Unfortunately, JavaScript does not have a native function to calculate gcd. But no problem, this article will show you the JavaScript code to calculate GCD.

Below is the JavaScript code:

function gcd(x,y) {
    /*
    This function finds the gcd (greatest common divisor)
    of the two integers x and y and returns the gcd
    It uses the Euclidean Algorithm.
    The general form for the Euclidean Algorithm is
    r_k = q_(k+2)*r_(k+1) + r_(k+2)
    Here _ denotes subsripts. 
    Above Parentheses indicate that the subscript is more than 1 character long
    for the code I just remove the _ and ()
    initally r_k = x and r_(k+1) = y
    */
    //if the integers are the same, then their gcd is the same number
    if (x === y) {
        return x;
    }
    //if the one of the integers is is 0, then the gcd is 1    
    else if (x === 0 || y === 0) {
        return 1;
    } 
    else {
        //we assume x is greater than y. If y is greater than x, just switch them
        var temp = 1;
        if (y > x) {
            temp = x;
            x = y;
            y = temp;
        }

        /* first round. The initial conditions are r_k = x and r_(k+1) = y
        note that q_(k+2) is part of the Euclidean Algorithm.
        But, we don't need it in our function. We only calculate
        rkp2 and use previous remainder values in the sequence. */

        rk = x;
        rkp1 = y;

        //qkp2 = Math.floor(x/y) Though this is in the Euclidean Algorithm, we don't need this

        rkp2 = rk % rkp1;
        if (rkp2 === 0) {
            return rkp1;
        }
        else {
            while (rkp2 != 0) {
                rk = rkp1;
                rkp1 = rkp2;
                rkp2 = rk % rkp1;
            }
            return rkp1;
        }
    }
}

To test this code, all you need to do is to open up a Firefox or Chrome browser and then type ‘F12’. The developer console will show up. Then just paste in the JavaScript function.

Then you can test out the gcd of various pairs of integers. For example,
gcd(64,784)
should print out 16.

You can also download the code here.

If you prefer to have the JavaScript displayed on the screen with HTML, you could just take the code above, and add an HTML form, and on submission, calculate the gcd of the two integers from two text input boxes where the user enters the integers.

What did you think of this article? Did you learn anything useful about JavaScript.? Let’s discuss it in the comments below.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.