Algorithm – Euclidean

The Euclidean algorithm is based on the principle that the greatest common divisor (GCD) of two numbers does not change if the larger number is replaced by its difference with the smaller number.

This is repeated with successive smaller pairs of numbers until they both are equal, which in that case they both represent the GCD of the two original numbers.

In the following c++ code I show the signed version of the gcd which can be used for a subtraction based algorithm.

int gcd (int n1, int n2) {
     while (n1 != n2) {
        if (n1 > n2 ) {
        n1 −= n2;
        }
        else {
        n2 −= n1;
        }
    }
    return n1;
}