The Euclidean algorithm computes gcd(a, b) in O(log min(a, b)) time. Instead of listing divisors, it uses a simple observation: gcd(a, b) = gcd(b, a mod b).
Keep replacing the pair (a, b) with (b, a mod b) until b becomes 0. When b = 0, the answer is a.
Example: gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6. Three steps instead of 18.