สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มบวก งานของเราคือค้นหาคู่ของจำนวนเต็มจากอาร์เรย์ โดยที่ค่า 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
