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

a and b are non-negative integers. Returns greatest common divisor.

Starter code

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

Common mistakes

Dividing by zero when b is 0 without checking loop condition.

Edge cases to handle

a == 0, b == 0, a == b, prime numbers.

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