Find the GCD of Two Numbers

📌 Definition:

📖 Detailed Explanation:

Use the Euclidean algorithm: gcd(a, b) = gcd(b, a % b), repeating until b is zero, at which point a is the GCD. This is far faster than trial division — O(log(min(a, b))). The LCM follows as a * b / gcd(a, b).

💻 Solutions:

• Java
• JavaScript
• Python

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

function gcd(a, b) {
  while (b !== 0) { [a, b] = [b, a % b]; }
  return a;
}

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

🔑 Key Points:

• Euclidean algorithm: gcd(a,b) = gcd(b, a%b)
• Base case: b == 0 -> return a
• O(log(min(a,b)))
• LCM = a*b / gcd

🌍 Real-World Example: