Method 2: Repeated Subtraction
The approach is to repeatedly subtract the smaller number from the larger number, as it end’s up with HCF.
Algorithm
-
Run a while loop until values of ‘n1’ != ‘n2’ (‘n1’ not equal to ‘n2’)
-
If ‘n1’ is greater than ‘n2’ then subtract ‘n2’ from ‘n1’ as ‘n1’ = ‘n1’ - ‘n2’
-
Otherwise, subtract ‘n1’ from ‘n2’ as ‘n2’ = ‘n2’ - ‘n1’
- Return ‘n1’ or ‘n2’
Code
/* C program to find HCF of two numbers using Repeated Substraction */
#include <stdio.h>
int hcf(int n1, int n2)
{
while (n1 != n2)
{
if (n1 > n2)
n1 -= n2;
else
n2 -= n1;
}
return n1;
}
int main()
{
int n1,n2;
n1 = 40, n2 = 10;
printf(" Using Repeated Substraction : \n");
printf(" HCF of %d and %d = %d\n", n1, n2, hcf(n1, n2));
n1 = 36, n2 = 60;
printf(" HCF of %d and %d = %d\n", n1, n2, hcf(n1, n2));
n1 = 24, n2 = 12;
printf(" HCF of %d and %d = %d\n", n1, n2, hcf(n1, n2));
return 0;
}
You can also try this code with Online C Compiler
Run Code
Output
Time and Space Complexity
As the while loop will run ‘n1’ / ’n2’ if (‘n2’ < ’n1’) times and the operations inside the while loop takes only O(1) time, therefore Time Complexity is O(n1/n2) if ‘n2’ < ’n1’, as we have only used variables which take constant space, therefore, the Space Complexity is O(1).
Read More - Time Complexity of Sorting Algorithms
Method 3: Euclidean Approach
This is the best approach used to find the Highest Common Factor of two numbers specially for large numbers because the time complexity in this approach is in logarithms. The approach is to divide the smaller number until the remainder obtained by dividing them becomes zero.
Algorithm
-
If ‘n1’ < ‘n2’ replace ‘n1’ and ‘n2’
-
Find ‘r’ (reminder) using formule ‘n1’%’n2’
-
If ‘r’ == 0 return ‘n2’
-
Else replace ‘n2’ by ‘r’ and ‘n1’ by ‘n2’
- Go to step 1
Code
/* C program to find HCF of two numbers using Euclidean Algorithm */
#include <stdio.h>
int hcf(int n1, int n2)
{
if (n2 > n1)
return hcf(n2,n1);
int r = n1%n2;
if(r == 0)
return n2;
return hcf(n2, r);
}
int main()
{
int n1,n2;
n1 = 40, n2 = 10;
printf(" Using Euclidean Approach : \n");
printf(" HCF of %d and %d = %d\n", n1, n2, hcf(n1, n2));
n1 = 36, n2 = 60;
printf(" HCF of %d and %d = %d\n", n1, n2, hcf(n1, n2));
n1 = 24, n2 = 12;
printf(" HCF of %d and %d = %d\n", n1, n2, hcf(n1, n2));
return 0;
}
You can also try this code with Online C Compiler
Run Code
Output
For better understanding try it by yourself with the help of the C online compiler.
Time and Space Complexity
So, after two iterations, the remainder becomea almost half of its original value. This shows that the number of iterations will be 2logB = O(logB), if B < A, Therefore the Time Complexity is O( log ( min( n1,n2 ) ) ), as we have only used variables which take constant space therefore the Space Complexity is O(1).
Frequently Asked Questions
How to calculate HCF in C?
HCF (Highest Common Factor) or GCD (Greatest Common Divisor) in a program determines the largest number that can exactly divide two integers without leaving a remainder.
What is HCF or GCD in a program?
HCF (Highest Common Factor) or GCD (Greatest Common Divisor) in a program determines the largest number that can exactly divide two integers without leaving a remainder.
What is the formula of HCF into LCM?
The formula connecting HCF and LCM (Least Common Multiple) of two numbers is:
HCF×LCM= Product of the two numbers.
What is the Complexity of the Euclidean Algorithm?
Euclid Algorithm is a recursive algorithm for finding the GCD(Greatest Common Divisor) of two numbers. The Time Complexity of the Euclidean Approach is O( log ( max( n1,n2 ) ) ), Where n1 and n2 are two given numbers. While the Space Complexity is O(1).
Conclusion
In this article, we see the implementation of the C program to find the HCF (Highest Common Factor) of two numbers. We had also seen the output of the written program on some random input.
If you want to learn more about C programs, visit the given links below:
You can also have a look at the interview bundle and interview experiences for placement preparations. Also, enroll in our courses and refer to the problems and mock test available.
Please upvote our blog to help other ninjas grow.
Happy Coding!