Home Tutorials Training Consulting Products Books Company Donate Contact us









Online training

Events

Quick links

Share

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.

4. vogella training and consulting support

Copyright © 2012-2018 vogella GmbH. Free use of the software examples is granted under the terms of the Eclipse Public License 2.0. This tutorial is published under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Germany license.