C++ Program to find the HCF or GCD

In this simple python program, we need to find HCF or GCD of two numbers

What is HCF/GCD?

The Highest Common Factor (HCF) of two numbers is the highest possible number that divides both the numbers completely. The highest common factor (HCF) is also called the greatest common divisor (GCD).

How can we calculate HCF?

There are many ways to find the highest common factor of the given numbers. Irrespective of the method, the answer to the HCF of the numbers would always be the same. There are 3 methods to calculate the HCF of two numbers:
•    HCF by listing factors method
•    HCF by prime factorization
•    HCF by division method

HCF by Division Method

The HCF of two numbers can be calculated using the division method.
•    Step 1: Divide the larger number by the smaller number and check the remainder.
•    Step 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.
•    Step 3: continue the long division process till we get the remainder as 0. It should be           noted that the last divisor will be the HCF of those two numbers.


 

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 (condition) 
{ ………….. }

If num > num1, then swap num1 and num2.
Then enter a for loop.
for ( initialization; condition; update )
{ body of loop )

Here our condition is ;
for ( i=1; 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

C++ Source Code

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

OUTPUT

5