AlgoScope

Greatest Common Divisor

The largest number that divides both. Euclid finds it in O(log n) steps.

Mathematics, mathematics, beginnerAlso called GCD
The greatest common divisor of 48 and 18 is 6.4801811226304
The greatest common divisor of 48 and 18 is 6.4801811226304

Number Theory Basics: gcd(48, 18) by Euclid

Result, step 5 of 5

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.