Calculate Greatest Common Divisor (GCD) in C++

Exercise:

Write a C++ program to calculate GCD using for loop or while loop:

Method 1: Calculating HCF/GCD with while loop:

Click Here to View the Solution:
#include <iostream>
using namespace std;
int main()
{
    int num1, num2;
    cout << "Enter any two positive numbers:\n ";
    cin >> num1 >> num2;
    while(num1 != num2)
    {
        if(num1 > num2)
        num1 -= num2;
        else
        num2 -= num1;
    }
    cout << "Highest Common Factor is: " << num1;
    return 0;
}
Click Here to View the Output:
Enter any two positive numbers:
 24
 9
 Highest Common Factor is: 3
Click Here to View the Explanation:
  • HCF (highest common factor) or GCD (greatest common divisor) is a common number which divides 2 whole numbers.
  • While loop is used and a condition is provided to enter the loop.
  • The code says num1 -= num2, meaning num1 = num1 – num2.
  • The screen displays the new assigned value of num1 when the loop is exited.
  • The code subtracts the lesser number from the greater number and assigned a new number to the greater number. This replaces the value of greater number.
  • The loop will not be exited until the two entered numbers are not equal. The number at which num1 and num2 is equal to the GCD.

Method 2: Calculating HCF/GCD with for loop:

Click Here to View the Solution:
#include <iostream>
using namespace std;
int main()
{
    int hcf,num1, num2,temp;
    cout << "Enter two numbers:\n ";
    cin >> num1 >> num2;
    // Swapping variables n1 and n2 if n2 is greater than n1.
    if ( num2 > num1)
    {   
        temp = num2;
        num2 = num1;
        num1 = temp;
    }
    for (int i = 1; i <=  num2; ++i)
    {
        if (num1 % i == 0 && num2 % i ==0)
        {
            hcf = i;
        }
    }
    cout << "Highest Common Factor is " << hcf;
    return 0;
}
Click Here to View the Output:
Enter two numbers:
 56
 32
 Highest Common Factor is 8
Click Here to View the Explanation:
  • This is a very easy program.
  • The program works only if num2 is greater than num1. In case num2 is the lesser number, the numbers are swapped using a temporary variable using if statement.
  • A for loop is added, with an if statement within it to calculate GCD in this code.
  • When the for loop is entered, the value of i which was put equal to 1 is incremented by 1 every time the compiler runs through the loop again. The for loop is iterated until num2 is equal to the incremented value of i.
  • Both numbers are divided by i. Wherever both numbers divide by i giving 0 as remainder, the loop is exited and number is printed on the screen as HCF.

%d bloggers like this: