Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Method 1: Linear Hunt
2.1.
Algorithm
2.2.
Code
2.3.
Output
2.4.
Time and Space Complexity
3.
Method 2: Repeated Subtraction
3.1.
Algorithm
3.2.
Code
3.3.
Output
3.4.
Time and Space Complexity
4.
Method 3: Euclidean Approach
4.1.
Algorithm
4.2.
Code
4.3.
Output
4.4.
Time and Space Complexity
5.
Frequently Asked Questions
5.1.
How to calculate HCF in C? 
5.2.
What is HCF or GCD in a program? 
5.3.
What is the formula of HCF into LCM? 
5.4.
What is the Complexity of the Euclidean Algorithm?
6.
Conclusion
Last Updated: Jul 15, 2024
Easy

C Program to Find HCF of Two Numbers

Author Ayushi Goyal
0 upvote

Introduction

In this blog, we will discuss the solution to the problem of finding the HCF(Highest Common Factor) of two numbers. We will discuss three different C program to find HCF of two numbers, and their time and space complexities. 

Before discussing the C program to find HCF of two numbers, Let’s first discuss what HCF(Highest Common Factor) means.

HCF(Highest Common Factor) is also known as GCF(Greatest Common Factor) or GCD(Greatest Common Divisor). HCF of two numbers is the greatest integer that divides both of them completely, i.e., the remainder is zero.

For Example: 

 

The different methods to find HCF of two numbers are:

  1. Linear Search for HCF
  2. Repeated Subtraction
  3. Euclidean Approach

Method 1: Linear Hunt

The approach is to check for each number starting from 1 to the minimum and return the maximum number that completely divides both numbers. 

Algorithm

  1. Initialize a variable ‘hcf’ to return the answer i.e., hcf=1
     
  2. Find the minimum of two numbers, ‘n1’ and ‘n2’
     
  3. Run a loop from 1 to ‘min’ value 
     
  4. For each value of ‘i’, check if ‘i’ completely divides ‘n1’ and ‘n2’, then set the value of ‘hcf’ to ‘i’
     
  5. Return value of ‘hcf’ variable

Code

/* C program to find HCF of two number using iterative approach */

#include <stdio.h>
int hcf(int n1, int n2)
{
    int min = (n1<n2) ? n1 : n2;
    int hcf=1;
    for(int i=1; i<=min; i++)
    {
        if(n1%i==0 && n2%i==0)
        {
            hcf = i;
        }
    }
    return hcf;
}

int main()
{
	int n1,n2;
	
	n1 = 40, n2 = 10;
	printf(" Using iterative 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

Time and Space Complexity

Code block inside the for loop takes O(min) time complexity, therefore, the Time Complexity is O(min(n1,n2)), as we have only used variables that take constant space, therefore, the Space Complexity is O(1).

Also Read - Dynamic Array in C

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’ 

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

  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

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 numbersWe 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!

Live masterclass