The greatest common divisor (GCD) of two positive integers is the largest integer that divides both numbers without a remainder. It is also know as Greatest Common Factors (GCF), Greatest Common Measure (GCM), Highest Common Divisor (HCD), or Highest Common Factor (HCF).


The 'official' algorithm in full 32-bit ARM instruction set. Cortex-M4 is different.

gcd     cmp    r0, r1     ;if r0 > r1
        subgt  r0, r0, r1 ;subtract r1 from r0
        sublt  r1, r1, r0 ;else subtract r0 from r1
        bne    gcd        ;reached the end?

Only 4 lines! Let us see if a compiler can do that.

Enter the following code:

int gcd(int A, int B)
{
    while( A != B )
    {
        if( A > B )
            A -= B;
        else
            B -= A;
    }
    return B;
}