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

**Related Posts:**

**Program to find LCM of two numbers.****Program to check whether entered number is odd or even.****Program to check whether entered number is prime number or not.****Program to check whether entered number is palindrome or not.****Program to check whether entered number is Armstrong Number or Not.****Program to convert binary number to octal number.****Program to convert binary number to decimal number.****Program to convert binary number to hexadecimal number.****Program to convert octal number to binary number.****Program to convert octal number to decimal number.****Program to convert octal number to hexadecimal number.****Program to convert decimal number to binary number.****Program to convert decimal number to octal number.****Program to convert decimal number to hexadecimal number.****Program to convert hexadecimal number to binary number.****Program to convert hexadecimal number to octal number.****Program to convert hexadecimal number to decimal number.****Program to check Leap Year.****Program to find sum of first ‘n’ natural numbers.****Program to Reverse a Number.**