algorithm - 为大数列表找到有效的公共最大公约数

Question

我有一项任务，我需要检查是否可以使用公约数来简化数字列表。

例如，如果我们有数字 12 48 36，它们都可以被 12 整除。我尝试过使用素数分解。但是，我拥有的一些数字非常大（比如 20 亿），并且很快找到所有可能的素数除数变得不可行。对于上面的素数分解的例子，效果很好：

12=2^2*3
48=2^4*3
36=2^2*3^2

我已经尝试为每一对运行 Eclidean 算法（https://en.wikipedia.org/wiki/Euclidean_algorithm）并取最小的数字，但我不确定这种方法是否有效，并且不会遇到结果的某些边缘情况有效的。

例子：

min(gcd(12,48), gcd(48,36), gcd(36,12))

所以我的问题是找到数字列表的最小公分母/除数的最有效的计算方法是什么，特别是如果数字往往很大？

标签： algorithmnumbersprimes