Solution 1

The naive approach would be to brute-force each pair of numbers in the array and calculate the maximum GCD. Sadly, this solution gets TLE on around half of the test cases.

Implementation

Time Complexity: $\mathcal{O}(N^2\log(\max(x_i)))$

Copy
from math import gcd

n = int(input())

arr = list(map(int, input().split()))

ans = 1
for i in range(n - 1):
	for j in range(i + 1, n):
		ans = max(ans, gcd(arr[i], arr[j]))

print(ans)

Solution 2

Maintain an array, $\texttt{cnt}$, to store the count of divisors. For each value in the array, find its divisors and for each $u$ in those divisors, increment $\texttt{cnt}$ by one. The greatest GCD shared by two elements in the array will be the greatest index in our stored count for divisors with a count greater than or equal to $2$.

Implementation

Time Complexity: $\mathcal{O}(N\sqrt{\max(x_i)})$

Copy
from math import sqrt

MAX_VAL = 1000000
divisors = [0] * (MAX_VAL + 1)

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	up = int(sqrt(a[i]))
	for div in range(1, up + 1):

Solution 3

Given a value, $x$, we can check whether a pair has a GCD equal to $x$ by checking all the multiples of $x$. With that information, loop through all possible values of $x$ and check if it is a divisor to two or more values. This works in $\mathcal{O}(\max(x_i)\log(\max(x_i)))$ since

Implementation

Time Complexity: $\mathcal{O}(\max(x_i)\log(\max(x_i)))$

Copy
MAXX = int(1e6 + 5)
n = int(input())
arr = list(map(int, input().split()))
p = [0] * MAXX

for i in range(n):
	p[arr[i]] += 1

for i in range(MAXX, 0, -1):
	div = 0
	for j in range(i, MAXX, i):
		div += p[j]
	if div >= 2:
		print(i)
		break