Program to Find the Highest Common Factor (HCF) in C++

Highest Common Factor (HCF)

The Highest Common Factor (HCF) of two numbers is the largest number that divides both of them without leaving a remainder. For example, the HCF of 36 and 60 is 12.

We will explore three different methods to find the HCF of two numbers using C++ programming.

Method 1: Using Euclidean Algorithm

We use the Euclidean algorithm, which repeatedly replaces the larger number with its remainder when divided by the smaller number, until the remainder becomes zero.

#include <iostream>
using namespace std;

int findHCF(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int num1, num2;
    cout << "Enter two numbers: ";
    cin >> num1 >> num2;
    
    cout << "HCF of " << num1 << " and " << num2 << " is " << findHCF(num1, num2);
    return 0;
}
            

Output:

Enter two numbers: 36 60
HCF of 36 and 60 is 12

Method 2: Using Prime Factorization

In this method, we find all prime factors of both numbers and take the product of the common ones.

#include <iostream>
using namespace std;

int min(int a, int b) {
    return (a < b) ? a : b;
}

int findHCFPrimeFactorization(int a, int b) {
    int hcf = 1;
    for (int i = 2; i <= min(a, b); i++) {
        while (a % i == 0 && b % i == 0) {
            hcf *= i;
            a /= i;
            b /= i;
        }
    }
    return hcf;
}

int main() {
    int num1, num2;
    cout << "Enter two numbers: ";
    cin >> num1 >> num2;
    
    cout << "HCF of " << num1 << " and " << num2 << " is " << findHCFPrimeFactorization(num1, num2);
    return 0;
}
            

Output:

Enter two numbers: 36 60
HCF of 36 and 60 is 12

Method 3: Using Recursion

We can also find HCF using recursion, following the Euclidean algorithm.

#include <iostream>
using namespace std;

int findHCFRecursive(int a, int b) {
    if (b == 0)
        return a;
    return findHCFRecursive(b, a % b);
}

int main() {
    int num1, num2;
    cout << "Enter two numbers: ";
    cin >> num1 >> num2;
    
    cout << "HCF of " << num1 << " and " << num2 << " is " << findHCFRecursive(num1, num2);
    return 0;
}
            

Output:

Enter two numbers: 36 60
HCF of 36 and 60 is 12