Tìm cặp có GCD tối đa trong một mảng trong C ++

Giả sử chúng ta có một mảng các số nguyên dương. Nhiệm vụ của chúng ta là tìm cặp số nguyên từ mảng, trong đó giá trị GCD là lớn nhất. Cho A ={1, 2, 3, 4, 5} thì kết quả là 2. Cặp (2, 4) có GCD 2, các giá trị GCD khác nhỏ hơn 2.

Để giải quyết vấn đề này, chúng ta sẽ duy trì một mảng đếm để lưu trữ số lượng ước của mỗi phần tử. Quá trình đếm số chia sẽ mất khoảng thời gian là O (sqrt (arr [i])). Sau khi duyệt toàn bộ, chúng ta có thể duyệt qua mảng đếm từ chỉ mục cuối cùng sang chỉ mục đầu tiên, sau đó nếu chúng ta tìm thấy giá trị nào đó trong đó phần tử lớn hơn 1, thì điều này có nghĩa là nó là ước của 2 phần tử và cũng là GCD tối đa.

Ví dụ

#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);
}

Đầu ra

Max GCD: 4