Program to find the GCD of two numbers in C++
Before understanding the program of GCD or HCF, one must know what GCD or HCF is.
What is GCD?
The GCD is referred to as Greatest Common Divisor. HCF is the other name for the GCD.
HCF is abbreviated as the highest common factor. The greatest number that divides the two provided numbers is the GCD.
Example 1
8 = 2 * 2 * 2
4 = 2 * 2
The two numbers have the highest common factor of 4.
Therefore, the GCD or the HCF of the two numbers is 4 (2 * 2).
Example 2
20 = 2 * 2 * 5
25 = 5 * 5
The two numbers have the highest common factor of 5.
Therefore, the GCD or the HCF of the two numbers is 5.
Example 3
15 = 3 * 5
45 = 3 * 3 * 5
The two numbers have the highest common factor of 15.
Therefore, the GCD or the HCF of the two numbers is 15 (3 * 5).
Method 1
Finding all the prime factors for the two numbers, then identifying common factors and returning their product, will solve the issue.
- Determine the first number's divisors.
- Determine the second number's divisors.
- Determine the two numbers' common divisors.
- For GCD, multiply all the common divisors.
Program for method 1 in C++:
#include <bits/stdc++.h>
#define MAXDIVISORS 1024 // let us define 1024 as the maximum divisors
using namespace std;
typedef struct
{
int size;
int factor[MAXDIVISORS + 1];
int exponent[MAXDIVISORS + 1];
} FACT;
// the below function is used for determining the factorization of M and N
void FindFactorization(int x, FACT* 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 that uses the Middle School method to find the gcd.
int gcd(int a, int b)
{
FACT aFactorization, bFactorization;
int r, ai, bi, i, k, x = 1, j;
// Step 1.
FindFactorization(a, &aFactorization);
// Step 2.
FindFactorization(b, &bFactorization);
// Steps 3 and 4.
// The algorithm for the highest common factor or
// greatest common divisor is given by :
int min;
i = 1;
j = 1;
while (i <= aFactorization.size && j <= bFactorization.size) {
if (aFactorization.factor[i] < bFactorization.factor[j])
i++;
else if (bFactorization.factor[j] < aFactorization.factor[i])
j++;
else /* if arr1[i] == arr2[j] */
{
min = aFactorization.exponent[i] > bFactorization.exponent[j]
? bFactorization.exponent[j]
: aFactorization.exponent[i];
x = x * aFactorization.factor[i] * min;
i++;
j++;
}
}
return x;
}
int main()
{
int a, b;
cin>>a;
cin>>b;
cout << "GCD of " << a << " and " << b << " is "
<< gcd(a, b);
return (0);
}
Output 1:
In the above-displayed output, the input is two numbers. The two numbers are 8 and 4.
8 = 2 * 2 * 2
8 has divisors 2,2, and 2.
4 = 2 * 2
4 has divisors 2 and 2.
Following method 1, all the common divisors of both numbers should be multiplied to get the GCD or HCF.
The two numbers have the highest common factor of 4.
Therefore, the GCD or the HCF of the two numbers is 4 (2* 2).
Output 2:
In the above-displayed output, the input is two numbers. The two numbers are 20 and 25.
20 = 2 * 2 * 5
20 has the divisors 2,2, and 5.
25 = 5 * 5
25 has the divisors 5 and 5.
Following method 1, all the common divisors of both numbers should be multiplied to get the GCD or HCF.
The two numbers have the highest common factor of 5.
Therefore, the GCD or the HCF of the two numbers is 5 (5).
Output 3:
In the above-displayed output, the input is two numbers. The two numbers are 15 and 45.
15 = 3 * 5
15 has divisors 3 and 5.
45 = 3 * 3 * 5
45 has divisors 3,3, and 5.
Following method 1, all the common divisors of both numbers should be multiplied to get the GCD or HCF.
The two numbers have the highest common factor of 15.
Therefore, the GCD or the HCF of the two numbers is 15 (3 * 5).
Method 2
Euclidean algorithm by subtraction is an easy and traditional strategy.
The method being employed is repeated subtraction. It brings the result forward each time until it equals the number being subtracted, if any. A GCD exists if the response is higher than 1. ( besides 1). Since there is only one additional common divisor, both integers are coprime if the response is 1.
Pseudo-code for the above method is given as:
def gcd(a, b):
if a == b:
return a
if a > b:
gcd(a – b, b)
else:
gcd(a, b – a)One number eventually becomes a factor of another; thus, rather than repeatedly subtracting until both are equal, we check to see if the first number is a factor of the second.
Example:
For instance, if a=98 and b=56, we would write a=a-b, and b would remain the same. So a=98-56=42 & b= 56 . As b>a, we determine whether b%a==0. We proceed because the answer is no. Now that b>a, b=b-a, and a stays the same. So b= 56-42 = 14 & a= 42 . We check to see whether a%b==0 because a>b. Now the answer is yes. As a result, we print smaller between a and b as HCF, i.e., 42 is three times 14; therefore, HCF equals 14.
Similar to the case where a=36 and b=60, here b>a makes b = 24 and a=36, but a%b!=0. Now that a>b, a=12 and b=24. and b%a==0. The HCF or the GCD of 36 and 60 is 12 and is smaller between a and b.
Method explanation:
To find the GCD of two numbers, first, find the smallest of the two numbers, and then find the highest common factor of that smallest number, which is also a factor of the other.
Program 1:
// Program that represents the code for GCD of two numbers.
#include <iostream>
using namespace std ;
// a function that returns the gcd of a and b
int gcd(int a, int b)
{
int result = min(a, b) ; // Find Minimum of a and b
while (result > 0) {
if (a % result == 0 && b % result == 0) {
break ;
}
result-- ;
}
return result ; // return gcd of a nd b
}
// Driver program to test the above function
int main()
{
int a, b ;
cin >> a ;
cin >> b ;
cout << "GCD of " << a << " and " << b << " is "
<< gcd(a, b);
return 0 ;
}Output
In the above-displayed output, the input is two numbers. The two numbers are 98 and 56.
Here, a=98 and b=56.
In the given numbers, the minimum number is 56. (b=56)
The variable result stores the minimum of the given values.
Using the while loop (result>0) , the loop body checks a%b ==0. As 98 % 56 != 0, the loop body continues until result>0 or the condition is fulfilled.
In this instance, the loop continues until it discovers the component that results in a 0.
14 is the HCF or GCD of the numbers 98 and 56.
Output 2
In the above-displayed output, the input is two numbers. The two numbers are 14 and 6.
Here, a=14 and b=6.
In the given numbers, the minimum number is 6. (b=6)
The variable result stores the minimum of the provided values.
Using the while loop (result>0) , the loop body checks a%b ==0. As 14 % 6 != 0, the loop body continues until result>0 or the condition is fulfilled.
In this instance, the loop continues until it discovers the component that results in a 0.
2 is the HCF or GCD of the numbers 14 and 6.
The program 1 has a time complexity of O(min(a,b)).
The Auxiliary Space required for program 1 is O(1) or constant.
Program 2
The Euclidean method, the primary algorithm used for this purpose, is an effective solution. The idea is that if you subtract a smaller number from a larger number, the GCD of the two numbers remains constant.
#include <iostream>
using namespace std;
// A Recursive function returns the gcd of the given two numbers.
int gcd(int a, int b)
{
// 0 divided by anything (any number) equals zero.
if (a == 0)
return b ;
if (b == 0)
return a ;
// base case
if (a == b)
return a ;
// a is larger
if (a > b)
return gcd(a-b, b) ;
return gcd(a, b-a) ;
}
// Driver program to test the above function
int main()
{
int a, b;
cin >> a ;
cin >> b ;
cout << "GCD of "<< a <<" and "<< b <<" is "<<gcd(a, b) ;
return 0 ;
}
Output 1
In the above-displayed output, the input is two numbers. The two numbers are 8 and 4.
Here, a = 8 and b = 4.
The program is a recursive function. For a = 8 and b = 4, the condition is satisfied for the “if” block that contains condition a>b. In the if block, it returns gcd(a-b,b).
a-b = 8 – 4 = 4;
Now, the function starts with numbers a = 4 and b = 4.
As the “if” block a == b is satisfied, the function returns “a” to the function gcd(8,4).
The “a” value contains value 4. The gcd(8,4) returns the value 4 to the main function.
The returned value is the HCF or GCD of the numbers provided.
Therefore, the HCF of 8 and 4 is 4.
The second program's time complexity is O(min(a,b)).
The Auxiliary Space required for program 2 is O(min(a,b)).
Program 3
Another way of writing the program is by using the Dynamic Programming Method (Top Down Memorization):
// Program that represents the code for GCD of two numbers.
#include <bits/stdc++.h>
using namespace std ;
int static gpp[1001][1001] ;
// The below function returns the HCF or gcd of the two numbers.
int gcd(int a, int b)
{
// 0 divided by anything (any number) equals zero.
if (a == 0)
return b ;
if (b == 0)
return a ;
// base case
if (a == b)
return a ;
// if the value a is already
// exists in gpp
if(gpp[a][b] != -1)
return gpp[a][b] ;
// a is larger value
if (a > b)
gpp[a][b] = gcd(a-b, b) ;
// b is larger value
else
gpp[a][b] = gcd(a, b-a) ;
// return gpp
return gpp[a][b] ;
}
// Driver program to test the above function
int main()
{
int a ;
int b ;
cin >> a ;
cin >> b ;
memset(gpp, -1, sizeof(gpp));
cout << "GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0 ;
}
Output 1
In the above-displayed output, the input is two numbers. The two numbers are 20 and 25.
The GCD for the numbers 20 and 25 is 5.
The program 3 has a time complexity of O(min(a,b)).
The Auxiliary Space required for program 3 is O(1).
Method 3
The Euclidean algorithm via subtraction is replaced by a superior method. We make no deductions in this case. We continue to divide the bigger number by the smaller one. By applying the modulo operator in the Euclidean method, more can be discovered about this effective solution.
Program
// Program that represents the code for GCD of two numbers.
#include <iostream>
using namespace std ;
// a recursive function for gcd of the numbers a and b.
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b) ;
}
// Driver program to test the above function
int main()
{
int a = 100, b = 1000 ;
cout<<"GCD of "<< a <<" and "<< b <<" is "<<gcd(a, b);
return 0 ;
}
Output
The above-displayed output is for the numbers 100 and 1000.
Here, a=100 and b=1000.
The program is a recursive function that returns “a” when b == 0, otherwise the functions returns gcd(b, a%b).
For the numbers 100 and 1000, the function checks b == 0. As b = 1000, the function returns gcd(100, 1000%100). The function starts again with gcd(100,0).
Now, as b==0, the function returns value "a" to the previously called function.
The gcd(100,1000) returns the value 100 to the main function.
Therefore, the GCD of the numbers 100 and 1000 is 100.