Greatest Common Divisor from a set of n integers

Math

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

Analysis & Solution

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

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);
}

如何从两个数的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
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;
}
int ans = arr;
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