Why GCD and LCM Euclidean Algorithm in DSA Python?

The Big Idea

Discover a simple trick that turns a long, boring task into a quick, clever calculation!

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

For example, to find the GCD of 48 and 180, you try to write down all factors of both numbers and then find the biggest one they share.

The Problem

This manual method is slow and tiring, especially for big numbers. It's easy to miss factors or make mistakes when listing them. Also, it takes a lot of time and effort, which is frustrating.

The Solution

The Euclidean Algorithm uses a simple trick: instead of listing all factors, it repeatedly subtracts or uses remainders to find the GCD quickly. This method is fast, reliable, and works even for very large numbers.

Once you have the GCD, you can easily find the LCM using a simple formula.

Before vs After

✗ Before

def gcd_manual(a, b):
    factors_a = [i for i in range(1, a+1) if a % i == 0]
    factors_b = [i for i in range(1, b+1) if b % i == 0]
    common = [i for i in factors_a if i in factors_b]
    return max(common)

✓ After

def gcd_euclidean(a, b):
    while b != 0:
        a, b = b, a % b
    return a

What It Enables

This algorithm makes it easy and fast to find GCD and LCM, even for huge numbers, enabling efficient math calculations and problem solving.

Real Life Example

When you want to schedule events that repeat every few days, like watering plants every 6 days and fertilizing every 8 days, the LCM tells you when both tasks happen together again.

Key Takeaways

Manual factor listing is slow and error-prone.

Euclidean Algorithm uses remainders to find GCD quickly.

LCM can be found easily once GCD is known.