我们有一些非负数。我们希望找到最大gcd对。实际上这个最大值比这对更重要！ 例如，如果我们有：
2 4 5 15
GCD（2,4）= 2
GCD（2,5）= 1
GCD（2,15）= 1
GCD（4,5）= 1
GCD（4,15）= 1
GCD（5,15）= 5
答案是5。
我们有一些非负数。我们希望找到最大gcd对。实际上这个最大值比这对更重要！ 例如，如果我们有：
2 4 5 15
GCD（2,4）= 2
GCD（2,5）= 1
GCD（2,15）= 1
GCD（4,5）= 1
GCD（4,15）= 1
GCD（5,15）= 5
答案是5。
有一个解决方案需要O（n）：
让我们的数字 a_i。首先，计算 m=a_0*a_1*a_2*...。对于每个数字a_i，计算 gcd(m/a_i, a_i)。您要查找的数字是这些值的最大值。
我没有证明这一直是真的，但在你的例子中，它有效：
m=2*4*5*15=600,
max(gcd(m/2,2), gcd(m/4,4), gcd(m/5,5), gcd(m/15,15))=max(2, 2, 5, 5)=5
注意：这是不正确的。如果是这个号码 a_i 有一个因素 p_j 重复两次，如果另外两个数字也包含这个因素， p_j，那么你得到的结果不正确 p_j^2 绝对的 p_j。例如，对于集合 3, 5, 15, 25， 你得到 25 作为答案而不是 5。
但是，您仍然可以使用它来快速过滤掉数字。例如，在上述情况下，一旦确定25，就可以先进行详尽的搜索 a_3=25 同 gcd(a_3, a_i) 找到真正的最大值， 5，然后过滤掉 gcd(m/a_i, a_i), i!=3 小于或等于 5 （在上面的示例中，这会过滤掉所有其他内容）。
添加了澄清和理由：
要了解为什么这应该有效，请注意 gcd(a_i, a_j) 分歧 gcd(m/a_i, a_i) 对全部 j!=i。
我们打电话吧 gcd(m/a_i, a_i) 如 g_i，和 max(gcd(a_i, a_j),j=1..n, j!=i) 如 r_i。我上面说的是 g_i=x_i*r_i，和 x_i 是一个整数。很明显 r_i <= g_i，所以 n gcd操作，我们得到一个上限 r_i 对全部 i。
上述说法不是很明显。让我们更深入地研究一下为什么它是真的：gcd of a_i 和 a_j 是两者中出现的所有主要因素的产物 a_i 和 a_j （根据定义）。现在，成倍增加 a_j 用另一个数字， b。的gcd a_i 和 b*a_j 要么等于 gcd(a_i, a_j)，或者是它的倍数，因为 b*a_j 包含所有主要因素 a_j，以及一些更多的主要因素 b，也可以包括在分解中 a_i。事实上， gcd(a_i, b*a_j)=gcd(a_i/gcd(a_i, a_j), b)*gcd(a_i, a_j)， 我认为。但我看不出有办法利用这个。 :)
无论如何，在我们的建设中， m/a_i 只是计算所有产品的捷径 a_j，哪里 j=1..1, j!=i。结果是， gcd(m/a_i, a_i) 包含所有 gcd(a_i, a_j) 作为一个因素。因此，显然，这些个别gcd结果的最大值将会分开 g_i。
现在，最大的 g_i 我们特别感兴趣：它是最大的gcd本身（如果 x_i 是1），或是一个很好的候选人。为此，我们做另一件事 n-1 gcd操作，并计算 r_i 明确。然后，我们放弃所有 g_j 小于或等于 r_i 作为候选人。如果我们没有剩下任何其他候选人，我们就完成了。如果没有，我们会选择下一个最大的 g_k，并计算 r_k。如果 r_k <= r_i，我们放弃 g_k，并与另一个重复 g_k'。如果 r_k > r_i，我们过滤掉剩余的 g_j <= r_k，并重复。
我认为有可能构造一个数字集，使这个算法在O（n ^ 2）中运行（如果我们没有过滤掉任何东西），但在随机数集上，我认为它将很快摆脱大块的候选人。
您可以使用欧几里德算法来查找两个数字的GCD。
while (b != 0)
{
int m = a % b;
a = b;
b = m;
}
return a;
如果你想要替代明显的算法，那么假设你的数字在有界范围内，并且你有足够的内存，你可以超过O（N ^ 2）时间，N是值的数量：
这告诉你最大gcd，但不告诉你哪一对产生了它。对于您的示例输入，计算出的数组如下所示：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
4 2 1 1 2 0 0 0 0 0 0 0 0 0 1
我不知道这对你必须处理的输入来说是否真的更快。涉及的常数因素很大：您的值的界限以及在该界限内分解值的时间。
您不必将每个值分解 - 您可以使用memoisation和/或预生成的素数列表。这给了我一个想法，如果你记住因子分解，你不需要数组：
虽然它取决于您使用的数据结构，但在集合中添加/查找可能是O（日志N）。每个值都有O（f（k））因子，其中k是最大值，我不记得函数f是什么...
在集合中遇到值时，您完成值的原因是您找到了一个数字，它是两个输入值的公因子。如果你保持因子分解，你只能找到较小的这样的数字，这些数字并不有意思。
我不太清楚重复更大因素的最佳方法是什么。我认为在实践中你可能需要取得平衡：你不想按降序顺序完成它们，因为生成有序因子很尴尬，但你也不想真正找到所有因素。
即使在O（N ^ 2）的领域，你也许能够击败欧几里德算法的使用：
将每个数字完全分解，将其存储为素数的指数序列（例如，2为{1}，4为{2}，5为{0,0,1}，15为{0,1,1}} 。然后你可以通过获取每个索引的最小值并将它们相乘来计算gcd（a，b）。不知道这是否比欧几里德平均快，但可能是。显然它使用了更多的内存。
我能想到的优化是
1）从两个最大的数字开始，因为它们可能具有最多的素数因子，因此可能具有最共享的素数因子（因此是最高的GCD）。
2）当计算其他对的GCD时，如果低于当前最大GCD，则可以停止欧几里德算法循环。
在我的脑海中，我无法想到一种方法，你可以计算出一对中最大的GCD，而不是试图单独计算每一对（并如上所述进行优化）。
免责声明：我以前从未考虑过这个问题，而且上面的内容已经脱离了我的脑海。可能有更好的方法，我可能是错的。如果有人想要，我很乐意更详细地讨论我的想法。 :)
没有 O(n log n) 一般来说解决这个问题。事实上，最糟糕的情况是 O(n^2) 在列表中的项目数。考虑以下一组数字：
2^20 3^13 5^9 7^2*11^4 7^4*11^3
只有最后两个的GCD大于1，但从查看GCD知道这一点的唯一方法是尝试每一对并注意其中一个大于1。
因此，当你已经找到一个大的GCD（同时确保你不会错过任何东西）时，你可能会坚持使用无聊的暴力尝试每对方法，或者进行一些巧妙的优化以避免做不必要的工作）。
对于某些约束，例如数组中的数字在给定范围内，比如1-1e7，它在O（NlogN）/ O（MAX * logMAX）中是可行的，其中MAX是A中的最大可能值。
灵感来自筛选算法，并在一个 Hackerrank挑战赛 - 在那里完成了两个阵列。检查他们的社论。
上一个答案： 仍为O（N ^ 2） - 对数组进行排序;应该消除一些不必要的比较;
max_gcd = 1
# assuming you want pairs of distinct elements.
sort(a) # assume in place
for ii = n - 1: -1 : 0 do
if a[ii] <= max_gcd
break
for jj = ii - 1 : -1 :0 do
if a[jj] <= max_gcd
break
current_gcd = GCD(a[ii], a[jj])
if current_gcd > max_gcd:
max_gcd = current_gcd
这应该节省一些不必要的计算。
伪代码
function getGcdMax(array[])
arrayUB=upperbound(array)
if (arrayUB<1)
error
pointerA=0
pointerB=1
gcdMax=0
do
gcdMax=MAX(gcdMax,gcd(array[pointera],array[pointerb]))
pointerB++
if (pointerB>arrayUB)
pointerA++
pointerB=pointerA+1
until (pointerB>arrayUB)
return gcdMax