C++ Program to find the HCF or GCD

In this simple C++ program, we need to find the HCF or GCD of two numbers

What is HCF/GCD?

The Highest Common Factor (HCF) is the highest number that can able to divide the given two numbers. It is also known as Greatest Common Divisor.

How can we calculate HCF?

HCF or GCD can be calculated by many ways, in that only 3 of them are widely used, which are given below

• HCF by listing factors method
• HCF by prime factorization
• HCF by division method

HCF by Division Method

In this C++ program, we are using the division method for calculating the HCF

1. Divide the larger integer by the lower integer and check the remainder.
2. Then, make the remainder of the previous step the new divisor and the divisor of the previous step as the new dividend and perform the long division again.
3. Continue the division until the remainder reaches zero anf we take the divisor of the last divisions as HCF.

How do implement a C++ program to find HCF?

Here the logic used to find the HCF is to find the largest integer which can perfectly divide two integers. The user is asked to enter two numbers. Load these entered values into two integer type variables num1 and num2. Compare both integers and store the smaller integer in num2. This can be done by an if condition.

If num > num1, then swap num1 and num2.Then enter a for loop.Here are the condition is int i = 1; i <=  num2; ++i .If both the numbers are divisible by I then that number is stored in a variable hcf. This process is repeated in each iteration. Finally, HCF will be stored in the variable hcf.

Algorithm

Step 1:  Call the header file iostream.

Step 2: Use the namespace std.

Step 3: Open the integer type main function; int main().

Step 4: Declare integer variables; num1, num2, hcf

Step 5: Print a message to enter two numbers.

Step 6: Read the numbers into the variables num1 and num2.

Step 7: compare num1 and num2; 
              If num2 > num1; swap num1 and num2;

Step 8: Start the for loop from i=0 to <= num2;
             Divide num1 and num 2 by i ; if both are divisible then 
             hcf =i;

Step 9:  print hcf;

Step 10: Exit

                                          #include <iostream>
using namespace std;

int main() {
  int num1, num2, hcf;
  cout << "Enter two numbers: ";
  cin >> num1 >> num2;

  // swapping variables num1 and num2 if num2 is greater than num1.
  if ( num2 > num1) {   
    int temp = num2;
    num2 = num1;
    num1 = temp;
  }
    
  for (int i = 1; i <=  num2; ++i) {
    if (num1 % i == 0 && num2 % i ==0) {
      hcf = i;
    }
  }

  cout << "HCF = " << hcf;

  return 0;
}
                                      

Enter two numbers: 12
60
HCF = 12