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