Greatest Common Divisor
The largest number that divides both. Euclid finds it in O(log n) steps.
Number Theory Basics: gcd(48, 18) by Euclid
The remainder hit 0, so the last non-zero value, 6, is the answer. gcd(48, 18) = 6 in 3 steps, and the numbers shrank fast: this is O(log n).
Cost
- Space
- O(1)
Leads to
Topics that need this one first.
Taught by the same lesson
Number Theory Basics covers these too, in the same run.