Greatest common divisor

Challenge

Compute the greatest common divisor of two integers with Euclid's algorithm.

Task

Implement int gcd(int a, int b) that returns the largest integer dividing both a and b. Use the iterative method: repeatedly replace (a, b) with (b, a % b) until b is 0, then return a. By convention gcd(x, 0) == x. No main — the grader calls it.

Input

Two non-negative ints a and b.

Output

Returns their greatest common divisor, as an int.

Example

gcd(12, 8)   ->   4
gcd(17, 5)   ->   1
gcd(9, 0)    ->   9
gcd(0, 6)    ->   6

Edge cases

• gcd(x, 0) == x and gcd(0, y) == y.

Input format

Two non-negative ints a and b.

Output format

The greatest common divisor of a and b, as an int.

Constraints

Inputs non-negative; gcd(x, 0) == x.

Starter code

int gcd(int a, int b) {
    /* TODO */
    return 0;
}