C Program to Find HCF of Two Numbers

This C program finds the Highest Common Factor (HCF) of two given numbers using recursion.

Problem Statement

Write a C program that finds the Highest Common Factor (HCF) of two numbers using the Euclidean algorithm.

Input: The user is prompted to enter two integers, num1 and num2, representing the two numbers for which the HCF needs to be calculated.

Output: The program calculates the HCF using the Euclidean algorithm and prints the result, which is the HCF of the two input numbers.

Note:

The Euclidean algorithm is an efficient method for finding the HCF of two numbers. It repeatedly divides the larger number by the smaller number and updates the values until the remainder becomes zero. The HCF is the value of the last non-zero remainder obtained during this process.

C Program to Find HCF of Two Numbers

#include <stdio.h>

// Function to calculate HCF using the Euclidean algorithm
int calculateHCF(int num1, int num2) {
    int remainder;
    
    // Make sure num1 is always greater than or equal to num2
    if (num2 > num1) {
        int temp = num1;
        num1 = num2;
        num2 = temp;
    }
    
    // Calculate HCF using the Euclidean algorithm
    while (num2 != 0) {
        remainder = num1 % num2;
        num1 = num2;
        num2 = remainder;
    }
    
    return num1; // num1 holds the HCF
}

int main() {
    int num1, num2;
    
    printf("Enter the first number: ");
    scanf("%d", &num1);
    
    printf("Enter the second number: ");
    scanf("%d", &num2);
    
    // Call the calculateHCF function and store the result
    int hcf = calculateHCF(num1, num2);
    
    printf("The HCF of %d and %d is %d.\n", num1, num2, hcf);
    
    return 0;
}

How it Works

1. The program starts by including the necessary header file stdio.h for input/output operations.
2. The program defines a function calculateHCF that takes two integer arguments num1 and num2 and returns the HCF.
3. Inside the calculateHCF function, a variable remainder is declared to store the remainder of the division operation.
4. To simplify the calculation, the program checks if num2 is greater than num1. If so, it swaps the values of num1 and num2 using a temporary variable temp. This ensures that num1 is always greater than or equal to num2.
5. The Euclidean algorithm is then applied iteratively. It divides num1 by num2 and assigns the remainder to remainder. It updates num1 with the value of num2 and num2 with the value of remainder.
6. The algorithm continues this process until num2 becomes zero. At this point, num1 holds the HCF, which is returned by the calculateHCF function.
7. The program then defines the main function, which is the entry point of the program.
8. Inside the main function, two integer variables num1 and num2 are declared to store the user-input numbers.
9. The program prompts the user to enter the first number using the printf function and reads the input using the scanf function.
10. Similarly, the program prompts the user to enter the second number and reads the input.
11. The calculateHCF function is called with the user-provided numbers num1 and num2, and the returned HCF value is stored in the variable hcf.
12. Finally, the program uses the printf function to display the calculated HCF along with the input numbers.
13. The program ends by returning 0, indicating successful execution.

When you run the program, it prompts you to enter two numbers. It then calculates their HCF using the Euclidean algorithm and displays the result on the console.

Input /Output

In this case, the user inputs the numbers 81 and 153. The program calculates their HCF using the Euclidean algorithm, which gives a result of 9.