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
Last updated
Was this helpful?