C++ Program - Find HCF of Two Numbers

HCF stands for Highest Common Factor. The HCF of two numbers is the largest number that divides both of them.

For example - HCF of 20 and 25 is 5, and HCF of 50 and 100 is 50.

Method 1: Using For Loop to find HCF of two numbers

In the example below, for loop is used to iterate the variable i from 1 to the smaller number. If both numbers are divisible by i, then it modifies the HCF and finally gives the HCF of two numbers.

#include <iostream>
using namespace std;

int main() {
  int x = 50;
  int y = 100;
  int temp, hcf;

  if (x > y) {
    temp = x;
    x = y;
    y = temp;
  }

  for(int i = 1; i < (x+1); i++) {
    if (x%i == 0 && y%i == 0)
      hcf = i;
  }

  cout<<"HCF of "<<x<<" and "<<y<<" is: "<<hcf;
  return 0;
}

The above code will give the following output:

HCF of 50 and 100 is: 50

Method 2: Using While Loop to find HCF of two numbers

In the example below, larger number is replaced by a number which is calculated by subtracting the smaller number from the larger number. The process is continued until the two numbers become equal which will be HCF of two numbers.

#include <iostream>
using namespace std;

int main() {
  int p, q, x, y;
  p = x = 20;
  q = y = 25;

  while (x != y) {
    if (x > y)
      x = x - y;
    else
      y = y - x;
  }

  cout<<"HCF of "<<p<<" and "<<q<<" is: "<<x;
  return 0;
}

The above code will give the following output:

HCF of 20 and 25 is: 5

Method 3: Using the recursive function to find HCF of two numbers

In the example below, recursive function is used. In this method, instead of using subtraction operator(as in above example), modulo operator is used. This method is also known as Euclidean algorithm.

#include <iostream>
using namespace std;

int hcf(int x, int y) {
  if (y == 0)
    return x;
  return hcf(y, x%y);
}

int main() { 
  int x = 250;
  int y = 475;

  cout<<"HCF of "<<x<<" and "<<y<<" is: "<<hcf(x,y);
  return 0;
}

The above code will give the following output:

HCF of 250 and 475 is: 25

Method 4: Using __gcd() function of <algorithm> header file

C++ has built-in function __gcd() in <algorithm> header file which can be used to calculate HCF of two numbers. The syntax for using this function is given below:

//returns 0 if both x and y are zero,
//else returns gcd/hcf of x and y
__gcd(x,y);

Consider the following example:

#include <iostream>
#include <algorithm>
using namespace std;

int main() { 
  int x = 100;
  int y = 150;

  cout<<"HCF of "<<x<<" and "<<y<<" is: "<<__gcd(x,y);
  return 0;
}

The above code will give the following output:

HCF of 100 and 150 is: 50