Tutorial

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.

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 then 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);
	}
}

		

Please help me to support this article:

Before posting questions, please see the vogella FAQ. If you have questions or find an error in this article please use the www.vogella.de Google Group. I have created a short list how to create good questions which might also help you.