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`):

```.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```public class GCD {
public static int compute(int x, int y) {
return (x % y != ) ? compute(y, x % y) : y;
}
}
```Code language: Java (java)```

Option 2 (using a `loop`):

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

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();
}
}
```Code language: Java (java)```

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=;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));
}
}
}
```Code language: Java (java)```