Max GCD Pair
- stored the frequency of the factors in map
- since we have to find the pairs, just evaluate which factor is maximum and occurring more than once.
Implementation
```cpp
int maxGCDPair(vector &arr, int n) {
map<int, int> mp;
for (const auto& x: arr) {
for (int i = 1; i <= sqrt(x); i++) {
if (x % i == 0) {
if (x/i == i) {
mp[i] ++;
}
else {
mp[i] ++;
mp[x/i] ++;
}
}
}
}
int mx = 0;
for (const auto& i: mp) {
int key = i.first;
int value = i.second;
if (value >= 2) mx = max(mx, key);
}
return mx;
}
```
</details>
- we will track if there exist some no. in the given range
- who has more then 2 factors in `a -> b`.
- if there is, that is our ans.
more optimized
```cpp
int maxGCDPair(vector &arr, int n) {
int a, b;
cin >> a >> b;
int ans = 1;
for (int i = 2; i <= 1e5; i++) {
int count = (b / i - (a - 1) / i);
if (count > 1)
ans = i;
}
cout << ans << '\n';
}
```
</details>