# Find the Greatest Common Divisor in Java

## The challenge

Find the greatest common divisor of two positive integers. The integers can be large, so you need to find a clever solution.

The inputs `x`

and `y`

are always greater or equal to 1, so the greatest common divisor will always be an integer that is also greater or equal to 1.

## The solution in Java code

Option 1 (using `Euclidean Algorithm`

):

```
public class GCD {
public static int compute(int x, int y) {
return (x % y != 0) ? compute(y, x % y) : y;
}
}
```

Option 2 (using a `loop`

):

```
public class GCD {
public static int compute(int x, int y) {
int gcd = 0;
for(int i=1; i<= x && i<= y; i++){
if(x %i == 0 && y %i ==0){
gcd = i;
}
}
return gcd;
}
}
```

Option 3 (using `BigInteger`

):

```
import static java.math.BigInteger.valueOf;
import java.math.BigInteger;
public class GCD {
public static int compute(int x, int y) {
return valueOf(x).gcd(valueOf(y)).intValue();
}
}
```

## Test cases to validate our solution

```
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
public class GreatestCommonDivisorTest {
@Test
public void testGcd() {
assertEquals(6, GCD.compute(30,12));
assertEquals(1, GCD.compute(8,9));
assertEquals(1, GCD.compute(1,1));
}
@Test
public void testSomeLargerValues() {
for (int i=0;i<20;i++){
int x = randint(10000,100000);
int y = randint(100,1000);
int ans=my_gcd(x,y);
int x2 = randint(10000,100000);
int ans2=my_gcd(x2*y,x*y);
assertEquals("Testing GCD.compute("+ x +","+ y +")== "+ ans, ans, GCD.compute(x,y));
assertEquals("Testing GCD.compute("+ x2*y +","+ x*y +")== "+ ans2, ans2, GCD.compute(x2*y,x*y));
}
}
}
```