Program to find GCD of 2 or more numbers

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store