# Euclidean algorithm – Greatest Common Divisor(GCD)

The greatest common divisor (GCD) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 10 and 15 is 5. (Source – Wiki – http://en.wikipedia.org/wiki/Greatest_common_divisor).

Euclidean Algorithm : The greatest common divisor of two numbers remains the same if the larger number is replaced by its difference with the smaller number. If we keep repeat this process until one of the number becomes 0, then other number will be the GCD. We can solve this recursively.

Example:

```GCD of 282 and 156 will be the same as 156 and (282-156)=126.
GCD of 156 and 126 will be the same as 126 and (156-126) = 30
GCD of 126 and 30 will be the same as 18 and (126-30) = 96
GCD of 96 and 30 will be the same as 30 and (96-30) = 66
GCD of 66 and 30 will be the same as 30 and (66-30) = 36
GCD of 36 and 30 will be the same as 30 and (36-30) = 6
GCD of 6 and 30 will be the same as 6 and (30-6) = 24
GCD of 24 and 6 will be the same as 6 and (24-6) = 18
GCD of 6 and 18 will be the same as 6 and (18-6) = 12
GCD of 12 and 6 will be the same as 6 and (12-6) = 6
GCD of 6 and 6 will be the same as 6 and (6-6) = 0

one number becomes 0, other number 6 will be the GCD.
```

Complete Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 public class ElucidGCD { public static int findGCD(int number1, int number2) { // base case if (number2 == 0) { return number1; } return findGCD(number2, number1 % number2); } public static void main(String[] args) { System.out.println(findGCD(156, 282)); } }

view raw

ElucidGCD.java

hosted with ❤ by GitHub

Output:

``` 6
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.