C Program to Find the HCF of Two Numbers

Last Updated on May 11, 2023 by Prepbytes

In C programming, the HCF (Highest Common Factor) of two numbers is the largest positive integer that divides them without leaving a remainder. It is also known as GCD (Greatest Common Divisor) of two numbers. The HCF of two numbers is a commonly used mathematical concept in various applications such as simplifying fractions, reducing a polynomial to its lowest terms, and finding the ratio between two quantities.

There are various approaches to finding the HCF of two numbers in C programming, such as using loops, recursion, and Euclid’s algorithm. These methods involve finding the factors of the given numbers and then identifying the common factors that are the highest. Once the HCF is determined, it can be used in various arithmetic and mathematical operations.

Different Methods to Find HCF of Two Numbers

The terms HCF (Highest Common Factor), GCF (Greatest Common Factor), and GCD (Greatest Common Divisor) are interchangeable. The HCF of those two numbers is the highest integer that divides two integers equally, leaving no residual.

Following are the methods to find HCF of two numbers are:

Method 1: Linear Search for HCF

While using linear search for finding HCF, the following are the steps:

• Step 1: Initialize a variable name hcf and assign 1 to it i.e.hcf =1.
• Step 2: Find the smaller numbers ‘n1’ and ‘n2’.
• Step 3: Run a loop going from 1 to the smaller value.
• Step 4: If ‘i’ entirely divides ‘n1’ and ‘n2’ for each value of ‘i,’ set the value of ‘hcf’ to ‘i.
• Step 5: Return the value of variable hcf.

Code Implementation

#include <stdio.h>

int main()
{
    int n1,n2;
    
    n1 = 36, n2 = 60;
    
    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;
        }
    }

    printf(" HCF of %d and %d = %d\n", n1, n2, hcf);

    
    return 0;
}

Output

HCF of 36 and 60 = 12

Time Complexity: O(min(n1,n2))
Space Complexity: O(1)

Method 2: Repeated Subtraction

The following steps are as follows:

• Step 1: Run a while loop until the values of ‘n1’!= ‘n2’ (‘n1’ does not equal ‘n2’)
• Step 2: If ‘n1’ is bigger than ‘n2,’ then ‘n2’ must be subtracted from ‘n1’ since ‘n1’ equals ‘n1’ – ‘n2’.
• Step 3: If not, ‘n1’ must be subtracted from ‘n2’ since ‘n2’ = ‘n2’ – ‘n1’
• Step 4: print n1 or n2

Code Implementation

#include<stdio.h>

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

Output

The HCF: 12

Time Complexity: O(n1/n2)
Space Complexity: O(1)

Method 3: Euclidean Approach

The temporal complexity in this method uses logarithms, making it the best method for finding the highest common factor of two integers, especially for big values. The strategy is to divide the smaller number until the result of their division has a remainder of zero.

The following steps are as follows:

• Step 1: If ‘n1’ < ‘n2’ replace ‘n1’ and ‘n2’
• Step 2: Using the formula ‘n1’%’n2’, locate ‘r’ (reminder).
• Step 3: Return ‘n2’ if ‘r’ equals 0
• Step 4: If not, substitute ‘r’ for ‘n2’ and ‘n1’ for ‘n2’.
• Step 5: Go to Step 1

Code Implementation

#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 = 36, n2 = 60;

    printf("  The  HCF is : %d\n", hcf(n1, n2));

}

Output

The HCF is : 12

Time Complexity: O(log(min(n1,n2))
Space Complexity: O(1)

Conclusion
In conclusion, finding the HCF of two numbers in C programming is a fundamental concept that involves identifying the largest positive integer that divides both of them without leaving a remainder. This concept is used in various applications in mathematics and computer science, including simplifying fractions, reducing a polynomial to its lowest terms, and finding the ratio between two quantities.

Overall, understanding how to find the HCF of two numbers in C programming is an important skill for any programmer or student of computer science. It is a basic concept that forms the foundation for many advanced concepts in mathematics and computer science.

Frequently Asked Questions

Q1. What is the difference between HCF and LCM?
Ans. HCF (Highest Common Factor) of two numbers is the largest positive integer that divides both of them without leaving a remainder, while LCM (Lowest Common Multiple) is the smallest positive integer that is divisible by both of them.

Q2. Can the HCF of two numbers be zero?
Ans. No, the HCF of two numbers cannot be zero. The HCF is always a positive integer.

Q3. What is the HCF of two prime numbers?
Ans. The HCF of two prime numbers is always 1 since prime numbers have no common factors except for 1.

Q4. How do you find the HCF of two numbers using Euclid’s algorithm?
Ans. Euclid’s algorithm involves dividing the larger number by the smaller number and taking the remainder. Then, divide the smaller number by the remainder and take the remainder again. You continue this process until the remainder is zero, and the HCF is the last non-zero remainder.

Q5. Can the HCF of two numbers be greater than the smaller number?
Ans. No, the HCF of two numbers cannot be greater than the smaller number. The HCF is always a factor of both numbers, and all factors of a number are less than or equal to the number itself.