# 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.

# 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.

`#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.

`#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.

`#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;}`

--

--