Tìm cặp có UCLN lớn nhất trong mảng trong C++

Cho mảng số nguyên dương. Tìm cặp số có UCLN (GCD) lớn nhất. Ví dụ A = {1, 2, 3, 4, 5} → UCLN max = 2 (cặp (2,4)).

Cách làm: mảng đếm ước số. Với mỗi phần tử, tìm tất cả ước số (O(√arr[i])), tăng đếm. Sau đó duyệt mảng đếm từ lớn đến nhỏ, giá trị đầu tiên có đếm > 1 là UCLN lớn nhất.

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

Kết quả

Max GCD: 4