Euclid’s GCD. This article describes how to calculate in Java the greatest common divisor of two positive number with Euclid’s algorithm.

1. Euclid’s Algorithm for the greatest common divisor

The greatest common divisor (gcd) of two positive integers is the largest integer that divides both without remainder. Euclid’s algorithm is based on the following property: if p>q then the gcd of p and q is the same as the gcd of p%q and q. p%q is the remainder of p which cannot be divided by q, e.g. 33 % 5 is 3. This is based on the fact that the gcd of p and q also must divided (p-q) or (p-2q) or (p-3q). Therefore you can subtract the maximum of a multitude q from p which is p%q.

2. Implementation in Java

Create a Java project "de.vogella.algorithms.euclid". Create the following program.

package de.vogella.algorithms.euclid;

/**
 * Calculates the greatest common divisor for two numbers.
 * <p>
 * Based on the fact that the gcd from p and q is the same as the gcd from p and
 * p % q in case p is larger than q
 *
 * @author Lars Vogel
 *
 */
public class GreatestCommonDivisor {
    public static int gcd(int p, int q) {
        if (q == 0) {
            return p;
        }
        return gcd(q, p % q);
    }

    // Test enable assert check via -ea as a VM argument

    public static void main(String[] args) {
        assert (gcd(4, 16) == 4);
        assert (gcd(16, 4) == 4);
        assert (gcd(15, 60) == 15);
        assert (gcd(15, 65) == 5);
        assert (gcd(1052, 52) == 4);
    }
}

3. Links and Literature

Nothing listed.

If you need more assistance we offer Online Training and Onsite training as well as consulting

See License for license information.