GCD of Two Numbers
EasyEuclid: replace the larger with the remainder
Problem
Return the greatest common divisor (largest number dividing both) of two integers a and b.
Keep replacing the bigger number with its remainder until one becomes zero.
The idea
gcd(a, b) equals gcd(b, a % b), because any number dividing both a and b also divides their remainder. Repeating that until b hits zero leaves the answer in a, and it converges in O(log min(a,b)) steps rather than the O(min(a,b)) of trial division.
The trick
- The loop ends when b == 0; a holds the gcd.
- lcm(a, b) = a / gcd(a, b) * b — divide first to avoid overflow.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — a = 12, b = 18 Values: 12, 18.
1while b != 0:2 (a, b) = (b, a % b)3return aInput
- array
- [12, 18]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- a = 12, b = 18
- Output:
- 6
- Explanation:
- 6 is the biggest number that divides both 12 and 18.
Example 2
- Input:
- a = 7, b = 5
- Output:
- 1
- Explanation:
- 7 and 5 share no factor except 1.
Example 3
- Input:
- a = 100, b = 40
- Output:
- 20
- Explanation:
- 20 divides both 100 and 40 evenly.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.