Given an array of integers find the pair in the array with maximum GCD. Find the maximum possible GCD.
Example 1:
Input: N = 5, a[] = {1, 2, 3, 4, 5}
Output: 2
Explanation: Maximum gcd is GCD(2, 4)
= 2.
​Example 2:
Input: N = 3, a[] = {3, 5, 2}
Output: 1
Explanation: Maximum gcd is 1.
Your Task:
Your task is to complete the function MaxGcd() which takes the N and list of N elements as inputs and returns the answer.
Expected Time Complexity: O(N * log N)
Expected Auxiliary Space: O(max(a_{i}))
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ a_{i} ≤ 10^{5}

见题面

见题面