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

- The program starts by including the necessary header file
`stdio.h`

for input/output operations. - The program defines a function
`calculateHCF`

that takes two integer arguments`num1`

and`num2`

and returns the HCF. - Inside the
`calculateHCF`

function, a variable`remainder`

is declared to store the remainder of the division operation. - 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`

. - 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`

. - The algorithm continues this process until
`num2`

becomes zero. At this point,`num1`

holds the HCF, which is returned by the`calculateHCF`

function. - The program then defines the
`main`

function, which is the entry point of the program. - Inside the
`main`

function, two integer variables`num1`

and`num2`

are declared to store the user-input numbers. - The program prompts the user to enter the first number using the
`printf`

function and reads the input using the`scanf`

function. - Similarly, the program prompts the user to enter the second number and reads the input.
- The
`calculateHCF`

function is called with the user-provided numbers`num1`

and`num2`

, and the returned HCF value is stored in the variable`hcf`

. - Finally, the program uses the
`printf`

function to display the calculated HCF along with the input numbers. - 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.