Merge pull request TheAlgorithms#993 from shellhub/dev

yanglbme · web-flow · commit 993f30bc04ba · 2019-10-08T21:40:38.000+08:00
update gcd
diff --git a/Maths/GCD.java b/Maths/GCD.java
@@ -1,4 +1,4 @@
-package Others;
+package Maths;
 
 /**
  * This is Euclid's algorithm which is used to find the greatest common denominator
@@ -8,21 +8,36 @@
  */
 public class GCD {
 
+    /**
+     * get greatest common divisor
+     *
+     * @param num1 the first number
+     * @param num2 the second number
+     * @return gcd
+     */
     public static int gcd(int num1, int num2) {
+        if (num1 < 0 || num2 < 0) {
+            throw new ArithmeticException();
+        }
 
-        if (num1 == 0)
-            return num2;
-
-        while (num2 != 0) {
-            if (num1 > num2)
-                num1 -= num2;
-            else
-                num2 -= num1;
+        if (num1 == 0 || num2 == 0) {
+            return Math.abs(num1 - num2);
         }
 
-        return num1;
+        while (num1 % num2 != 0) {
+            int remainder = num1 % num2;
+            num1 = num2;
+            num2 = remainder;
+        }
+        return num2;
     }
 
+    /**
+     * get greatest common divisor in array
+     *
+     * @param number contains number
+     * @return gcd
+     */
     public static int gcd(int[] number) {
         int result = number[0];
         for (int i = 1; i < number.length; i++)
diff --git a/Maths/GCDRecursion.java b/Maths/GCDRecursion.java
@@ -0,0 +1,36 @@
+package Maths;
+
+/**
+ * @author https://github.com/shellhub/
+ */
+public class GCDRecursion {
+    public static void main(String[] args) {
+        System.out.println(gcd(20, 15)); /* output: 5 */
+        System.out.println(gcd(10, 8));  /* output: 2 */
+        System.out.println(gcd(gcd(10, 5), gcd(5, 10))); /* output: 5 */
+    }
+
+    /**
+     * get greatest common divisor
+     *
+     * @param a the first number
+     * @param b the second number
+     * @return gcd
+     */
+    public static int gcd(int a, int b) {
+
+        if (a < 0 || b < 0) {
+            throw new ArithmeticException();
+        }
+
+        if (a == 0 || b == 0) {
+            return Math.abs(a - b);
+        }
+
+        if (a % b == 0) {
+            return b;
+        } else {
+            return gcd(b, a % b);
+        }
+    }
+}
