GCD / HCF

The Greatest Common Divisor is the highest number that completely divides a group of numbers. Take 9 and 12: factors of 9 are 1, 3, 9; factors of 12 are 1, 2, 3, 4, 6, 12. The common factors are 1 and 3, so the GCD of 9 and 12 is 3.

Naive approach: loop from 1 to n, and at each step check if the loop index divides both numbers — if it does, that becomes the current GCD candidate.

static int printGcd(int n1, int n2){
    int gcd = 1; // we know for a fact that the gcd of two numbers will always be 1
    for (int i = 1; i < n1; i++){
        if (n1 % i == 0 && n2 % i == 0){
            gcd = i;
        }
    }
    return gcd;
}

This loops to n1, but if n1 were larger than n2, there’s no point checking values that can’t possibly divide the smaller number. So loop to Math.min(n1, n2) instead:

static int printGcd(int n1, int n2){
    int gcd = 1;
    for (int i = 1; i < Math.min(n1, n2); i++){
        if (n1 % i == 0 && n2 % i == 0){
            gcd = i;
        }
    }
    return gcd;
}

Even better: the Euclidean Algorithm solves this in far less time. It states that gcd(n1, n2) is equivalent to gcd(n1 - n2, n2) where n1 > n2. Keep applying it, shrinking the numbers, until one becomes 0 — the other number is the GCD.

gcd(n1, n2) -> gcd(n1-n2, n2)
gcd(20, 15) -> gcd(5, 15) // swap n1 with n2
gcd(15, 5) -> gcd(10, 5)
gcd(10, 5) -> gcd(5, 5)
gcd(5, 5) -> gcd(0, 5)

Now that we’ve reached (0, 5), the gcd of 20, 15 is 5.

There’s a catch: with a bigger gap like (52, 10), repeated subtraction takes a long time to converge. But notice that (2, 10) — the value you’d eventually reach via subtraction — is exactly the remainder of 52 / 10. So the algorithm can be improved: gcd(n1, n2) is equivalent to gcd(n1 % n2, n2) where n1 > n2. This skips straight past all the intermediate subtraction steps.

while (a > 0 && b > 0){
    if (a > b){
        a = a % b;
    } else{
        b = a % b;
    }
    if (a == 0){
        return b;
    } else{
        return a;
    }
}