在C ++中查找数组中具有最大GCD的对
假设我们有一个正整数数组。我们的任务是从GCD值最大的数组中找到一对整数。令A={1,2,3,4,5}，则输出为2。对(2,4)的GCD为2，其他GCD值小于2。
为了解决这个问题，我们将维护一个count数组来存储每个元素的除数的数量。计算除数的过程将花费O（sqrt（arr[i]））时间。整个遍历之后，我们可以将count数组从最后一个索引遍历到第一个索引，然后如果找到某个元素大于1的值，则意味着它是2个元素的除数，也是最大GCD。
示例
#include <iostream>
#include <cmath>
using namespace std;
int getMaxGCD(int arr[], int n) {
int high = 0;
for (int i = 0; i < n; i++)
high = max(high, arr[i]);
int divisors[high + 1] = { 0 }; //array to store all gcd values
for (int i = 0; i < n; i++) {
for (int j = 1; j <= sqrt(arr[i]); j++) {
if (arr[i] % j == 0) {
divisors[j]++;
if (j != arr[i] / j)
divisors[arr[i] / j]++;
}
}
}
for (int i = high; i >= 1; i--)
if (divisors[i] > 1)
return i;
}
int main() {
int arr[] = { 1, 2, 4, 8, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Max GCD: " << getMaxGCD(arr,n);
}输出结果
Max GCD: 4