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
public 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#
public int GreatestCommonDivisor(int first, int second) {
int a = Math.Abs(first), b = Math.Abs(second);
while (b != 0) { int t = a % b; a = b; b = t; }
return a;
}