Greatest Common Divisor

Given two integers, find their greatest common divisor.

If you don't know the Euclid algorithm, you should get to a piece of code like this:

static public int naive(int a, int b) {
    int result = 1;
    for (int i = 2; i <= Math.min(a, b); ++i) {
        if (a % i == 0 && b % i == 0) {
            result = i;
        }
    }
    return result;
}

This raw idea could be improved considering that it doesn't make any sense to check numbers bigger than the square root of the smaller one (beside itself), as well as the multiple of the already discarded numbers - if 2 is not a good candidate, there is no use in checking any even number.

However, Euclid devised such an elegant and fast converging algorithm that you should have a really good reason to explore alternatives.

Knowing that the gcd of a and b is the same as the gcd of a and a % b, we can write:

public static int euclid(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

To ensure I didn't make any silly mistake when writing my Java code, I have written a couple of simple JUnit test cases. Both files are now on GitHub.

Go to the full post