basics · beginner · ~15 min
Apply Euclid's algorithm; iterative remainder.
Implement int gcd(int a, int b) using Euclid's algorithm. Inputs are non-negative.
Euclid's algorithm is the oldest known nontrivial algorithm. It's the basis of modular arithmetic, RSA key generation, and many number-theoretic constructs.
int gcd(int a, int b) { /* TODO */ return 0; }
Stopping when a == b (works but is inelegant — Euclid's is while (b) { ... }). Recursing without a base case for negative inputs. Using % on negative numbers (implementation-defined sign in older C).
gcd(0, 0) = 0 (some define as undefined). gcd(n, 0) = n. gcd(0, n) = n.
O(log min(a, b)) — Fibonacci-like number of iterations in the worst case.
Solve this exercise in the browser editor — compile and run against the test harness, no setup required.