C Program to Find HCF of Two Numbers

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

1. Run a while loop until values of ‘n1’ != ‘n2’ (‘n1’ not equal to ‘n2’)
    
2. If ‘n1’ is greater than ‘n2’ then subtract ‘n2’ from ‘n1’ as ‘n1’ = ‘n1’ - ‘n2’
    
3. Otherwise, subtract ‘n1’ from ‘n2’ as ‘n2’ = ‘n2’ - ‘n1’
    
4. Return ‘n1’ or ‘n2’ 

Implementation

/* 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

1. If ‘n1’ < ‘n2’ replace ‘n1’ and ‘n2’
    
2. Find ‘r’ (reminder) using formule ‘n1’%’n2’
    
3. If ‘r’ == 0 return ‘n2’ 
    
4. Else replace ‘n2’ by ‘r’ and ‘n1’ by ‘n2’ 
    
5. Go to step 1

Implementation

/* 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:

• Short int in C Programming
• Bubble Sort Program in C
• Ternary Operator in C
• Conditional Operator in C