Why GCD and LCM Euclidean Algorithm in DSA C?

The Big Idea

Discover how a simple remainder trick can replace hours of tedious factor checking!

The Scenario

Imagine you want to find the greatest common divisor (GCD) or least common multiple (LCM) of two large numbers by listing all their factors or multiples on paper.

This can take forever and is very tiring!

The Problem

Manually listing factors or multiples is slow and easy to make mistakes.

For big numbers, it becomes impossible to do quickly or accurately.

The Solution

The Euclidean Algorithm uses a simple, fast way to find the GCD by repeatedly subtracting or using remainders.

From the GCD, we can easily calculate the LCM without listing all multiples.

Before vs After

✗ Before

int gcd(int a, int b) {
  // list all factors of a and b
  // find the largest common one
  // very slow and complex
  return 1; // placeholder
}

✓ After

int gcd(int a, int b) {
  while (b != 0) {
    int temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

What It Enables

This algorithm lets us quickly find GCD and LCM even for very large numbers, enabling efficient math and problem solving.

Real Life Example

When scheduling events that repeat every few days, the LCM helps find when they coincide again, like two buses arriving together.

Key Takeaways

Manual factor listing is slow and error-prone.

Euclidean Algorithm uses remainders to find GCD fast.

LCM can be found easily from GCD, saving time and effort.