How to find GCD of two or more numbers?

Programming in general does not require knowledge of advanced maths concepts, but having basic mathematics knowledge is always helpful especially in the case of Competitive Programming (CP).

It does not hurt to learn some concepts and tricks which might come handy. One such concept is finding Greatest Common Divisor (GCD) of two or more numbers. It might not be used directly, it can still give you a basic idea of how to solve mathematical problems using programming.

In mathematics, the greatest common divisor (GCD), also called the greatest common factor of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted gcd(x,y). For example, gcd(8,12) is 4 as 4 is the greatest positive number which divides both 8 and 12.

Applications of GCD

The GCD is used for a number of applications both simple and complex. In fact, you've likely implicitly calculated GCDs without recognizing it when simplifying fractions: reducing a fraction is a matter of dividing both the numerator and denominator by their GCD.

The GCD is also used in the extended Euclidean algorithm to compute modular inverses, which are of extreme importance in encryption schemes such as RSA. Hence it is an important tool in cryptography.

I will be using C++ to write a program to find GCD of 2 or more numbers. As always, there are multiple ways to solve this problem and I will be discussing about 2 or 3 of them.

1. GCD Using for loop and if Statement

This method can be considered as a Brute Force approach, as we iterate over all the numbers starting from 1 till the smallest of the numbers whose GCD we have to find out. Then for each of these numbers, we check if it completely divides all the numbers. If yes, then we call it gcd and move on to next number and repeat the process as we need the greatest number which divides them all completely.

NOTE: The below code is for 2 numbers only. It can be generalised for n numbers as well by dividing each number with all the numbers instead of just 2 of them or by calling the gcd function again and again with the gcd of first 2 numbers and the next number and repeat this process.

#include <iostream>
using namespace std;
int gcd(int n1, int n2){
    int gcd, i;
    for(i=1; i <= n1 && i <= n2; ++i){
        // Checks if i is factor of both integers
        if(n1 % i == 0 && n2 % i == 0)
            gcd = i;
    }
    return gcd;
}

int main(){
    int n1, n2, res;

    cout<<"Enter two integers: \n";
    cin>>n1>>n2;

    res = gcd(n1, n2);

    cout<<"G.C.D of "<<n1<<" and "<<n2<<" is "<<res;

    return 0;
}

2. GCD Using while loop and if Statement

 
This is a better way to find the GCD. In this method, smaller integer is subtracted from the larger integer, and the result is assigned to the variable holding larger integer. This process is continued until n1 and n2 are equal.
 

NOTE: The below code is for 2 numbers only. It can be generalised for n numbers as well by calling the gcd function again and again with the gcd of first 2 numbers and the next number and repeat this process.

#include <iostream>
using namespace std;

int gcd(int n1, int n2){
    while(n1 != n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }

    return n1;
}

int main()
{
    int n1, n2, res;

    cout<<"Enter two integers: \n";
    cin>>n1>>n2;

    res = gcd(n1, n2);

    cout<<"G.C.D of "<<n1<<" and "<<n2<<" is "<<res;

    return 0;
}

3. GCD Using Euclidean Algorithm

Euclidean algorithm is one of the most efficient algorithm used for calculating gcd of 2 or more numbers. We use the modulo operation in this approach i.e. divide the larger number by smaller number and take the remainder. Now, the larger number is swapped by the smaller number and the smaller number is swapped by the remainder and we repeat the whole process until the remainder is not 0.

For more than 2 numbers, we can first find gcd of 2 numbers and then use the gcd along with next number find this pair's gcd and keep repeating until all the numbers are used. We can also use recursion to solve this problem.

#include <iostream>
using namespace std;

int gcd(int n1, int n2){
    int gcd;
    while((n1 % n2) > 0)
    {
        gcd = n1 % n2;
        n1 = n2;
        n2 = gcd;
    }
    return n2;
}

int main()
{
    int n1, n2, res;

    cout<<"Enter two integers: \n";
    cin>>n1>>n2;

    if(n1 >= n2)
        res = gcd(n1, n2);
    else
        res = gcd(n2, n1);

    cout<<"G.C.D of "<<n1<<" and "<<n2<<" is "<<res;

    return 0;
}

Share your thoughts in the comments below and if you liked the article, then give it a thumbs up.

You can check out my blog https://codeunlock.in/ to read other such articles.