8️⃣C Program to Find GCD of Two Numbers

 

✅ C Program to Find GCD of Two Numbers

📌 What is GCD?

GCD (Greatest Common Divisor) is the largest positive number that divides two numbers without leaving a remainder.

🔹 Example:

• Numbers: 24 and 36

• Common divisors: 1, 2, 3, 4, 6, 12

• Greatest among them = 12

👉 So, GCD of 24 and 36 is 12

---

🧠 Method Used: Euclidean Algorithm

The Euclidean Algorithm is the most efficient way to find GCD.

Rule:

GCD(a, b) = GCD(b, a % b)

Repeat until b becomes 0.
The remaining value of a is the GCD.

---

💻 C Program to Find GCD of Two Numbers

#include <stdio.h>

int main() {
    int a, b, temp;

    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);

    while (b != 0) {
        temp = b;
        b = a % b;
        a = temp;
    }

    printf("GCD is: %d", a);

    return 0;
}

---

🧪 Example Output

Input:

Enter two numbers: 24 36

Output:

GCD is: 12

---

🔍 Step-by-Step Explanation

Let input be:

a = 24, b = 36

Step	a	b	a % b
1	24	36	24
2	36	24	12
3	24	12	0

When b = 0,
➡ a = 12 → This is the GCD

---

🧩 Explanation of Code

• scanf() → Takes two numbers from user

• while (b != 0) → Loop runs until remainder becomes 0

• a % b → Finds remainder

• temp → Stores value to swap numbers

• Final value of a → GCD   

✅ Conclusion

In this program, we learned how to calculate the GCD of a Number in C.
📘 C Programming Series – What’s Next?
👉 In the next post of this series, we will learn how to Find LCM of Two Numbers with complete explanation and output examples. Stay tuned! 🚀