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.
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
#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
m > n
m = m – n = 144 – 32 = 112
now m = 112, n = 32
m = m – n = 112 – 32 = 80
now m = 80, n = 32
m = m – n = 80 – 32 = 48
now m = 48, n = 32
m = m – n = 48 – 32 = 16
now m = 16, n = 32
Since, m < n
We will do subtraction in opposite fashion.
n = n – m = 32 – 16 = 16
now m = 16, n = 16
m = n. So, stop. HCF = 16
Method 2 Code
#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.
The HCF of two numbers by definition when one number is 0, is the other non zero number
Example: HCF of 0 and 6 will be 6
We will handle this case in the below program as well.
Method 3 Code
#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
#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.
Incase of -144 & 32 : 16 is highest number that divides both
Incase of -144 & -32 : 16 is again highest number that divides both
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
#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
Login/Signup to comment