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 <stdio.h>

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

int main() {
    int num1, num2;
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);
    
    printf("HCF of %d and %d is %d", num1, num2, 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 <stdio.h>

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;
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);
    
    printf("HCF of %d and %d is %d", num1, num2, 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 <stdio.h>

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

int main() {
    int num1, num2;
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);
    
    printf("HCF of %d and %d is %d", num1, num2, findHCFRecursive(num1, num2));
    return 0;
}
            

Output:

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