# Compute GCD/HCF between two Numbers

Compute GCD/HCF between two Numbers” is a basic programming exercise problem. Here, we are given two numbers, entered by user and our task is to compute GCD (Greatest Common Divisor) between two numbers.

GCD: A GCD, also known as HCF, of two number is a largest possible number which can divide both the numbers.

Example:

```INPUT:
N1 = 100, N2 = 50
OUTPUT:
The GCD/HCF of 100 and 50 is 50```

There are several ways to compute the GCD between two number. Two of them are:

1. Brute-force, using loop.
2. Equalizing the number.

METHOD 1: Brute-Force Approach

The steps to find the GCD of two numbers are as follows:

1. Scan the numbers(N1,N2) from user.
2. Initialize GCD = 1.
3. Iterate a loop, starting from 1 to small(N1,N2).
4. In each iteration, if both N1 and N2 are exactly divisible by iterator, the value of iterator is assigned to GCD.

C++ Program to compute the GCD/HCF of two number:

```#include<bits/stdc++.h>
using namespace std;
int main()
{
//Scan the number
int n1,n2;
cout<<"Enter the numbers:";
cin>>n1>>n2;

// Computing the GCD/HCF
int GCD = 1;
for(int i = 1; i<=n1 && i<=n2; i++)
{
if(n1%i == 0 && n2%i == 0)
GCD = i;
}
cout<<"The GCD/HCF of "<<n1<<" "<<n2<<" is "<<GCD;
}
```
```OUTPUT:
Enter the numbers: 100 50
The GCD/HCF of 100 and 50 is 50```

METHOD 2: Equalizing the number

This is much better method in terms of time complexity of the solution. Here, smaller number 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. When they become equals, that number would be the GCD.

C++ Program to compute the GCD/HCF of two number:

```#include<bits/stdc++.h>
using namespace std;
int main()
{
//Scan the number
int n1,n2;
cout<<"Enter the numbers:";
cin>>n1>>n2;

// Computing the GCD/HCF
while(n1!=n2)
{
/* If n1 is greater, subtract n2 from n1 */
if(n1 > n2)
n1 -= n2;
/* If n2 is greater, subtract n1 from n2 */
else
n2 -= n1;
}

// Printg the GCD/HCF
cout<<"The GCD/HCF of "<<n1<<" "<<n2<<" is "<<GCD;
}
```
```OUTPUT:
Enter the numbers: 100 50
The GCD/HCF of 100 and 50 is 50```

Related Posts: