Euclidean Algorithm
Replace (a, b) with (b, a mod b) until b is 0. The last non-zero value is the gcd.
Number Theory Basics: gcd(48, 18) by Euclid
48 mod 18 = 12. Any divisor of 48 and 18 divides 12 too, so the pair becomes (18, 12).
Cost
- Best
- O(1)
- Average
- O(log min(a, b))
- Worst
- O(log min(a, b))
- Space
- O(1)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Number Theory Basics covers these too, in the same run.