Greatest Common Divisor or Highest Common Factor

Math

Write an algorithm to determine the GCD of N positive numbers.

Analysis & Solution

欧几里得算法求最大公约数

关于GCD算法，自然是有欧几里得算法Euclid Algorithm。不过实现上，可以是迭代，或者递归。

Pseudo Code:

Iterative

function gcd(a, b)
    while b ≠ 0
        t ← b
        b ← a mod b
        a ← t
    return a

Recursive:

function gcd(a, b)
    if b = 0
       return a
    else
       return gcd(b, a mod b)

Iterative (Java)

int gcd(int a, int b) {
        int tmp;
        while (b > 0) {
            tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

Recursive (Java)

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

Euclid Algorithm Time Complexity

这是一个挺复杂的数学问题，作为估计（也是实际上的），可以认为迭代次数O(logN)

如何从两个数的GCD拓展到N个数呢？

You could use this common property of a GCD:

GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) = GCD(GCD(a, c), b)

GeeksforGeeks:

gcd(a, b, c) = gcd(a, gcd(b, c)) 
             = gcd(gcd(a, b), c) 
             = gcd(gcd(a, c), b)

For an array of elements:

result = arr[0]
For i = 1 to n-1
   result = GCD(result, arr[i])

Implementation:

class GCD
{
    private int gcd(int a, int b) {
        int tmp;
        while (b > 0) {
            tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

    public int generalizedGCD(int num, int[] arr)
    {
        // WRITE YOUR CODE HERE
        if (num == 0 || arr == null) {
            return 0;
        } 
        if (num < 2) {
            return arr[0];
        }
        int ans = arr[0];
        for (int i = 1; i < num; i++) {
            ans = gcd(ans, arr[i]);
        }
        return ans;
    }

}

Reference

Greatest Common Divisor of a list of numbers - C++ and Python Implementation https://www.rookieslab.com/posts/cpp-python-code-to-find-gcd-of-a-list-of-numbers

https://www.geeksforgeeks.org/gcd-two-array-numbers/

Time complexity of Euclid's Algorithm https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm

欧几里得算法时间复杂度简单分析 https://blog.csdn.net/ZeroOnet/article/details/53375313