GCD Algorithm

The GCD (Greatest Common Divisor) Algorithm, also known as the Euclidean Algorithm, is a widely-used mathematical method for finding the greatest common divisor of two integers. This divisor is the largest positive integer that evenly divides both numbers without leaving a remainder. The GCD Algorithm is important in number theory, simplifying fractions, and solving Diophantine equations, among other applications. It is an efficient technique for computing the GCD, as it relies on the fundamental properties of integers and the divisibility of numbers. The GCD Algorithm works by repeatedly applying the modulo operation and replacing the given integers with the remainder until the remainder becomes zero. In its simplest form, the algorithm starts with two input numbers, a and b (with a ≥ b), and computes the remainder when a is divided by b. Then, it replaces a with b and b with the remainder, continuing this process until the remainder is zero. At this point, the greatest common divisor is the non-zero remainder obtained in the previous step. The efficiency of the GCD Algorithm arises from the fact that the numbers involved in the calculations rapidly decrease in size, resulting in fewer iterations and faster convergence to the solution.
package Maths;

/**
 * This is Euclid's algorithm which is used to find the greatest common denominator
 * Overide function name gcd
 *
 * @author Oskar Enmalm 3/10/17
 */
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 || num2 == 0) {
            return Math.abs(num1 - num2);
        }

        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++)
            // call gcd function (input two value)
            result = gcd(result, number[i]);

        return result;
    }

    public static void main(String[] args) {
        int[] myIntArray = {4, 16, 32};

        // call gcd function (input array)
        System.out.println(gcd(myIntArray)); // => 4
        System.out.printf("gcd(40,24)=%d gcd(24,40)=%d%n", gcd(40, 24), gcd(24, 40)); // => 8
    }
}

LANGUAGE:

DARK MODE: