C Exercises: Determine the HCF of two numbers

Last update on March 18 2025 13:34:34 (UTC/GMT +8 hours)

43. HCF (Highest Common Factor) Calculation

Write a C program to find the HCF (Highest Common Factor) of two numbers.

The task is to write a C program that calculates the Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), of two given numbers. The program should implement an algorithm, such as the Euclidean algorithm, to determine the largest number that evenly divides both input numbers.

Visual Presentation:

Sample Solution:

C Code:

#include <stdio.h> // Include the standard input/output header file.

void main()  
{  
    int i, n1, n2, j, hcf=1; // Declare variables to store input and results.

    printf("\n\n  HCF of two numbers:\n "); // Print a message.
    printf("----------------------\n"); // Print a separator.

    printf("Input 1st number for HCF: ");  // Prompt the user for input.
    scanf("%d", &n1);  // Read the first number from the user.
    printf("Input 2nd number for HCF: ");  // Prompt the user for input.
    scanf("%d", &n2);  // Read the second number from the user.

    j = (n1 < n2) ? n1 : n2;  // Determine the smaller of the two numbers. 

    // Loop to find the highest common factor (HCF).
    for(i = 1; i <= j; i++)  
    {  
        if(n1 % i == 0 && n2 % i == 0)  
        {  
            hcf = i;  // Update the HCF whenever a common factor is found.
        }  
    }  

    // Print the result.
    printf("\nHCF of %d and %d is : %d\n\n", n1, n2, hcf);  
}

Output:

  HCF of two numbers:                                                                                         
 ----------------------                                                                                       
Input 1st number for HCF: 24                                                                                  
Input 2nd number for HCF: 28                                                                                  
                                                                                                              
HCF of 24 and 28 is : 4

Flowchart:

For more Practice: Solve these Related Problems:

Write a C program to compute the HCF of two numbers using the recursive Euclidean algorithm.
Write a C program to calculate the HCF using iterative subtraction instead of division.
Write a C program to compute the HCF of two numbers employing bitwise operations for optimization.
Write a C program to compute the HCF of two numbers and then list all numbers that are coprime with both.

C Programming Code Editor:

Previous: Write a program in C to convert a binary number into a decimal number without using array, function and while loop.
Next: Write a program in C to find LCM of any two numbers using HCF.