## 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));
}
}
}
``````