# 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:**

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

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

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

*METHOD 1: Brute-Force Approach*

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

- Scan the numbers(N1,N2) from user.
- Initialize GCD = 1.
- Iterate a loop, starting from 1 to small(N1,N2).
- 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; }

Enter the numbers: 100 50 The GCD/HCF of 100 and 50 is 50OUTPUT:

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

Enter the numbers: 100 50 The GCD/HCF of 100 and 50 is 50OUTPUT: