Euclidean GCD
The oldest named algorithm still in use: gcd(a, b) = gcd(b, a mod b), because any common divisor of a and b also divides their remainder. It shrinks fast.
- Category
- Mathematics
- Time complexity
- O(log min)
- Space complexity
- O(1)
Pseudocode
while b ≠ 0 (a, b) ← (b, a mod b) gcd is the last non-zero a
Reference implementation
def gcd(a, b):
while b:
a, b = b, a % b
return a