Problem:
 Score : 500 points    Problem Statement We have N integers. The i -th number is A_i .  \{A_i\} is said to be pairwise coprime when GCD(A_i,A_j)=1 holds for every pair (i, j) such that 1\leq i < j \leq N .  \{A_i\} is said to be setwise coprime when \{A_i\} is not pairwise coprime but GCD(A_1,\ldots,A_N)=1 .  Determine if \{A_i\} is pairwise coprime, setwise coprime, or neither.  Here, GCD(\ldots) denotes greatest common divisor.      Constraints  2 \leq N \leq 10^6  1 \leq A_i\leq 10^6         Input Input is given from Standard Input in the following format:  N  A_1  \ldots  A_N       Output If \{A_i\} is pairwise coprime, print pairwise coprime ; if \{A_i\} is setwise coprime, print setwise coprime ; if neither, print not coprime .        Sample Input 1 3
3 4 5      Sample Output 1 pairwise coprime  GCD(3,4)=GCD(3,5)=GCD(4,5)=1 , so they are pairwise coprime.       Sample Input 2 3
6 10 15      Sample Output 2 setwise coprime  Since GCD(6,10)=2 , they are not pairwise coprime. However, since GCD(6,10,15)=1 , they are setwise coprime.       Sample Input 3 3
6 10 16      Sample Output 3 not coprime  GCD(6,10,16)=2 , so they are neither pairwise coprime nor setwise coprime.

Solution (Python):
def li():
    return [int(x) for x in input().split()]

N = int(input())
A = li()

import math
from functools import reduce
from collections import defaultdict



def GCD_list(numbers):
    return reduce(math.gcd, numbers)




MAX = 10 ** 6
is_prime = [True] * (MAX + 1)
divs = [1] * (MAX + 1)
is_prime[0], is_prime[1] = False, False
i = 1
while i * i <= MAX:
    if not is_prime[i]:
        i += 1
        continue
    for j in range(2 * i, MAX + 1, i):
        is_prime[j] = False
        divs[j] = i
    i += 1

pairwise_coprime = True
all_primes = defaultdict(int)
for k in range(N):
    n = A[k]
    p = divs[n]
    primes = defaultdict(int)
    while p > 1:
        primes[p] += 1
        n = n // p
        p = divs[n]
    
    if n != 1:
        primes[n] += 1
    for key in primes:
        if all_primes[key] > 0 and primes[key] > 0:
            pairwise_coprime = False
            break
        all_primes[key] += primes[key]

gcd = GCD_list(A)
setwise_comprime = (gcd == 1)
if pairwise_coprime:
    print('pairwise coprime')
elif setwise_comprime:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
import sys, math
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().split()]

m = max(a)
primes = list(range(m+1))
primes[1] = 0
for i in range(2, m+1, 2): primes[i] = 2

for i in range(3, int(m ** 0.5)+1):
    for j in range(i, m+1, i):
        if primes[j] > i: primes[j] = i

b = [0] * (m + 1)
jdg_p = True
for aa in a:
    aset = set()
    while aa != 1:
        aset.add(primes[aa])
        aa //= primes[aa]
    for aaset in aset:
        b[aaset] += 1
        if b[aaset] >= 2:
            jdg_p = False
            break
        else:
            b[aaset] += 1
    if not jdg_p: break

x = a[0]
jdg_s = True
for aa in a[1:]:
    x = math.gcd(x, aa)
if x != 1: 
    jdg_s = False

if jdg_p: print('pairwise coprime')
elif jdg_s: print('setwise coprime')
else: print('not coprime')

Solution (Python):
import math
import _collections
n=int(input())
A=list(map(int,input().split()))
ans=A[0]
X=[0]*(max(A)+1)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return set(a)



for i in range(1,n):
    ans=math.gcd(ans,A[i])

if ans!=1:
    print('not coprime')
else:
    ans='pairwise coprime'
    for a in A:
        B=prime_factorize(a)
        for b in B:
            if X[b]!=0:
                ans='setwise coprime'
            else:
                X[b]+=1
    print(ans)

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

number_list = [0]*1000010
for a in A:
    number_list[a] += 1
    
flag1 = True
flag2 = True

for i in range(2,1000001):
    count = 0
    for j in range(1,1000001):
        if i*j > 1000000:
            break
        tmp = i*j
        count += number_list[tmp]
    if count > 1:
        flag1 = False
    if count == N:
        flag2 = False
        
if flag2 == False and flag1 == False:
    print("not coprime")
elif flag2 == True and flag1 == False:
    print("setwise coprime")
else:
    print("pairwise coprime")

Solution (Python):
from math import gcd
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return set(a)
  
n = int(input())
a = list(map(int, input().split()))
dic = {}
g = a[0]
flg = True
for i in range(n):
  g = gcd(g, a[i])
  if flg:
    tmp = prime_factorize(a[i])
    for j in tmp:
      if j in dic:
        flg = False
      else:
        dic[j]=1
        
if flg:
  print("pairwise coprime")
elif g == 1:
  print("setwise coprime")
else:
  print("not coprime")

Solution (Python):
from math import gcd
from functools import reduce
k=10**6+1
def judge(n,a):
  c=[0]*k
  for x in a:
    c[x]+=1 
  t=any(sum(c[i::i])>1 for i in range(2,k)) 
  t+=reduce(gcd,a)>1 
  return ['pairwise','setwise','not'][t]+' coprime' 
n=int(input())
a=list(map(int,input().split()))
print(judge(n,a))

Solution (Python):
from math import gcd
from functools import reduce
k=10**6+1
def judge(n,a):
  c=[0]*k
  for x in a:
    c[x]+=1
  t=any(sum(c[i::i])>1 for i in range(2,k))
  t+=reduce(gcd,a)>1
  return ['pairwise','setwise','not'][t]+' coprime'
n=int(input())
a=list(map(int,input().split()))
print(judge(n,a))

Solution (Python):
from math import gcd
from functools import reduce
NUM_MAX = 10**6 + 1
def solve(n, a):
    c = [0] * NUM_MAX
    for x in a:
        c[x] += 1
    t = any(sum(c[i::i]) > 1 for i in range(2, NUM_MAX))
    t += reduce(gcd, a) > 1
    return ["pairwise", "setwise", "not"][t] + " coprime"

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

Solution (Python):
import math
n = int(input())
a = list(map(int, input().split()))

def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a
r = [0] * (n+1)
sosu = [False for i in range(10**6+1)]

for i in range(n):
  r[i+1] = math.gcd(r[i],a[i])
if r[-1] != 1:
  print ('not coprime')
  exit()

for i in range(n):
  ary = set(prime_factorize(a[i]))
  for j in ary:
    if sosu[j]:
      print ('setwise coprime')
      exit()
    sosu[j] = True
print ('pairwise coprime')

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)
    N = 1000001
    f = [1]*N
    lis = []
    p = 2
    while p < N:
        while p < N and not f[p]:
            p += 1
        j = p
        lis.append(p)
        while j < N:
            f[j] = 0
            j += p
    def func(n):
        i = 0
        p = lis[i]
        if n < 2:
            return 0
        while p*p <= n:
            if n%p == 0:
                if c[p]:
                    return 1
                c[p] = 1
                while n%p == 0:
                    n //= p
            i += 1
            p = lis[i]
        if c[n]:
            return 1
        if n > 1:
            c[n] = 1
        return 0
    n = I()
    a = LI()
    g = a[0]
    for i in a[1:]:
        g = gcd(g,i)
    if g != 1:
        print("not coprime")
        return
    c = [0]*N
    for i in a:
        if func(i):
            print("setwise coprime")
            return
    print("pairwise coprime")
    return


if __name__ == "__main__":
    solve()

Solution (Python):
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineerin College

'''
import sys
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007

inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]



def solve():
    
    
    
    
    
    
    n = ii()
    a = li()
    f = 1
    freq = [0]*1000005
        
    for i in a:
        x = i
        for j in range(2,int(sqrt(x))+1):
            c = 0
            while(x%j==0):
                x//=j
                c=1
            if(c > 0):
                if freq[j]>0:
                    f = 0
                    break
                freq[j] = 1
        if(x>1):
            freq[x]+=1
            if(freq[x]>1):
                f = 0
                break
        if(f==0):
            break
        
    if(f):
        print('pairwise coprime')
    else:
        x = a[0]
        for i in range(1,n):
            x = gcd(x,a[i])
        if(x==1):
            print('setwise coprime')
        else:
            print('not coprime')
    
    
    
    
    
    
    
if __name__ =="__main__":
    
    solve()

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

cnt = [0] * (10**6 + 1)
for i in range(N):
    cnt[A[i]] += 1

flag = True
for i in range(2, 10**6 + 1):
    multiple = 0
    for j in range(i, 10**6 + 1, i):
        multiple += cnt[j]
    if multiple == N:
        print("not coprime")
        exit()
    if multiple >= 2:
        flag = False

print("pairwise coprime" if flag else "setwise coprime")

Solution (Python):
import math
N = int(input())
Alist = list(map(int,input().split()))
box = [0]*(10**6+1)
sign = math.gcd(Alist[0],Alist[1])
Amax = max(Alist[0],Alist[1])
for i in range(0,len(Alist)):
    A = Alist[i]
    sign = math.gcd(sign, A)
    Amax = max(Amax, A)
    box[A] += 1
setwise = (sign == 1)
pairwise = (sign == 1)
Amax = math.sqrt(Amax)+1
for i in range(2,10**6+1):
    if sum(box[i::i]) >1:
        pairwise = False
        break
if setwise:
    if pairwise:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
from math import gcd
from functools import reduce
NUM_MAX = 10**6 + 1
def solve(n, a):
    c = [0] * NUM_MAX
    for x in a:
        c[x] += 1
    t = any(sum(c[i::i]) > 1 for i in range(2, NUM_MAX))
    t += reduce(gcd, a) > 1
    return ["pairwise", "setwise", "not"][t] + " coprime"

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

Solution (Python):
import sys
input = sys.stdin.readline

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


def prime_factor(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return set(a)




n=int(input())
L=list(map(int,input().split()))
val = L[0]

for i in range(1,n):
    val = gcd(L[i],val)

if val!=1:
    print('not coprime')
    sys.exit()

d={}
for i in range(n):
    factor=prime_factor(L[i])
    for j in factor:
        if j not in d:
            d[j]=1
        else:
            print('setwise coprime')
            sys.exit()
print('pairwise coprime')

Solution (Python):
from math import gcd
N = int(input())
A = list(map(int,input().split()))

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

MAXA = 10**6
B = [0] * (MAXA+1)
for a in A:
    if a==1: continue
    if B[a]:
        print('setwise coprime')
        exit()
    B[a] = 1

for n in range(2,MAXA+1):
    c = 0
    for m in range(n,MAXA+1,n):
        c += B[m]
        if c > 1:
            print('setwise coprime')
            exit()

print('pairwise coprime')

Solution (Python):
_, *A = map(int, open(0).read().split())
lc = 10**6 + 1
C = [0] * lc
for a in A: C[a] += 1
import functools, math
t = any(sum(C[i::i]) > 1 for i in range(2, lc))
t += functools.reduce(math.gcd, A) > 1
print(['pairwise','setwise','not'][t], 'coprime')

Solution (Python):
_ = input()
A = [*map(int, input().split())]
C = [0] * (1000001)
for a in A: C[a] += 1
from functools import reduce
from math import gcd
t = any(sum(C[i::i]) > 1 for i in range(2, 1000001))
t += reduce(gcd, A) > 1
print(['pairwise','setwise','not'][t], 'coprime')

Solution (Python):
import sys, math

N = int(input())
A = list(map(int, input().split()))
G = 0
for a in A:
    G = math.gcd(G, a)

if G != 1:
    print("not coprime")
    exit(0)

M = 10 ** 6 + 5
B = dict()
for a in A:
    if a in B:
        B[a] = B[a] + 1
    else:
        B[a] = 1

for i in range(2, M):
    cnt = 0
    for j in range(i, M, i):
        if j in B:
            cnt += B[j]
    if cnt > 1:
        print("setwise coprime")
        exit(0)

print("pairwise coprime")

Solution (Python):
from collections import defaultdict
MAX_A = 10**6

sieve = [[] for _ in range(MAX_A+1)]



for f in range(2, MAX_A + 1):
  if not sieve[f]:
    c = f
    while c <= MAX_A:
      sieve[c].append(f)
      c += f

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

cnt = defaultdict(int)
for a in A:
  for s in sieve[a]:
    cnt[s] += 1

def is_pairwise_coprime():
  return all(v == 1 for v in cnt.values())

def is_setwise_coprime():
  return all(v < N for v in cnt.values())

if is_pairwise_coprime():
  print('pairwise coprime')
elif is_setwise_coprime():
  print('setwise coprime')
else:
  print('not coprime')

Solution (Python):
import math
from functools import reduce

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

max_A = max(A)
sqrt_max_A = math.ceil(max_A ** 0.5)
sieve = list(range(2, max_A+1))
prime = list(range(max_A+1))
while len(sieve) > 0 and sieve[0] <= sqrt_max_A:
    p = sieve[0]
    prime[p]= p
    new_sieve = []
    for s in sieve:
        if s % p == 0:
            prime[s] = p
        else:
            new_sieve.append(s)
    sieve = new_sieve

factors = {}
pairwise = True
for a in A:
    while prime[a] != a:
        if prime[a] in factors:
            pairwise = False
            break
        factors[prime[a]] = True
        p = prime[a]
        while a % p == 0:
            a //= p
    if a != 1:
        if a in factors:
            pairwise = False
        else:
            factors[a] = True
    if not pairwise:
        break
if pairwise:
    print('pairwise coprime')
else:
    gcd = reduce(math.gcd, A)
    if gcd == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n = int(input())
a = [int(x) for x in input().split()]


def smallest_prime_factors(a):
    max_a = max(a)
    smallest_prime_factors = [int(x) for x in range(max_a + 1)]
    for i in range(2, max_a + 1):
        if smallest_prime_factors[i] == i:
            for j in range(i, max_a + 1, i):
                if smallest_prime_factors[j] == j:
                    smallest_prime_factors[j] = i
        else:
            continue
    return smallest_prime_factors

smallest_prime_factors = smallest_prime_factors(a)


def prime_factorize(n):
    prime_factors = []
    if n == 1:
        return prime_factors
    while n != smallest_prime_factors[n]:
        prime_factors.append(smallest_prime_factors[n])
        n //= smallest_prime_factors[n]
    prime_factors.append(n)
    return prime_factors

prime_factors = set()

flag = 1

for i in a:
    prime_factorize_i = set(prime_factorize(i))
    for j in prime_factorize_i:
        if j in prime_factors:
            flag = 0
            break
        else:
            prime_factors.add(j)

if flag:
    print('pairwise coprime')
    sys.exit()

import math
from functools import reduce

def gcd(*numbers):
    return abs(reduce(math.gcd, numbers))

if gcd(*a) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]

    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1




for pp in range(2,amax+1):
    psum=sum(aa[pp: :pp])

    if psum>=2:
            print("setwise coprime")
            sys.exit()

print("pairwise coprime")

Solution (Python):

import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

from collections import deque    






def get_primenumber(number):
    prime_list = []

    search_list = list(range(2,number+1))
    

    while search_list[0]**2 <= number:
      
      

        head_num = search_list.pop(0)
        prime_list.append(head_num)
        

        search_list =[num for num in search_list if num % head_num != 0]
    
    prime_list.extend(search_list)
    return prime_list

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp.sort()
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1




for pp in range(2,amax+1):
    psum=sum(aa[pp: :pp])

    if psum>=2:
            print("setwise coprime")
            sys.exit()

print("pairwise coprime")

Solution (Python):
import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

from collections import deque    






def get_primenumber(number):
    prime_list = []
    search_list = deque(list(range(2,number+1)))

    

    while search_list[0]**2 <= number:
      
      
        head_num = search_list.popleft()

        prime_list.append(head_num)
        
        search_list =deque( [num for num in search_list if num % head_num != 0])
    
    prime_list.extend(search_list)
    return prime_list

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp.sort()
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1




for pp in range(2,amax+1):
    psum=sum(aa[pp: :pp])

    if psum>=2:
            print("setwise coprime")
            sys.exit()

print("pairwise coprime")

Solution (Python):

import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

from collections import deque    






def get_primenumber(number):
    prime_list = []
    search_list = deque(list(range(2,number+1)))

    

    while search_list[0]**2 <= number:
      
      
        head_num = search_list.popleft()

        prime_list.append(head_num)
        
        search_list =deque( [num for num in search_list if num % head_num != 0])
    
    prime_list.extend(search_list)
    return prime_list

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp.sort()
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1

p=get_primenumber(amax)

for pp in p:

    psum=sum(aa[pp: :pp])

    if psum>=2:
            print("setwise coprime")
            sys.exit()

print("pairwise coprime")

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

N, *A = map(int, open(0).read().split())

C = [0] * (max(A) + 1)
for a in A:
    C[a] += 1

if reduce(gcd, A) != 1:
    print("not coprime")

elif all(sum(C[i::i]) <= 1 for i in range(2, len(C))):
    print("pairwise coprime")

else:
    print("setwise coprime")

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

N, *A = map(int, open(0).read().split())

C = [0] * (10 ** 6 + 10)
for a in A:
    C[a] += 1

if reduce(gcd, A) != 1:
    print("not coprime")

elif all(sum(C[i::i]) <= 1 for i in range(2, len(C))):
    print("pairwise coprime")

else:
    print("setwise coprime")

Solution (Python):
from math import gcd

n = int(input())
A = list(map(int, input().split()))
maxA = 10**6+5

def furui(x):
    memo = [0]*(x+1)
    primes = []
    for i in range(2, x+1):
        if memo[i]: continue
        primes.append(i)
        memo[i] = i
        for j in range(i*i, x+1, i):
            if memo[j]: continue
            memo[j] = i
    return primes

primes = furui(maxA)

c = [0]*maxA
for a in A: c[a] += 1

for p in primes:
    cnt = 0
    for i in range(p, maxA, p):
        cnt += c[i]
    if cnt >= 2:
        break
else:
    print('pairwise coprime')
    exit()

g = 0
for a in A:
    g = gcd(g, a)
if g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
from math import gcd
n=int(input())
a=list(map(int,input().split()))
g=gcd(a[0],a[1])
for i in range(n-2):
    g=gcd(g,a[i+2])
if a==[1]*n:
    print("pairwise coprime")
    exit()
if g!=1:
    print("not coprime")
    exit()
temp=[i for i in range(10**6+5)]
p=2
while p*p<=10**6+5:
    if temp[p]==p:
        for q in range(2*p,10**6+5,p):
            if temp[q]==q:
                temp[q]=p
    p+=1
ans=[0]*(10**6+10)
for j in a:
    count=set()
    while j>1:
        count.add(temp[j])
        j//=temp[j]
    for k in count:
        ans[k]+=1
if max(ans)!=1:
    print("setwise coprime")
else:
    print("pairwise coprime")

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

n = int(input())
A = list(map(int, input().split()))
maxA = 10**6+5

def furui(x):
    memo = [0]*(x+1)
    for i in range(2, x+1):
        if memo[i]: continue
        memo[i] = i
        for j in range(i*i, x+1, i):
            if memo[j]: continue
            memo[j] = i
    return memo

memo = furui(maxA)
tf = [True]*(maxA)
for a in A:
    if a == 1: continue
    pfct = []
    while a > 1:
        pfct.append(memo[a])
        a //= memo[a]

    for b in set(pfct):
        if not tf[b]:
            break
        tf[b] = False
    else:
        continue
    break
else:
    print('pairwise coprime')
    exit()

if reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
from math import gcd 

n = int(input())
maxA = 10**6+5
A = list(map(int, input().split()))
c = [0]*maxA
for a in A:
    c[a] += 1

for i in range(2, maxA):
    cnt = 0
    for j in range(i, maxA, i):
        cnt += c[j]
    if cnt >= 2:
        break
else:
    print('pairwise coprime')
    exit()

g = 0
for a in A:
    g = gcd(g, a)
if g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
from math import gcd
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
x=[-1]*(10**6+5)
x[0]=0
x[1]=1
i=2
while i<=10**6+1:
    j=2*i
    if x[i]==-1:
        x[i]=i
        while j<=10**6+1:
            if x[j]==-1:x[j]=i
            j+=i
    i+=1

z=[0]*(10**6+5)

g=gcd(a[0],a[0])
for i in range(n):
    g=gcd(g,a[i])
if g!=1:
    print("not coprime")
else:
    f=0
    for i in range(n):
        p=1
        while a[i]>=2:
            if p==x[a[i]]:
                a[i]=a[i]//p
                continue
            else:
                p=x[a[i]]
                z[p]+=1
                a[i]=a[i]//p

    for i in range(10**6+1):
        if z[i]>=2:
            f=1
    print("pairwise coprime" if f==0 else "setwise coprime")

Solution (Python):
from math import gcd
n=int(input())
a=list(map(int,input().split()))
x=[-1]*(10**6+5)
x[0]=0
x[1]=1
i=2
while i<=10**6+1:
    j=2*i
    if x[i]==-1:
        x[i]=i
        while j<=10**6+1:
            if x[j]==-1:x[j]=i
            j+=i
    i+=1

z=[0]*(10**6+5)

g=gcd(a[0],a[0])
for i in range(n):
    g=gcd(g,a[i])
if g!=1:
    print("not coprime")
else:
    f=0
    for i in range(n):
        p=1
        while a[i]>=2:
            if p==x[a[i]]:
                a[i]=a[i]//p
                continue
            else:
                p=x[a[i]]
                z[p]+=1
                a[i]=a[i]//p

    for i in range(10**6+1):
        if z[i]>=2:
            f=1
    print("pairwise coprime" if f==0 else "setwise coprime")

Solution (Python):
from math import gcd
n=int(input())
a=list(map(int,input().split()))
x=[-1]*(10**6+5)
x[0]=0
x[1]=1
i=2
while i<=10**6+1:
    j=2*i
    if x[i]==-1:
        x[i]=i
        while j<=10**6+1:
            x[j]=i
            j+=i
    i+=1

z=[0]*(10**6+5)

g=gcd(a[0],a[0])
for i in range(n):
    g=gcd(g,a[i])
if g!=1:
    print("not coprime")
else:
    f=0
    for i in range(n):
        p=1
        while a[i]>=2:
            if p==x[a[i]]:
                a[i]=a[i]//p
                continue
            else:
                p=x[a[i]]
                z[p]+=1
                a[i]=a[i]//p

    for i in range(10**6+1):
        if z[i]>=2:
            f=1
    print("pairwise coprime" if f==0 else "setwise coprime")

Solution (Python):
from math import gcd
n=int(input())
a=list(map(int,input().split()))
x=[-1]*(10**6+5)
x[0]=0
x[1]=1
i=2
while i<=10**6+1:
    j=2*i
    if x[i]==-1:
        x[i]=i
        while j<=10**6+1:
            x[j]=i
            j+=i
    i+=1

z=[0]*(10**6+5)
def d(y):
    t=[]
    while y>=2:
        p=x[y]
        t.append(p)
        y=y//p
    t=list(set(t))
    for i in range(len(t)):
        z[t[i]]+=1
    return
g=gcd(a[0],a[0])
for i in range(n):
    g=gcd(g,a[i])
if g!=1:
    print("not coprime")
else:
    f=0
    for i in range(n):
        d(a[i])
    for i in range(10**6+1):
        if z[i]>=2:
            f=1
    print("pairwise coprime" if f==0 else "setwise coprime")

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

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

def furui(x):
    memo = [0]*(x+1)
    primes = []
    for i in range(2, x+1):
        if memo[i]: continue
        primes.append(i)
        memo[i] = i
        for j in range(i*i, x+1, i):
            if memo[j]: continue
            memo[j] = i
    return memo, primes

memo, primes = furui(10**6+5)

pr = [True]*(10**6+5)
for a in A:
    if a == 1: continue
    while a != 1:
        w = memo[a]
        if not pr[w]:
            break
        pr[w] = False
        while a%w == 0:
            a = a // w
    else:
        continue
    break
else:
    print('pairwise coprime')
    exit()

if reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
def gen_d_prim(n):
    D = [0,0] + [-1] * (n-1)
    for i in range(2, n+1):
        if D[i] > 0: continue
        for j in range(i, n+1, i): D[j] = i
    return D

def is_pairwise(A):
    D = gen_d_prim(10**6)
    past = set()
    for a in A:
        now = set()
        while a != 1:
            if not D[a] in now and D[a] in past:
                return False
            now.add(D[a])
            past.add(D[a])
            a //= D[a]
    return True

def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def solve():
    if is_pairwise(A): return 0
    if gcd_all(A) ==1: return 1
    return 2
    
n = int(input())
A = [*map(int,input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Solution (Python):
def gen_d_prim(n):
    D = [0,0] + [-1] * (n-1)
    for i in range(2, n+1):
        if D[i] > 0: continue
        for j in range(i, n+1, i): D[j] = i
    return D

def is_pairwise(A):
    D = gen_d_prim(10**6)
    past = set()
    for a in A:
        now = set()
        while a != 1:
            if not D[a] in now and D[a] in past:
                return False
            now.add(D[a])
            past.add(D[a])
            a //= D[a]
    return True

def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def solve():
    if is_pairwise(A): return 0
    if gcd_all(A) ==1: return 1
    return 2
    
n = int(input())
A = [*map(int,input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Solution (Python):
import math
import sys
from functools import lru_cache
sys.setrecursionlimit(10000000)

N = int(input())
A_list = [int(e) for e in input().split()]





def make_trial_division_dict(n):
    
    td_dict = dict()
    for i in range(2,n+1):
        if i not in td_dict:
            td_dict[i] = i
            for j in range(2,1+n//i):
                if j*i not in td_dict:
                    td_dict[j*i] = i
    td_dict[1] = 1
    return td_dict


@lru_cache(maxsize=None)
def high_speed_prime_factorization(n):
    pf_list = list()
    pf_list.append(td_dict[n])
    
    if n//td_dict[n] == 1:
        if n!=1:
            pf_list.append(1)
        return pf_list
    else:
        pf_list.extend(high_speed_prime_factorization(n//td_dict[n]))
        return pf_list

td_dict = make_trial_division_dict(max(A_list))

all_pf = set()    
common_pf = set() 
all_pf |= set(high_speed_prime_factorization(A_list[0]))
common_pf |= set(high_speed_prime_factorization(A_list[0]))
is_pairwise = True



for i in range(1,len(A_list)):
    A_pf = set(high_speed_prime_factorization(A_list[i]))
    common_pf &= A_pf 
    
    
    
    if is_pairwise and len(all_pf&A_pf)!=1: 
        is_pairwise = False
    else:
        all_pf |= A_pf

if is_pairwise:
    print("pairwise coprime")
elif len(common_pf) == 1: 
    print("setwise coprime")
else:
    print("not coprime")