Greatest common divisor

The GCD of two numbers is the largest integer that divides both. Euclid's algorithm is beautifully short: while b isn't 0, replace the pair (a, b) with (b, a % b). When b reaches 0, a is the answer.

Complete int gcd(int a, int b) to return the greatest common divisor of a and b. Euclid's method: repeatedly replace (a, b) with (b, a % b) until b is 0.

/* Greatest common divisor. Do not write main(). */
int gcd(int a, int b) {
    return 1;   /* change this */
}

Click Run to see the output here.

Next lesson →

Greatest common divisor

Greatest common divisor

Sign in

Log in or create account