In this guide, we are going to create a C++ script that calculates the Greatest Common Divisor (GCD) of two given numbers.
GCD, which stands for Greatest Common Divisor, is alternatively referred to as HCF, which stands for Highest Common Factor.
For example
36 = 2 2 3 * 3
60 = 2 2 3 * 5
The greatest common divisor of the two numbers is 2, 2, and 3.
So, the HCF of two numbers is 2 2 3 = 12
20 = 2 2 5
28 = 2 2 7
The greatest common divisor of the two numbers is 2 and 2.
So, the HCF of two numbers is 2 * 2 = 4.
Approach 1
The problem can be solved by finding all the prime factors of the two numbers and then find common factors and return their product.
- Find the factors of the first number
- Find the factors of the second number
- Find common factors of both numbers
- Multiply them to get GCD
C++ code
#include <bits/stdc++.h>
#define MAXFACTORS 1024 // Let us consider max factors can be 1024
using namespace std;
typedef struct
{
int size;
int factor[MAXFACTORS + 1];
int exponent[MAXFACTORS + 1];
} FACTORIZATION;
// Function to find the factorization of M and N
void FindFactorization(int x, FACTORIZATION* factorization)
{
int i, j = 1;
int n = x, c = 0;
int k = 1;
factorization->factor[0] = 1;
factorization->exponent[0] = 1;
for (i = 2; i <= n; i++) {
c = 0;
while (n % i == 0) {
c++;
// factorization->factor[j]=i;
n = n / i;
// j++;
}
if (c > 0) {
factorization->exponent[k] = c;
factorization->factor[k] = i;
k++;
}
}
factorization->size = k - 1;
}
// function to find the gcd using Middle School procedure
int gcdMiddleSchoolProcedure(int m, int n)
{
FACTORIZATION mFactorization, nFactorization;
int r, mi, ni, i, k, x = 1, j;
// Step 1.
FindFactorization(m, &mFactorization);
// Step 2.
FindFactorization(n, &nFactorization);
// Steps 3 and 4.
// Procedure algorithm for computing the
// greatest common divisor.
int min;
i = 1;
j = 1;
while (i <= mFactorization.size && j <= nFactorization.size) {
if (mFactorization.factor[i] < nFactorization.factor[j])
i++;
else if (nFactorization.factor[j] < mFactorization.factor[i])
j++;
else /* if arr1[i] == arr2[j] */
{
min = mFactorization.exponent[i] > nFactorization.exponent[j]
? nFactorization.exponent[j]
: mFactorization.exponent[i];
x = x * mFactorization.factor[i] * min;
i++;
j++;
}
}
return x;
}
int main()
{
int m = 36, n = 60;
cout << "GCD of " << m << " and " << n << " is "
<< gcdMiddleSchoolProcedure(m, n);
return (0);
}
Output
GCD of 36 and 60 is 12
Approach 2
Approach 1 can be effectively addressed by leveraging the Euclidean algorithm. This particular algorithm operates on the principle that the greatest common divisor remains constant even when the smaller number is subtracted from the larger one.
C++ code
#include <iostream>
using namespace std;
int gcd(int a, int b) // The function runs recursive in nature to return GCD
{
if (a == 0) // If a becomes zero
return b; // b is the GCD
if (b == 0)// If b becomes zero
return a;// a is the GCD
if (a == b) // The case of equal numbers
return a; // return any one of them
// Apply case of substraction
if (a > b) // if a is greater subtract b
return gcd(a-b, b);
return gcd(a, b-a); //otherwise subtract a
}
int main()
{
int a = 36, b = 60;
cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
return 0;
}
Output
GCD of 36 and 60 is 12
Approach 3
Approach two can be further enhanced by utilizing a modulo operator instead of subtraction.
C++ code
#include <iostream>
using namespace std;
int gcd(int a, int b) // The function runs recursive in nature to return GCD
{
if (b == 0) // if b becomes 0 return a
return a;
return gcd(b, a % b); // divide to a by b to make smaller number
}
int main()
{
int a = 60, b = 36;
cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
return 0;
}
Output
GCD of 60 and 36 is 12
