Greatest common divisor
Reducing a fraction, or laying tiles that divide a wall evenly, both come down to the same number.
- Signs do not matter: the divisor of -12 and 18 is the same as of 12 and 18.
- The divisor of 0 and n is n; of 0 and 0 it is 0.
greatestCommonDivisor(first: int, second: int) → int
C++ needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
int greatestCommonDivisor(int first, int second) {
}Worked examples
| Call | Result |
|---|---|
greatestCommonDivisor(12, 18) | 6 |
greatestCommonDivisor(17, 5) | 1 |
greatestCommonDivisor(0, 5) | 5 |
greatestCommonDivisor(0, 0) | 0 |
Hint
Euclid: keep replacing the pair with (second, first mod second) until the second is zero.
Reference solution in C++
int greatestCommonDivisor(int first, int second) {
int a = first < 0 ? -first : first, b = second < 0 ? -second : second;
while (b != 0) { int t = a % b; a = b; b = t; }
return a;
}