Micro-Drill #78 — GCD (Euclidean)

Divide & Conquer Target: 10s

Euclidean GCD runs in O(log min(a,b)). Foundation for fraction simplification and LCM.

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

Type it from memory. Go.