In this post we show how to implement **GCD** in **Java** using **Euclidean Algorithm**. **GCD** is known as **Greatest Common Divisor/Factor/Measure**, **Highest Common Divisor/Factor**.

**Greatest Common Divisor** of integers is the largest positive integer that divides the numbers without a reminder. There are many ways to calculate **GCD**, but in this post we’re going to implement **Euclidean Algorithm** in a few different ways. The **Euclidean algorithm** is know for about 2300 years and it’s still used today.

## How it works

**GCD(a, b)** works as follows:

- If
**b**is 0 then,**a**is**GCD**, because any number is divisor of 0 and the greatest divisor of**a**is**|a|**. - The result is
**GCD(b, a mod b)**, because the**greatest common divisor**doesn’t change when the larger number is replaced with it’s difference with the smaller number.

## Euclidean algorithm – recursively

Recursive version is the simplest implementation of **Euclidean algorithm**:

public int euclidRecursive(int a, int b) { return b == 0 ? Math.abs(a) : euclidRecursive(b, a % b); }

We use **Math.abs(a)**, because the numbers may be negative and we want to find positive integer.

## Euclidean algorithm – iterative version

Here’s the same algorithm, but written iteratively, which is usually preferred for languages without **Tail Call Optimization**:

public int euclidIterative(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return Math.abs(a); }

## GCD of many numbers

To calculate **GCD(a, b, c, …)** we have to recursively calculate **Greatest Common Divisor** for the first pair, then **GCD** for the result and the next number, and so on:

public int of(int a, int b, int... ints) { int gcd = euclidIterative(a, b); if (ints != null) { for (int i : ints) { gcd = euclidIterative(gcd, i); } } return Math.abs(gcd); }

## Unit tests

Here are sample JUnit tests to show that it all works:

package com.farenda.tutorials.algorithms.numbers; import org.junit.Test; import static org.junit.Assert.assertEquals; public class GCDTest { private GCD gcd = new GCD(); @Test public void gcdOfZeroAndNumberIsNumber() { assertEquals(42, gcd.euclidIterative(0, 42)); assertEquals(42, gcd.euclidRecursive(0, 42)); } @Test public void shouldCalculateGCDofTwoPositiveNumbers() { assertEquals(120, gcd.euclidIterative(1080, 1920)); assertEquals(120, gcd.euclidRecursive(1080, 1920)); assertEquals(120, gcd.euclidIterative(1920, 1080)); assertEquals(120, gcd.euclidRecursive(1920, 1080)); } @Test public void shouldCalculateForNegativeNumber() { assertEquals(3, gcd.euclidIterative(21, -9)); assertEquals(3, gcd.euclidRecursive(21, -9)); assertEquals(3, gcd.euclidIterative(-21, 9)); assertEquals(3, gcd.euclidRecursive(-21, 9)); assertEquals(3, gcd.euclidIterative(-21, -9)); assertEquals(3, gcd.euclidRecursive(-21, -9)); } @Test public void shouldCalculateForMultipleNumbers() { assertEquals(3, gcd.of(12, 6, -21, 33)); } }

## References:

- Check out other algorithms in Algorithms Tutorial