Understanding and Implementing HCF Calculation in C 🖥️

Finding the Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), of two numbers is a fundamental concept in mathematics. In this blog, we’ll explore how to compute the HCF using C programming with the help of the Euclidean algorithm. 📚

---

Introduction 🌟

The HCF of two integers is the largest positive integer that divides both numbers without leaving a remainder. It’s a handy concept used in fractions, ratios, and number theory.

In this blog, we’ll dive into a simple C program that calculates the HCF of two numbers. This program is based on the Euclidean algorithm, which is both efficient and elegant. 🚀

---

Program Code 👨‍💻

#include<stdio.h>
int main(){
    int a,b,r;
    printf("Enter two numbers : ");
    scanf("%d",&a);
    scanf("%d",&b);
    do{
        r=a%b;
        if(r!=0){
            a=b;
            b=r;
        }
    }while(r!=0);
    printf("HCF of two numbers is %d", b);
    return 0;
}

---

Explanation of the Logic 🧠

1. Input Prompt:

   • The program starts by asking the user to enter two integers. ✍️
   • Example: If the user inputs 36 and 60, these values are stored in the variables a and b respectively.

2. Euclidean Algorithm:

   • The algorithm repeatedly replaces the larger number with the remainder of dividing the larger number by the smaller number. 🔄
   • Let’s break it down for 36 and 60:
     • First iteration: r = 36 % 60 = 36. Update a = 60, b = 36.
     • Second iteration: r = 60 % 36 = 24. Update a = 36, b = 24.
     • Third iteration: r = 36 % 24 = 12. Update a = 24, b = 12.
     • Fourth iteration: r = 24 % 12 = 0. The loop stops here. ✅
   • The value of b (12 in this case) is the HCF. 🏆

3. Output:

   • The program displays the calculated HCF using a printf statement. 🖨️

---

Sample Output 📝

Here’s an example of the program in action:

Input:

Enter two numbers: 36 60

Output:

HCF of two numbers is 12

---

Conclusion 🎉

The program above demonstrates how to calculate the HCF of two numbers using the Euclidean algorithm. This method is simple, effective, and perfect for handling even large numbers. With this understanding, you can now incorporate HCF calculation into your own C programs for a variety of applications. 💡

Give it a try and experiment with different pairs of numbers to see the magic of the algorithm in action! ✨

---