C Program to Find HCF of Two Numbers

Write a Program to Find the HCF of two numbers in C.

HCF (Highest Common Factor)

HCF stands for Highest Common Factor. HCF of two numbers is the largest positive integer that completely divides both the given numbers.

Example: HCF(10,15) = 15, HCF(12,15) = 3.

1. Take two numbers as input.
2. Find the greater of the two numbers.
3. Keep on dividing the greater number by the smaller number until remainder becomes 0.
4. When the remainder becomes 0 print the smaller number i.e., the denominator as the output.
5. Exit.

There are several ways to find the HCF of two numbers in C language. Let’s look at the five different approaches to write a C program to calculate the HCF of two numbers.

• HCF of Two Numbers in C using While Loop
• HCF of Two Numbers in C using For Loop
• HCF of Two Numbers in C using Recursion
• HCF of Two Numbers in C using Euclidean Algorithm
• HCF of Two Numbers in C using Recursive Euclidean Algorithm

In this approach, we find the HCF of two numbers using a while loop.

Here is the source code of the C program to find the HCF of two numbers using a while-loop. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C program to find the HCF of two integers using While-loop
 */
#include<stdio.h>
 
void main()
{
    int num1, num2, hcf, remainder, numerator, denominator;
 
    printf("Enter two numbers\n");
    scanf("%d %d", &num1, &num2);
    if (num1 > num2)
    {
        numerator = num1;
        denominator = num2;
    }
    else
    {
        numerator = num2;
        denominator = num1;
    }
    remainder = numerator % denominator;
    while (remainder != 0)
    {
        numerator   = denominator;
        denominator = remainder;
        remainder   = numerator % denominator;
    }
    hcf = denominator;
    printf("HCF of %d and %d = %d\n", num1, num2, hcf);
}

1. Take the two numbers num1 and num2 as input.
2. Store the greater number in the variable numerator and the smaller number in the variable denominator.
3. Run the while loop until the remainder becomes ‘0’. Inside the while loop keep on dividing the numerator by denominator and store the value in the remainder variable.
4. When the value of the remainder variable becomes ‘0’ come out of the loop and store the value of the denominator in the hcf variable.
5. Print the hcf.

Example:

• Consider, the two numbers 50 and 30, first find the greater of the two numbers and store the greater in the numerator and smaller in the denominator i.e., numerator=50 and denominator=30.
• Divide the numerator by the denominator and store the value in the remainder variable i.e., remainder = 50%30 = 20.
• Now, enter the while loop and check if the remainder value is ‘0’ or not.
• Now, assign the value of the denominator to the numerator and the value of the remainder to the numerator i.e., numerator=30 and denominator=20
• Divide the numerator by the denominator and store the value in the remainder variable i.e., remainder = 30%20 = 10.
• Now, enter the while loop and check if the remainder value is ‘0’ or not.
• Now, assign the value of the denominator to the numerator and the value of the remainder to the numerator i.e., numerator=20 and denominator=10
• Calculate the remainder of the two variables i.e., remainder = 20%10 = 0.
• Now, check the while loop condition again, this time remainder = 0, therefore come out of the loop and store the value of the denominator in hcf i.e., hcf = 10.
• Now, print hcf as 10.

Time Complexity: O(log(min(a,b)))
The above program for finding HCF of two numbers has a time complexity of O(log(min(a,b))), as the while loop runs for number of times the numerator is divided by the denominator.

Space Complexity: O(1)
In the above program, space complexity is O(1) as no extra variable has been taken to store the values in the memory. All the variables initialized takes a constant O(1) space.

Testcase 1: The numbers entered by the user to calculate hcf in this case are 12 and 15.

Enter two numbers
12 15
HCF of 12 and 15 = 3.

Testcase 2: The numbers entered by the user to calculate hcf are 50 and 30.

Enter two numbers
50 30
HCF of 50 and 30 = 10

In this approach, we find the HCF of two numbers using for-loop.

Here is the source code of the C program to find the HCF of two numbers using for loop. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C program to find the HCF of two integers using for-loop
 */
#include<stdio.h>
void main()
{
    int n1, n2, i, HCF;
 
    printf("Enter two integers: ");
    scanf("%d %d", &n1, &n2);
 
    int min = (n1 < n2)? n1:n2;  // to find minimum of the two numbers.
 
    for(i=min; i >=1; --i)
    {
        // Checks if i divides both the integers
        if(n1%i==0 && n2%i==0)
        {
            HCF = i;
            break;
        }
    }
 
    printf("HCF of %d and %d is %d", n1, n2, HCF);
}

1. Take the two integers n1 and n2 as input.
2. Store the minimum of the two integers in the variable min.
3. Run the for loop from i=min to i>=1 and decrease the value of i by 1 after each iteration.
4. Divide both the numbers n1 and n2 by i, if both gives remainder = 0 then store the value of i in HCF variable and break the for loop. (We are breaking the for loop because we are checking for HCF from the greatest number possible for HCF. So, the 1st greatest number that divides both the number completely is the HCF of the two numbers.)
5. Print the HCF.

Example:

• Consider the two numbers are n1=10 and n2=15.
• Find minimum of the two numbers and store it in the variable min i.e., min=10.
• Run the for loop from i = min to 1 and check if i divides both n1 and n2 completely.
• At the beginning i = 1, 10%10 gives the remainder as 0 but 15 %10 is 5 so, the if condition is false, decrement the value of i to 9 and again check the if condition.
• Repeat this step until if condition becomes true. Check for i=5, so 10%5=0 and 15%5=0 so, enter the if condition. Inside if statement assign the value of i to variable HCF.
• Now, break the condition i.e., come out of the for loop and print the value of HCF.
• Therefore, HCF of 10 and 15 is 5.

Time Complexity: O(min(n1,n2)))
The above program for finding HCF of two numbers has a time complexity of O(min(n1,n2)), as the for loop runs for minimum of number of times of n1 and n2.

Space Complexity: O(1)
In the above program, space complexity is O(1) as no extra variable has been taken to store the values in the memory. All the variables initialized takes a constant O(1) space.

Testcase 1: The numbers entered by the user to calculate HCF in this case are 10 and 15.

Enter the two numbers: 10 15
HCF of 10 and 15 is 5

Testcase 2: The numbers entered by the user to calculate HCF are 15 and 24.

Enter the two numbers: 15 24
HCF of 15 and 24 is 3

In this approach, hcf() function is used to find the HCF of two entered numbers using recursion.

Here is the source code of the C program to find the HCF of two numbers using recursion. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C Program to find HCF of given Numbers using Recursion
 */
#include<stdio.h>
 
int HCF(int, int);
 
int main()
{
    int a, b, result;
 
    printf("Enter the two numbers to find their HCF: ");
    scanf("%d%d", &a, &b);
    result = HCF(a, b);
    printf("The HCF of %d and %d is %d.\n", a, b, result);
}
 
int HCF(int a, int b)
{
    while (a != b)
    {
        if (a > b)
        {
            return HCF(a - b, b);
        }
        else
        {
            return HCF(a, b - a);
        }
    }
    return a;
}

In this C Program, we are reading the two integer numbers using ‘a’ and ‘b’ variable. The HCF() function is used to find the HCF of two entered integers using recursion.

While loop is used to check that both the ‘a’ and ‘b’ variable values are not equal. If the condition is true then execute the loop. Otherwise, return the value of ‘a’ variable. If else condition statement is used to check the value of ‘a’ variable is greater than the value of ‘b’ variable.

If the condition is true, then recursively call the HCF() function passing the values (a-b, b). Otherwise, if the condition is false, then recursively call the HCF() function passing the values (a, b-a). Run this until while loop condition becomes false and then return the value of ‘a’ as output.

Example:
Consider, the two numbers a and b are 15 and 20. Enter the HCF() function and check if both are equal or not. Since, 15! = 20 enter the while-loop. Inside the while-loop we see that a<b, therefore, enter the else statement and recursively call HCF function passing the values (a, b-a) i.e., (15,5).

Again, follow the same procedure as above. This time a>b, therefore, execute the if statement and call the function HCF() passing the values (a-b, b) i.e., (10,5).

Repeat the same process again. This time a>b, therefore, execute the if statement and call the function HCF() passing the values (a-b, b) i.e., (5,5).

Now, a=b, therefore do not enter the while loop and return the value of ‘a‘ i.e., 5 as HCF.

Time Complexity: O(log(min(a,b)))
The above program for finding HCF of two numbers has a time complexity of O(log(min(a,b))), as the while loop runs for number of times the lesser number is subtracted from the greater number until both becomes equal.

Space Complexity: O(log(min(a,b)))
In the above program, space complexity is O(log(min(a, b))) as the value of a and b gets stored in the memory until the recursive function gets terminated.

Testcase 1: In this case, the numbers entered by the user to calculate HCF using recursion are 15 and 20.

Enter the two numbers to find their HCF: 15 20
The HCF of 15 and 20 is 5.

Testcase 2: The numbers entered by the user to calculate HCF using recursion are 50 and 20.

Enter the two numbers to find their HCF: 50 20
The HCF of 50 and 20 is 10.

In this approach, we find the HCF of two numbers using Euclidean Algorithm.

Here is the source code of the C program to find the HCF of two numbers using Euclidean Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C Program to find HCF of two Numbers using Euclidean Algorithm
 */
#include<stdio.h>
 
int HCF(int x, int y) {
    int r = 0, a, b;
    a = (x > y) ? x : y; // a is greater number
    b = (x < y) ? x : y; // b is smaller number
 
    r = b;
    while (a % b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return r;
}
 
int main(int argc, char **argv) {
    printf("Enter the two numbers: ");
    int x, y;
    scanf("%d", &x);
    scanf("%d", &y);
    printf("The HCF of two numbers is: %d", HCF(x, y));
    return 0;
}

In this C Program, we are reading the two integer numbers using ‘x’ and ‘y’. The hcf() function is used to find the HCF of two entered integers without recursion.

This program is same as the “using while” program, the only difference is that we are implementing it using function.

The while loop terminates when a modulus b becomes 0, and r is returned back to the main function.

Example:
Consider, the two numbers 12 and 15, first find the greater of the two numbers and store the greater in the variable a and smaller in the variable b i.e., a=15 and b=12.

In the while loop check if a%b is not equal to 0. Since, 15%12 = 3 which is not equal to 0, enter the while loop. Store the value of a%b in the variable r i.e., r=3. Assign the value of b in a and r in b i.e., a=12 and b=3.

Now, again check the while loop, since 12%3=0 come out of the loop and return the value of r i.e., 3. In the main function print the value returned by r as HCF. Therefore, HCF of 15 and 12 is 3.

Time Complexity: O(log(min(a,b)))
The above program for finding HCF of two numbers has a time complexity of O(log(min(a,b))), as the while loop runs for number of times the a is divided by b.

Space Complexity: O(1)
In the above program, space complexity is O(1) as no extra variable has been taken to store the values in the memory. All the variables initialized takes a constant O(1) space.

Testcase 1: In this case, the numbers entered by the user to calculate HCF using the Euclidean algorithm are 12 and 15.

Enter the two numbers: 12 15
The HCF of two numbers is: 3

Testcase 2: The numbers entered by the user to calculate HCF using the Euclidean algorithm are 50 and 20.

Enter the two numbers: 50 20
The HCF of two numbers: 10

In this approach, we find the HCF of two numbers using Recursive Euclidean Algorithm.

Here is the source code of the C program to find the HCF of two numbers using Recursive Euclidean Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C Program to find HCF of two Numbers using Recursive Euclidean Algorithm
 */
#include<stdio.h>
 
int HCF_algorithm(int a, int b)
{
    int x = (a > b) ? a : b; // a is greater number
    int y = (a < b) ? a : b; // b is smaller number
 
    if (y == 0) {
        return x;
    } else {
        return HCF_algorithm(y, (x % y));
    }
}
 
int main()
{
    int num1, num2, HCF;
    printf("\nEnter two numbers to find HCF using Euclidean algorithm: ");
    scanf("%d%d", &num1, &num2);
    HCF = HCF_algorithm(num1, num2);
 
    printf("The HCF of %d and %d is %d\n", num1, num2, HCF);
    return 0;
}

In this C Program, we are reading the two integer numbers using ‘num1’ and ‘num2’. The HCF_algorithm() function is used to find the HCF of two entered integers using recursive Euclidean Algorithm.

Store the greater of the two numbers in variable x and smaller number in variable y. If y becomes 0 then return x else recursively call the HCF_algorithm() function with parameters (y,(x%y)). Repeat this process until y becomes 0.

Example:

• Consider the two numbers are 20 and 12. The greater number i.e., 20 is stored in x and the smaller number i.e., 12 is stored in y.
• Check the condition if y==0, since condition is false execute the else statement and recursively call the HCF_algorithm() function by passing the values as (y,(x%y)) i.e., (12,8).
• Now, repeat the same process. X=12 and y=8. As y is not equal to 0 again execute the else part and call the recursive function HCF_algorithm() by passing the values as (y,(x%y)) i.e., (8,4).
• In the next step again the same process will be followed and the values that will be returned to the function are (4,0).
• Now, x=4 and y=0. Check the if condition, this time the condition i.e., y==0 becomes true and hence x i.e., 4 is returned as HCF.
• In the main function print 4 as HCF.

Time Complexity: O(log(min(x,y)))
The above program for finding HCF of two numbers has a time complexity of O(log(min(x,y))), as the HCF_algorithm() function runs for minimum of number of times x is divided by y.

Space Complexity: O(log(min(x,y)))
In the above program, space complexity is O(log(min(x, y))) as the value of x and y gets stored in the memory until the recursive function gets terminated.

Testcase 1: In this case, the numbers entered by the user to calculate HCF using the Euclidean algorithm are 12 and 20.

Enter two numbers to find HCF using Euclidean algorithm: 12 20
The HCF of 12 and 20 is 4

Testcase 2: The numbers entered by the user to calculate HCF using Euclidean algorithm are 18 and 144.

Enter two numbers to find HCF using Euclidean algorithm: 18 144
The HCF of 18 and 144 is 18

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.