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

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; } }
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=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)); } } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments