HCF Of Two Numbers | C Program

Write a  C program to find  HCF of Two Numbers

 

Here, in this page we will discuss HCF of two numbers in C . The HCF or the Highest Common Factor of two numbers is the largest common factor of two or more values. The HCF can be calculated using some simple mathematical tricks. The following algorithm will determine how a c program can calculate the HCF of two numbers.

HCF

Different Method discussed in post

We have discussed the following methods in the post

  • Method 1: Linear Quest to find HCF
  • Method 2: Euclidean Algorithm: Repeated Subtraction
  • Method 3: Recursive Euclidean Algorithm: Repeated Subtraction
  • Method 4: Modulo Recursive Euclidean Algorithm: Repeated Subtraction
  • Method 5: Handling Negative Numbers in HCF

Method 1

For input num1 and num2

This method works on the quest to find the highest number that divides both num1 & num2

  • Initialize HCF = 1
  • Run a loop in the iteration of (i) between [1, min(num1, num2)]
  • Note down the highest number that divides both num1 & num2
  • That is satisfies (num1 % i == 0 && num2 %) i == 0

Method 1 Code

Run
#include<stdio.h>

int main()
{
    int num1 = 36, num2 = 60, hcf = 1;
    
    for(int i = 1; i <= num1 || i <= num2; i++) {
        if(num1 % i == 0 && num2 % i == 0)
            hcf = i;
    }
    
    printf("The HCF: %d", hcf);
    
    return 0;
}
// Time complexity : O(N)
// Space complexity : O(1)

Output

The HCF: 12

Method 2 (Repeated Subtraction)

This method works on Euclidean Algorithm

Method 2 Code

Run
#include<stdio.h>

int main()
{
    int num1 = 144, num2 = 32, hcf = 1;
    
    while (num1 != num2)
    {
        if (num1 > num2)
            num1 -= num2;
        else
            num2 -= num1;
    }
    
    printf("The HCF : %d", num1);
    
    return 0;
}

Output

The HCF: 16

Method 3 (Recursive – Repeated Subtraction)

This method works on Euclidean Algorithm. It is similar to what we have seen in method 2. But, we are just following a recursive way to do it.

Method 3 Code

Run
#include<stdio.h>

// Recursive function for repeated subtraction HCF calculation
int getHCF(int num1, int num2)
{
    // Handles the case when one of the number is 0 (num1) 
    // Check alert above in explanation
    if (num1 == 0)
       return num2;
    
    // Handles the case when one of the number is 0 (num2)
    // Check alert above in explanation
    if (num2 == 0)
       return num1;
  
    // base case
    if (num1 == num2)
        return num1;
  
    // num1 is greater
    if (num1 > num2)
        return getHCF(num1 - num2, num2);

    return getHCF(num1, num2 - num1);
}
int main()
{
    int num1 = 144, num2 = 32, hcf = 1;
    
    hcf = getHCF(num1, num2);
    
    printf("The HCF : %d", hcf);
    
    return 0;
}

Output

The HCF: 16

Method 4 (Recursive – Repeated Subtraction using Modulo)

This method works on Euclidean Algorithm. It is similar to what we have seen in method 2. But, we are just following a recursive way to do it.

In Addition, we are using modulo operation to reduce the number of subtractions required and improve time complexity

Method 4 Code

Run
#include<stdio.h>

// This method improves complexity of repeated substraction
// By efficient use of modulo operator in euclidean algorithm
int getHCF(int a, int b)
{
    return b == 0 ? a : getHCF(b, a % b);   
}

int main()
{
    int num1 = 144, num2 = 32, hcf = 1;
    
    hcf = getHCF(num1, num2);
    
    printf("The HCF : %d", hcf);
    
    return 0;
}
// Time Complexity: log(max(a,b))

Output

The HCF: 16

Method 5 (Handling Negative Numbers in HCF)

According to the proper definition HCF of two numbers can never be negative.

We can make some minor changes in all of our codes so that they work with negative numbers. As you can see below, such kind of alteration will handle negative numbers

Method 5 Code

Run
#include<stdio.h>

// This method improves complexity of repeated substraction
// By efficient use of modulo operator in euclidean algorithm
int getHCF(int a, int b)
{
    return b == 0 ? a : getHCF(b, a % b);   
}

int main()
{
    int num1 = -144, num2 = 32, hcf = 1;
    
    // if user enters negative number, we just changing it to positive
    // By definition HCF is highest positive number that divides both numbers
    // -144 & 32 : HCF = 16 (as highest num that divides both)
    // -144 & - 32 : HCF = 16 (as highest num that divides both)
    num1 = (num1 > 0) ? num1 : -num1;
    num2 = (num2 > 0) ? num2 : -num2;
    
    hcf = getHCF(num1, num2);
    
    printf("The HCF : %d", hcf);
    
    return 0;
}
// Time Complexity: log(max(a,b))

Output

The HCF: 16

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription