Greatest Common Divisor

The GCD of two numbers is the largest integer that divides both. The Euclidean algorithm finds it in O(log min(a,b)) time.

Euclidean Algorithm

The insight: GCD(a, b) = GCD(b, a % b). Keep replacing (a, b) with (b, a % b) until b = 0. The answer is a.

Example: GCD(48, 18)
gcd(48, 18) → gcd(18, 48%18=12) → gcd(12, 18%12=6) → gcd(6, 12%6=0) → 6

C++

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

// or use the built-in:
int g = __gcd(a, b); // GCC/Clang
int g = gcd(a, b);   // C++17 <numeric>

Rust

fn gcd(mut a: u64, mut b: u64) -> u64 {
    while b != 0 {
        let temp = b;
        b = a % b;
        a = temp;
    }
    a
}

// or use the built-in:
let g = a.gcd(&b);  // from num::Integer

💡 Why it works

If d divides both a and b, then d also divides a % b = a − (a/b)×b. So the set of common divisors of (a, b) is the same as (b, a % b). Repeating shrinks the numbers exponentially.

Key Takeaways

→ Euclidean algorithm: GCD(a, b) = GCD(b, a % b).
→ Complexity: O(log min(a,b)).
→ Use built-in gcd (C++17) or write the loop yourself.

Euclidean Algorithm

C++

Rust

Key Takeaways

Practice