# Greatest Common Divisor or Highest Common Factor

`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[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)
{
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

Last updated