Greatest common divisor

Challenge

Find the greatest common divisor of two non-negative integers using Euclid's algorithm.

Task

Implement int gcd(int a, int b) that returns the largest integer dividing both a and b. Use the iterative remainder method: repeatedly replace (a, b) with (b, a % b) until b is 0, then return a.

Input

Two non-negative ints a and b.

Output

Returns their greatest common divisor as an int. By convention, gcd(x, 0) is x.

Example

gcd(12, 8)   ->   4
gcd(13, 7)   ->   1
gcd(10, 0)   ->   10
gcd(6, 6)    ->   6

Edge cases

• When b is 0, the answer is a.
• Equal inputs return that value.

Why this matters

Euclid's algorithm is the oldest known nontrivial algorithm. It's the basis of modular arithmetic, RSA key generation, and many number-theoretic constructs.

Input format

Two non-negative ints a and b.

Output format

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

Constraints

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

Starter code

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

Common mistakes

Stopping when a == b (works but is inelegant — Euclid's is while (b) { ... }). Recursing without a base case for negative inputs. Using % on negative numbers (implementation-defined sign in older C).

Edge cases to handle

gcd(0, 0) = 0 (some define as undefined). gcd(n, 0) = n. gcd(0, n) = n.

Complexity

O(log min(a, b)) — Fibonacci-like number of iterations in the worst case.

Background lessons

• Loops: for / while / do-while
• Functions

Up next

• Integer power (iterative)
• Leap year check