C++の配列で最大GCDのペアを検索します

正の整数の配列があるとします。私たちのタスクは、GCD値が最大である配列から整数のペアを見つけることです。 A ={1、2、3、4、5}とすると、出力は2になります。ペア（2、4）にはGCD 2があり、他のGCD値は2未満です。

この問題を解決するために、各要素の除数の数を格納するためのカウント配列を維持します。除数を数えるプロセスには、O（sqrt（arr [i]））の時間がかかります。全体をトラバースした後、最後のインデックスから最初のインデックスまでカウント配列をトラバースできます。要素が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