在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

以上是 在C ++中查找数组中具有最大GCD的对 的全部内容, 来源链接: utcz.com/z/343306.html

回到顶部