Problem:
 Score : 300 points    Problem Statement There are N integers, A_1, A_2, ..., A_N , written on the blackboard.  You will choose one of them and replace it with an integer of your choice between 1 and 10^9 (inclusive), possibly the same as the integer originally written.  Find the maximum possible greatest common divisor of the N integers on the blackboard after your move.      Constraints  All values in input are integers.  2 \leq N \leq 10^5  1 \leq A_i \leq 10^9       Output Input is given from Standard Input in the following format:  N  A_1  A_2  ...  A_N       Output Print the maximum possible greatest common divisor of the N integers on the blackboard after your move.       Sample Input 1 3
7 6 8      Sample Output 1 2  If we replace 7 with 4 , the greatest common divisor of the three integers on the blackboard will be 2 , which is the maximum possible value.       Sample Input 2 3
12 15 18      Sample Output 2 6       Sample Input 3 2
1000000000 1000000000      Sample Output 3 1000000000  We can replace an integer with itself.

Solution (Python):

import sys
import math
from collections import Counter
import collections
INF = float("inf")


def factorial(n):
    
    prime_count = collections.Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def GCD(a, b):
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


def GCDs(*a):
    
    if len(a) == 0:
        return -1  

    if len(a) == 1:
        return a[0]

    res = a[0]
    for i in range(1, len(a)):
        res = GCD(res, a[i])
    return res


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors


def solve(N: int, A: "List[int]"):
    c1 = make_divisors(A[0])
    c2 = make_divisors(A[1])
    c = sorted(list(set(c1 + c2)))

    OKs = []
    for cv in c:
        if sum([1 if a % cv == 0 else 0 for a in A]) >= N-1:
            OKs.append(cv)
    print(max(OKs))

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, A)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = sorted(list(map(int, input().split())))

if N == 2:
  print(max(A))
  exit()
  

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    divisors.reverse()
    return divisors
rawcdivisors = set(make_divisors(A[0]))|set(make_divisors(A[1]))|set(make_divisors(A[2]))



cnum = A[1]

cdivisors = set(list(rawcdivisors))

for divnum in list(rawcdivisors):
  if divnum > cnum: cdivisors.remove(divnum)

ans = 0
for i in sorted(list(cdivisors),reverse=True): 
  ngcnt = 0 
  for a in A:

    if a % i != 0: 
      ngcnt += 1
      if ngcnt >= 2: break 
  if ngcnt >= 2: continue 
  else:
    ans = i 
    break
  
  
print(ans)

Solution (Python):
import fractions

n = int(input())
a = list(map(int, input().split()))
gcd_0 = fractions.gcd(a[0],a[1])
gcd_1 = min(a[0], a[1])
for i in range(2,n):
    gcd_1 = max(gcd_0, fractions.gcd(gcd_1, a[i]))
    gcd_0 = fractions.gcd(gcd_0, a[i])

gcd_0 = fractions.gcd(a[0],a[1])
gcd_2 = max(a[0], a[1])
for i in range(2,n):
    gcd_2 = max(gcd_0, fractions.gcd(gcd_2, a[i]))
    gcd_0 = fractions.gcd(gcd_0, a[i])
    
print(max(gcd_2,gcd_1))

Solution (Python):
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
A = IL()

A.sort()
ABS = []
for i in range(1,N):
    ABS.append(A[i]-A[i-1])

ABS.sort()
num = A[1]
cnt = 0
for i in range(num+1,0,-1):
    cnt = 0
    for j in range(N):
        if A[j]%i==0:
            continue
        else:
            cnt += 1
        if cnt == 2:
            break
    else:
        print(i)
        exit()

Solution (Python):


import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

cache = {}


def gcd(a, b):
    if a not in cache:
        cache[a] = {}
    if b in cache[a]:
        return cache[a][b]
    if b == 0:
        cache[a][b] = a
        return a
    n = gcd(b, a % b)
    cache[a][b] = n
    return n

def main_lte(N, An):
    if N == 2:
        n = max(An[0], An[1])
        print(n)
        return
    nn = [An[0]] * N
    nn[0] = An[1]
    for i in range(1, N):
        for j in range(N):
            if i == j:
                continue
            nn[j] = gcd(nn[j], An[i])
    print(int(max(nn)))

def main(N, An):
    if N == 2:
        n = max(An[0], An[1])
        print(n)
        return
    nn0 = gcd(An[0], An[1])
    nn1 = set((An[0], An[1]))
    for i in range(2, N):
        t1 = nn0
        nn0 = gcd(nn0, An[i])
        t2 = [gcd(n, An[i]) for n in nn1]
        nn1 = set(t2)
        nn1.add(t1)
    n = max(nn1)
    print(int(n))

N = i2n()
An = i2nn()
main(N, An)

Solution (Python):

import numpy as np
N = int(input())
As=input().split()
A = np.array([int(s) for s in As])
del(As)

min2A = A[A.argsort()[1]]
minA = np.amin(A)
if np.sum((A%min2A)==0)>=N-1:
    print(min2A)
elif np.sum((A%minA)==0)>=N-1:
    print(minA)
else:
    for i in range(2,min2A+1):
        if (min2A%i == 0) or (minA%i == 0):
            if(min2A%i == 0):
                j = int(min2A/i)
            elif(minA%i == 0):
                j=int(minA/i)
            if np.sum((A%j)==0)>=N-1:
                print(j)
                break

Solution (Python):

def gcd(x,y):
  while y:
    x,y=y,x%y
  return x


class struct:
  def __init__(self,a,b,c):
    self.a=a
    self.b=b
    self.c=c

n=int(input())
if n==2:
  a,b=map(int,input().split())
  print(max(a,b))
  exit()
elif n==3:
  a,b,c=map(int,input().split())
  print(max(gcd(a,b),gcd(a,c),gcd(b,c)))
  exit()
else:
  l=list(map(int,input().split()))
  a=l[0]
  b=l[1]
  c=l[2]
  d=l[3]
  l2=[]
  l2.append(struct(a,b,gcd(a,b)))
  l2.append(struct(a,c,gcd(a,c)))
  l2.append(struct(a,d,gcd(a,d)))
  l2.append(struct(b,c,gcd(b,c)))
  l2.append(struct(b,d,gcd(b,d)))
  l2.append(struct(c,d,gcd(c,d)))
  l2=sorted(l2,key=lambda x:(x.c,x.a,x.b))
  l3=[l2[0].a,l2[0].b,l2[1].a,l2[1].b]
  jama=10000000000000000
  if l3.count(l3[0])>1:
    jama=l3[0]
  if l3.count(l3[1])>1:
    jama=l3[1]
  if l3.count(l3[2])>1:
    jama=l3[2]
  if l3.count(l3[3])>1:
    jama=l3[3]
  mein=100000000000000000
  if jama==a:
    mein=gcd(gcd(b,c),d)
  if jama==b:
    mein=gcd(gcd(a,c),d)
  if jama==c:
    mein=gcd(gcd(a,c),d)
  if jama==d:
    mein=gcd(gcd(b,c),a)
  for x in l[4:]:
    xx=gcd(mein,x)
    yy=gcd(mein,jama)
    if xx<yy:
      jama=x
      mein=yy
    else:
      mein=xx
  print(mein)

Solution (Python):
import sys
from functools import reduce
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def gcd_list(numbers):
    return reduce(gcd, numbers)
n = ni()
a = nl()
if len(a) == 2:
    print(max(a))
    exit()
minn = 10 ** 9 + 1
idx = -1
for i in range(n - 2):
    if minn >= gcd_list([a[i], a[i + 1], a[i + 2]]):
        minn = gcd_list([a[i], a[i + 1], a[i + 2]])
        idx = i
gcd1 = 0
gcd2 = 0
gcd3 = 0
for i in range(n):
    if i != idx:
        gcd1 = gcd(gcd1, a[i])
    if i != idx + 1:
        gcd2 = gcd(gcd2, a[i])
    if i != idx + 2:
        gcd3 = gcd(gcd3, a[i])
print(max(gcd1, gcd2, gcd3))

Solution (Python):
N = int(input()) 
def gcd(m, n):
  a = max(m,n)
  b = min(m,n)
  if a%b==0:
    return b
  while not a % b == 0:
      a, b = b, a % b
  return b

arr = [int(item) for item in input().split()]
a = [arr[0]]
b = [arr[-1]]
for i in range(1, N):
  a.append(gcd(a[i-1], arr[i]))
  b.append(gcd(b[i-1], arr[N-i-1]))
ans = max(a[-2], b[-2])
b = b[::-1]
for i, j in zip(a[:-2], b[2:]):
  ans = max(ans, gcd(i,j))
print(ans)

Solution (Python):

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    numdct = {}
    for i in range(2):
        for div in make_divisors(a[i]):
            if(not div in numdct):
                numdct[div] = 0
            numdct[div] += 1

    dellist = []
    for i in range(2, n):
        for num in numdct.keys():
            if(a[i] % num != 0):
                numdct[num] -= 1
                if(numdct[num] == 0):
                    dellist.append(num)
        for d in dellist:
            del numdct[d]
        dellist.clear()
    
    numlist = sorted(numdct.items(), key=lambda x: -x[1])

    maxnum = 0
    for item in numlist:
        if(item[1] > 0):
            if(maxnum <= item[0]):
                maxnum = item[0]
        else:
            break

    print(maxnum)

Solution (Python):
from fractions import gcd

N = int(input())
A = [int(i) for i in input().split(" ")]

if N == 2:
    print(max(A))
    import sys
    sys.exit()

g = gcd(A[0], A[1])
lmax = 1
num = 0
for i in range(2,N):
    cand = gcd(g, A[i])
    if cand < g:
        l = int(g / cand)
        g = cand
        if lmax < l:
            lmax = l
            num = A[i]
A = A[1:] + [A[0]]
g = gcd(A[0], A[1])
for i in range(2,N):
    cand = gcd(g, A[i])
    if cand < g:
        l = int(g / cand)
        g = cand
        if lmax < l:
            lmax = l
            num = A[i]
A = A[1:] + [A[0]]
g = gcd(A[0], A[1])
for i in range(2,N):
    cand = gcd(g, A[i])
    if cand < g:
        l = int(g / cand)
        g = cand
        if lmax < l:
            lmax = l
            num = A[i]
if num == A[0]:
    A = A[1:]
    flag = False
    N -= 1
elif num == A[1]:
    A = [A[0]] + A[2:]
    flag = False
    N -= 1
else:
    flag = True
g = gcd(A[0], A[1])
for i in range(2,N):
    if A[i] == num and flag:
        flag = False
    else:
        g = gcd(g, A[i])
print(g)

Solution (Python):
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
gcdL = [0] * N
gcdR = [0] * N

gcdL[0] = A[0]
gcdR[-1] = A[-1]

if N == 2:
    print(max(A))
    exit()


for i in range(1, N):
    gcdL[i] = gcd(gcdL[i-1], A[i])
for i in range(1, N):
    gcdR[-i-1] = gcd(gcdR[-i], A[-i-1])

ans = gcdR[1]  

for i in range(1, N-1):
    tmp = gcd(gcdL[i-1], gcdR[i+1])
    
    ans = max(tmp, ans)
ans = max(ans, gcdL[-2])

print(ans)

Solution (Python):
def gcd(a,b):
  while b:a,b=b,a%b
  return a
n,a,b=int(input()),list(map(int,input().split())),[]
if n==2:print(max(a[0],a[1]))
elif n==3:print(max(gcd(a[0],a[1]),gcd(a[0],a[2]),gcd(a[1],a[2])))
else:
  no,mi=a[0],a[0]
  for i in range(1,n):
    s=gcd(no,a[i])
    if s!=no:
      no=max(s,mi)
      mi=gcd(s,mi)
  print(no)

Solution (Python):
import fractions as f

N = int(input())
A = [int(x) for x in input().split()]

if N == 2:
    print(max(A))
else:
    A = sorted(A)
    l1,l2 = [],[]
    c1,c2 = 0,0
    for i in range(1,N):
        a = f.gcd(A[0],A[i])
        l1 += [a]
        if a == 1:
            c1 += 1
            if c1 >= 2:
                break
    for j in range(2,N):
        a = f.gcd(A[1],A[j])
        l2 += [a]
        if a == 1:
            c2 += 1
            if c2 >= 1:
                break

    if c1 >= 2 and c2 >= 1:
        print(1)
    else:
        ans1, ans2 = 1,1
        if c1 < 2:
            l1.pop(l1.index(min(l1)))
            ans1 = l1[0]
            for i in range(1,len(l1)):
                ans1 = f.gcd(ans1,l1[i])
        if c2 < 1:
            ans2 = l2[0]
            for i in range(1,len(l2)):
                ans2 = f.gcd(ans2,l2[i])
        print(max(ans1,ans2))

Solution (Python):

from collections import defaultdict
def inpl(): return list(map(int, input().split()))
N = int(input())
A = inpl()

def primes(N):
    sieve = [1]*(N+1)
    sieve[:2] = [0, 0]
    P = []
    for i in range(2, N+1):
        if sieve[i]:
            for j in range(2*i, N, i):
                sieve[j] = 0
            P.append(i)
    return P

P = set(primes(32000))
D = defaultdict(list)
C = set()
for a in A:
    removes = []
    for p in P:
        cnt = 0
        while a%p==0:
            cnt += 1
            a //= p
        if cnt:
            D[p].append(cnt)
        else:
            if p in C:
                removes.append(p)
            else:
                C.add(p)
    P = P - set(removes)
    if a > 1:
        D[a].append(1)

D = {k:[0]*(len(v) == N-1) + sorted(v) for k, v in D.items() if len(v) >= N-1}

ori = 1
for k, v in D.items():
    ori *= k**v[0]

ans = max(ori, 1)
for a in A:
    tmp = 1 * ori
    for p in D.keys():
        cnt = 0
        while a%p==0:
            cnt += 1
            a //= p
        if cnt == D[p][0]:
            tmp *= p**(D[p][1] - D[p][0])
    ans = max(ans, tmp)
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

tmp = A[0]
for i in range(N):
    tmp = gcd(tmp, A[i])
    
    
for i in range(N):
    A[i] //= tmp
 
A.sort(reverse=True)

v1 = A[0]
count1 = 0
for i in range(N):
    tmp1 = v1
    v1 = gcd(v1, A[i])
    if  v1 == 1:
        count1 += 1
        if count1 == 1:
            v1 = tmp1
        
        
v2 = A[1]
count2 = 0
for i in range(N):
    tmp2 = v2
    v2 = gcd(v2, A[i])
    if v2 == 1:
        count2 += 1
        if count2 == 1: 
            v2 = tmp2

if 1:
    s1 = 1
    s2 = 1
    if count1 == 1 and v1 <= 10 ** 9:
        s1 = v1
    if count2 == 1 and v2 <= 10 ** 9:
        s2 = v2
    print(tmp * max(s1, s2))

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
import bisect

memo = {}


def gcd(a, b):
    if a in memo:
        if b in memo[a]:
            return memo[a][b]
    ans = gcd_core(a, b)
    if a in memo:
        memo[a][b] = ans
    else:
        memo[a] = {}
        memo[a][b] = ans
    return ans


def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def main():
    N = int(input())
    A = list(map(int, input().split()))

    ming = 0

    cand = []

    for i in range(N):
        temp = gcd(A[i], ming)
        
        if temp != ming:
            cand.append(i)
        ming = temp

    

    answers = []
    for c in cand:
        ans1 = 0
        for i in range(N):
            if i != c:
                ans1 = gcd(A[i], ans1)
        answers.append(ans1)

    print(max(answers))


if __name__ == '__main__':
    main()

Solution (Python):
def gcd(a,b):
  if b == 0:
    ret = a
  else:
    ret = gcd(b, a%b)
  return ret

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
gu = [0 for i in range(N)]
gl = [0 for i in range(N)]
if N == 2:
  if A[0] > A[1]:
    print(A[0])
  else:
    print(A[1])
else:
  max = 0
  gu[0] = A[0]
  for i in range(1,N-1):
    y = gu[i-1]
    x = A[i]
    gu[i] = gcd(y,x)
    
  gl[0] = A[N-1]
  for i in range(1,N-1):
    y = gl[i-1]
    x = A[N-1-i]
    gl[i] = gcd(y,x)

  for i in range(N):
    if i == 0:
      x = gl[N-2]
    elif i == N-1:
      x = gu[N-2]
    else:
      y = gu[i-1]
      x = gl[N-2-i]
      x = gcd(y,x)
    if max < x:
      max = x
  print(max)

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y) 
    
list_gcd = [(gcd(A[0],A[1]),False),(A[0],True),(A[1],True)]


for i in range(2,len(A)):
    next_gcd = []
    for j in list_gcd:
        if j[1]:
            this_gcd = (gcd(j[0],A[i]),True)
            if not(this_gcd in next_gcd):
                next_gcd.append(this_gcd)
        else:
            this_gcd = (gcd(j[0],A[i]),False)
            if not(this_gcd in next_gcd):
                next_gcd.append(this_gcd)
                
            this_gcd = (j[0],True)
            if not(this_gcd in next_gcd):
                next_gcd.append(this_gcd)
    list_gcd = next_gcd
    
         
out = 1
for i in list_gcd:
    if i[0] > out:
        out = i[0]
        
print(out)

Solution (Python):
from fractions import gcd

def main():
    N = int(input())
    A = list(map(int, input().split()))

    if len(A) == 2:
        print(max(A))
        return

    if len(A) == 3:
        gcd1 = gcd(A[0], A[1])
        gcd2 = gcd(A[0], A[2])
        gcd3 = gcd(A[1], A[2])
        print(max(gcd1, gcd2, gcd3))
        return

    gcd1 = gcd(A[0], A[1])
    gcd2 = gcd(A[0], A[2])
    gcd3 = gcd(A[1], A[2])
    yet_used_gcd = max(gcd1, gcd2, gcd3)
    not_used_gcd = gcd(gcd1, A[2])

    for i in range(3, N):
        yet_used_gcd = gcd(yet_used_gcd, A[i])
        if yet_used_gcd < not_used_gcd:
            yet_used_gcd = not_used_gcd
        not_used_gcd = gcd(not_used_gcd, A[i])

    if yet_used_gcd > not_used_gcd:
        print(yet_used_gcd)
    else:
        print(not_used_gcd)

main()

Solution (Python):

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    b = sorted(make_divisors(a[0]), reverse = True)
    res = b[0]
    for i in b:
        c = [_ % i != 0 for _ in a]
        if sum(c) <= 1:
            res = i
            break
    a2 = a[1:]
    a2.sort()
    b2 = sorted(make_divisors(a2[0]), reverse = True)
    res2 = b2[0]
    for i in b2:
        c = [_ % i != 0 for _ in a]
        if sum(c) <= 1:
            res2 = i
            break
    print(max(res,res2))

Solution (Python):
from functools import reduce
import numpy as np


def _gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def gcd(*n):
    return reduce(_gcd, n)


def my_bisect(x):

    def find_pos(left, right):
        return left + (right - left - 1) // 2

    def func(left, right, prev):
        if right - left == 1:
            return [left]
        if right - left == 2:
            return [left, left+1]
        pos = find_pos(left, right)
        g1 = gcd(*x[left:pos+1])
        g2 = gcd(*x[pos+1:right])
        if prev is not None:
            g1, g2 = gcd(g1, prev), gcd(g2, prev)
        if g1 < g2:
            return func(left, pos + 1, max(g1, g2))
        else:
            return func(pos + 1, right, max(g1, g2))
    return func(0, len(x), None)


N = int(input())
A = list(map(int, input().split()))
print(max([gcd(*np.delete(A, i)) for i in my_bisect(A)]))

Solution (Python):
from fractions import gcd
from functools import reduce

def gcd_list(numbers):
    return reduce(gcd,numbers)

N = int(input())
A = list(map(int,input().split()))

res1 = [gcd(A[-1],a) for a in A]

min_res = min(res1)
index = res1.index(min_res)

res1 = [A[i] for i in range(N) if i != index]
res2 = A[:N-1]

res1 = gcd_list(res1)
res2 = gcd_list(res2)

print(max(res1,res2))

Solution (Python):
import fractions
N = int(input())
A_array = list(map(int, input().split()))

if N == 2:
    print(max(A_array[0], A_array[1]))
    exit()

remove_index = []
for i, A in enumerate(A_array):
    if i == 0:
        gcd_max = A
        remove_index.append(i)
        continue
    gcd = fractions.gcd(gcd_max, A)
    
    if gcd_max > gcd:
        gcd_max = gcd
        remove_index.append(i)



gcd_ans = gcd_max
for index in remove_index:
    gcd = 0
    for i, A in enumerate(A_array):
        if i == index:
            continue
        if gcd == 0:
            gcd = A
            continue
        
        gcd = fractions.gcd(gcd, A)
        if gcd_ans >= gcd:
            break
    
    gcd_ans = max(gcd_ans, gcd)
print(gcd_ans)

Solution (Python):
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

N = int(input())
A = list(map(int, input().split()))

A.sort()

inf = int(2e9)

m = inf
check = 0
for i in range(N):
    check1 = gcd(A[0], A[i])
    if check1 < m:
        m = check1
        check = i


check2 = A[1]
for i in range(1,N):
    check2 = gcd(check2, A[i])

ans = check2


if check != 0:
    check3 = A[0]
    for i in range(N):
        if i == check:
            continue
        check3 = gcd(check3, A[i])
    ans = max(check2, check3)

print(ans)

Solution (Python):
import fractions
import numpy as np

N = int(input())
A = np.array(sorted([int(i) for i in input().split()]))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

divisors=make_divisors(A[0])
divisors_1=make_divisors(A[1]) 
divisors.extend(divisors_1)

def gcd(l):
    ans = l[0]
    for j in range(1, N-1):
        ans = fractions.gcd(ans, l[j])
    return ans


for i in sorted(list(set(divisors))):



    if(np.sum(A%i != 0)<=1):
        
        res = i


print(res)

Solution (Python):

n = int(input())

a = list(map(int, input().split()))
a.sort(reverse=True)


from functools import lru_cache
import sys
if n == 2:
    print(max(a))
    sys.exit()


@lru_cache(maxsize=100000)
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def gcd_list(li):
    if len(li) == 1:
        return li[0]
    g = gcd(li[0], li[1])
    for i in range(2, len(li)):
        g = gcd(g, li[i])
    return g


def gcd_list_2(li):
    g = gcd(li[0], li[1])
    if g == 1:
        return max(gcd_list([li[0]] + li[2:]), gcd_list(li[1:]))
    for i in range(2, n):
        if gcd(g, li[i]) == 1:
            if i == n - 1:
                return gcd_list(li[:i])
            gg = gcd_list(li[i+1:])
            bb = [gcd(li[x], gg) for x in range(i+1)]
            bb.sort()
            return bb[1]
        else:
            g = gcd(g, li[i])
    return g


def max_gcd(a):
    g = gcd_list(a)
    a = [a[i]//g for i in range(n)]
    m = gcd_list_2(a)
    print(g * m)


max_gcd(a)

Solution (Python):
import fractions
from functools import reduce
import random
import copy

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

n = int(input())
a = list(map(int, input().split()))
ans = 1

if n < 1000:
  for i in range(n):
    b = copy.copy(a)
    b.pop(i)
    t = gcd(b)
    if ans < t:
      ans = t
else:
  for _ in range(200):
    t = gcd(random.sample(a, 500))
    if ans < t:
      ans = t

print(ans)

Solution (Python):
def gcd(x,y):
    if x == 0:return y
    return gcd(y % x, x)

n = int(input())
a = list(map(int, input().split()))

lgcd = [0]
rgcd = [0]
for i in a:
    lgcd.append(gcd(lgcd[-1], i))

for i in a[::-1]:
    rgcd.append(gcd(rgcd[-1], i))

rgcd = rgcd[::-1]

ans = 1 << 60
print(max([gcd(lgcd[i],rgcd[i+1]) for i in range(n)]))

Solution (Python):



from collections import defaultdict
import copy

N = int(input())
A = sorted(list(map(int, input().rstrip().split(' '))))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
                
    divisors.sort()
    return divisors
    
max_divisor = 0
for a in A[:2]:
    divisors = make_divisors(a)
    
    for divisor in divisors:
        if divisor > max_divisor:
            nondivisable = 0
            for a in A:
                if a % divisor != 0:
                    nondivisable += 1
                if nondivisable > 2:
                    break
                
            if nondivisable <= 1:
                max_divisor = divisor
            
            
print(max_divisor)

Solution (Python):
from fractions import gcd

n = int(input())
as_ = list(map(int, input().split()))

gcd_all = as_.pop()
set_ = {as_[0]}
for a in as_:
    set_ = set(gcd(s, a) for s in set_)
    set_.add(gcd_all)
    gcd_all = gcd(gcd_all, a)

print(max(set_))

Solution (Python):
from fractions import gcd
from functools import reduce
 
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
 
    divisors.sort()
    return divisors
 
def gcds(n):
    return reduce(gcd, n)
 
n=int(input())
a=list(map(int, input().split()))
a=sorted(a)

m1=a[0]
m2=a[1]
ans=1
divm2=make_divisors(m2)
divm2.reverse()
divm1=make_divisors(m1)
divm1.reverse()
divs=list(set(divm1+divm2))
divs.sort()
divs.reverse()
ans=1
for i in divs:
    count=0
    for j in a:
        if j%i != 0:
            count+=1
        if count>=2:
            break
    if count<=1:
        ans=i
        break
print(ans)

Solution (Python):
def gcd(a,b):
    while a>0:
        a,b  = b%a, a
    return b

N = int(input())
A = [int(c) for c in input().split()]

gcd_l = []
d = A[0]
for a in A:
    d = gcd(d,a)
    gcd_l.append(d)

gcd_r = []
d = A[-1]
for a in reversed(A):
    d = gcd(d,a)
    gcd_r.append(d)
gcd_r = list(reversed(gcd_r))

gcd_a = [gcd_r[1]]
for i in range(1,N-1):
    gcd_a.append(gcd(gcd_l[i-1], gcd_r[i+1]))
gcd_a.append(gcd_l[N-2])

print(max(gcd_a))

Solution (Python):
def gcdf(x,y):
  if y==0:return x
  if y>x:return gcdf(y,x)
  else:return gcdf(y,x%y)

N=int(input())
A=[int(s)for s in input().split()]
A=sorted(A)
if N==2:
  print(A[1])
  exit()
r=[]
for i in range(1,N):
  r.append(gcdf(A[i],A[0]))
r=sorted(r)
gcd=r[1]
for i in range(2,N-1):
  gcd=gcdf(r[i],gcd)
  
gcd2=A[1]
for i in range(2,N):
  gcd2=gcdf(A[i],gcd2)
print(max((gcd,gcd2)))

Solution (Python):
import functools
import fractions


N = int(input())
a = list(map(int,input().split()))
ans = 1
gcd = functools.reduce(fractions.gcd,a)
s_front = [1]*N
s_back = [1]*N
s_front[0] = a[0]
s_back[0] = a[N-1]

for i in range(N):
	if i > 0:
		s_front[i] = fractions.gcd(s_front[i-1],a[i])
		s_back[i] = fractions.gcd(s_back[i-1],a[N-i-1])
for i in range(N):
	if i == 0:
		gcd_new = s_back[N-2]
	elif i == N-1:
		gcd_new = s_front[N-2]
	else:
		gcd_new = fractions.gcd(s_front[i-1],s_back[N-i-2])
	ans = max(ans,gcd_new)
print(ans)

Solution (Python):




def cd(a, b):
  if a == 1 or b == 1:
    return 1

  while a != 0 and b != 0:
    if a < b:
      b %= a
    else:
      a %= b

  return a if a != 0 else b


def main():
  input()
  prevs = list(map(int, input().split()))
  posts = prevs[::-1]

  for i in range(1, len(prevs)):
    prevs[i] = cd(prevs[i - 1], prevs[i])
    posts[i] = cd(posts[i - 1], posts[i])

  posts = posts[::-1]

  gcd = max(prevs[-2], posts[1])

  for i in range(1, len(prevs) - 1):
    gcd = max(cd(prevs[i - 1], posts[i + 1]), gcd)

  print(gcd, flush=True)


if __name__ == '__main__':
  main()

Solution (Python):
import sys
import math
import fractions

sys.setrecursionlimit(10000)
INF = float('inf')


def inp():
    return int(input())


def inl():
    return list(map(int, input().split()))


def inls():
    return input().split()


def Yesif(cond):
    print('Yes' if cond else 'No')


def YESIF(cond):
    print('YES' if cond else 'NO')


def yesif(cond):
    print('yes' if cond else 'no')


N = inp()
A = inl()

ans = {A[1]}
gcd = A[0]
for a in A[1:]:
    ans = {fractions.gcd(r, a) for r in ans}
    ans.add(gcd)
    gcd = fractions.gcd(gcd, a)

print(max(ans))

Solution (Python):
import math
import fractions
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
from_left = [0 for i in range(N)]
from_right = [0 for i in range(N)]
from_left[0] = A[0]
from_right[-1] = A[-1]
for i in range(1, N):
    from_left[i] = fractions.gcd(A[i], from_left[i-1])
for i in range(N-2, -1, -1):
    from_right[i] = fractions.gcd(A[i], from_right[i+1])


ans = max(from_left[-2], from_right[1])
for i in range(1, N-1):
    ans = max(ans, fractions.gcd(from_left[i-1], from_right[i+1]))
print(ans)

Solution (Python):
from heapq import heappush,heappop
import queue
import re
import math
import functools
import numpy

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)


N = int_raw()
As = ints_raw()


def main():
    f_gcds = [As[0]]
    for i in range(1,N):
        f_gcds.append(gcd(As[i],f_gcds[-1]))
    b_gcds = [0]*(N-1)+[As[-1]]
    for i in range(N-2,-1,-1):
        b_gcds[i] = gcd(As[i],b_gcds[i+1])
    ans = max(b_gcds[1],f_gcds[-2])
    for i in range(1,N-1):
        ans = max(ans,gcd(f_gcds[i-1],b_gcds[i+1]))
    return ans

print(main())

Solution (Python):
def gcd(a, b):
    if b == 0:
        return a
    g = gcd(b, a % b)
    return g

n = input()
a_list = map(int, raw_input().split())

gs1 = [None] * n
gs1[0] = a_list[0]
for i in xrange(1, n):
    gs1[i] = gcd(gs1[i - 1], a_list[i])

gs2 = [None] * n
gs2[n - 1] = a_list[n - 1]
for i in reversed(xrange(n - 1)):
    gs2[i] = gcd(gs2[i + 1], a_list[i])

max_g = 0
for exclude in xrange(n):
    if exclude == 0:
        g = gs2[1]
    elif exclude == n - 1:
        g = gs1[n - 2]
    else:
        g = gcd(gs1[exclude - 1], gs2[exclude + 1])
    if g > max_g:
        max_g = g
print(max_g)

Solution (Python):
from functools import reduce
inf = 10**10
import sys
input = sys.stdin.readline


def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
def gcd_list(numbers):
    return reduce(gcd,numbers)
n = int(input())
a = list(map(int,input().split()))
index = inf
if n == 2:
    print(max(a))
else:
    a.sort()
    if gcd(a[0],a[n-1]) == 1:
        print(max(gcd_list(a[1:n]),gcd_list(a[0:n-1])))
    else:
        ans = gcd(a[0],a[n-1])
        for i in range(1,n-1):
            if gcd(a[i]-a[0],a[n-1]-a[i]) <= ans:
                index = i
                ans = gcd(a[i]-a[0],a[n-1]-a[i])
        print(max(gcd_list(a[0:index]+a[index+1:n]),gcd_list(a[1:n]),gcd_list(a[0:n-1])))

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
def GCD(x,y):
	if x>y:
		a=x
		b=y
	else:
		a=y
		b=x
	while(True):
		c=a%b
		if c==0:
			return b
		else:
			a,b=b,c
 

if N==2:
	print(max(A))
else:
	B=[]
	a0=A[-1]
	for aa in A[0:-1]:
		B.append(GCD(aa,a0))
	gomikamo=B.index(min(B))
	g0=A[0]
	for i in range(0,N-1):
		g0=GCD(A[i],g0)
	del A[gomikamo]
	g1=A[0]
	for i in range(N-1):
		g1=GCD(A[i],g1)
	print(max(g0,g1))