Home Tutorials Training Consulting Products Books Company Donate Contact us









NOW Hiring

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. About this website

4. Links and Literature

Not listed yet.

4.3. vogella GmbH training and consulting support

TRAINING SERVICE & SUPPORT

The vogella company provides comprehensive training and education services from experts in the areas of Eclipse RCP, Android, Git, Java, Gradle and Spring. We offer both public and inhouse training. Whichever course you decide to take, you are guaranteed to experience what many before you refer to as “The best IT class I have ever attended”.

The vogella company offers expert consulting services, development support and coaching. Our customers range from Fortune 100 corporations to individual developers.

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

See Licence.