GCD via Euclid

The oldest algorithm in the book.

math recursion

Implement `gcd(a: int, b: int) -> int` using the Euclidean algorithm.

Return the largest integer that divides both a and b.

Constraints

1 ≤ a, b ≤ 10^12

Example

>>> gcd(48, 18)
6

10 points ~10 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

gcd(a, b) == gcd(b, a % b); base case: gcd(a, 0) == a.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.