Compute GCD of two Numbers

“Compute GCD of 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 (Compute GCD of two Numbers):

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

There are several ways to compute GCD of two numbers. Two of them are:

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

METHOD 1: Brute-Force Approach to compute GCD of two numbers

The steps to compute 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 GCD of two numbers is as follows:

/* C++ Program to compute GCD of two numbers */
#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 to compute GCD of two numbers

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 GCD of two numbers is as follows:

/* C++ Program to compute GCD of two numbers */
#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:

1. Program to find LCM of two numbers.
2. Program to check whether entered number is odd or even.
3. Program to check whether entered number is prime number or not.
4. Program to check whether entered number is palindrome or not.
5. Program to check whether entered number is Armstrong Number or Not.
6. Program to convert binary number to octal number.
7. Program to convert binary number to decimal number.
8. Program to convert binary number to hexadecimal number.
9. Program to convert octal number to binary number.
10. Program to convert octal number to decimal number.
11. Program to convert octal number to hexadecimal number.
12. Program to convert decimal number to binary number.
13. Program to convert decimal number to octal number.
14. Program to convert decimal number to hexadecimal number.
15. Program to convert hexadecimal number to binary number.
16. Program to convert hexadecimal number to octal number.
17. Program to convert hexadecimal number to decimal number.
18. Program to check Leap Year.
19. Program to find sum of first ‘n’ natural numbers.
20. Program to Reverse a Number.