Greatest common divisor
Reducing a fraction, or laying tiles that divide a wall evenly, both come down to the same number.
- Signs do not matter: the divisor of -12 and 18 is the same as of 12 and 18.
- The divisor of 0 and n is n; of 0 and 0 it is 0.
greatest_common_divisor(first: int, second: int) → int
Where you start
def greatest_common_divisor(first: int, second: int) -> int:
Worked examples
| Call | Result |
|---|---|
greatest_common_divisor(12, 18) | 6 |
greatest_common_divisor(17, 5) | 1 |
greatest_common_divisor(0, 5) | 5 |
greatest_common_divisor(0, 0) | 0 |
Hint
Euclid: keep replacing the pair with (second, first mod second) until the second is zero.
Reference solution in Python
def greatest_common_divisor(first: int, second: int) -> int:
a, b = abs(first), abs(second)
while b:
a, b = b, a % b
return a