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):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

from collections import deque, defaultdict





from math import gcd

def solve():
    N = II()
    A = LI()
    
    mx = 1000003
    D = [1] * mx
    for i in range(2, len(D)):
        
        
        for j in range(i, len(D), i):
            if D[j] == 1:
                D[j] = i
    
    

    g = A[0]
    
    
    C = [0] * mx
    for a in A:
        g = gcd(g, a)
        
        
        
        
        
        d = D[a]
        p = a
        while p != d:
            p = p // d
            d = D[p]
        
        C[p] += 1
    
    
    if all(C[i] <= 1 for i in range(2, len(C))):
        flag = True
    else:
        flag = False

    if g == 1:
        if flag:
            print('pairwise coprime')
        else:
            print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    solve()

Solution (Python):
if True:
    N = int(input())
    As = list(map(int, input().split()))

    maxA = 10**6 + 6
    c = [0] * (maxA+1)
    for A in As:
        c[A] += 1
    isPrime = True
    cnt = 0
    for i in range(2, maxA+1):
        cnt = sum(c[i::i])
        if cnt == N:
            
            print("not coprime")
            break
        if cnt >= 2:
            isPrime = False
        
    else:
        if isPrime:
            print("pairwise coprime")
        else:
            print("setwise coprime")

Solution (Python):
if True:
    N = int(input())
    As = list(map(int, input().split()))

    maxA = 10**6 + 6
    c = [0] * (maxA+1)
    for A in As:
        c[A] += 1
    isPrime = True
    cnt = 0
    for i in range(2, maxA+1):
        cnt = sum(c[i::i])
        if cnt == N:
            
            print("not coprime")
            exit()
        if cnt >= 2:
            isPrime = False
        
    else:
        if isPrime:
            print("pairwise coprime")
        else:
            print("setwise coprime")

Solution (Python):

from math import gcd

def getPrime(x):
    num_list=[i for i in range(2,x+1)]
    prime_list=[]
    D=[x+1 for i in range(x+1)]
    
    while num_list[0]<x**(1/2):
        p=num_list.pop(0)
        prime_list.append(p)
        for i in range(len(num_list)):
            if num_list[i]%p==0:
                if D[num_list[i]]>p:
                    D[num_list[i]]=p
        num_list = [e for e in num_list if e % p != 0]
    
    prime_list = prime_list + num_list
    for i in range(len(prime_list)):
        D[prime_list[i]] = prime_list[i]
    D[0]=1
    D[1]=1
    return D

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

if max(A) == 1:
    print("pairwise coprime")
    exit()

D = getPrime(max(A))

pc_flg = True

x = A[0]
for i in range(N):
    x = gcd(x,A[i])

prime_flg=[False for i in range(10**6+1)]

for i in range(N):
    num = A[i]
    primes = []
    while True:
        p = D[num]
        num = num//p
        primes.append(p)
        if num == 1:
            break
    for j in set(primes):
        if not(prime_flg[j]):
            prime_flg[j] = True
        else:
            if j != 1:
                pc_flg = False


if pc_flg:
    print("pairwise coprime")
elif x==1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
if a == [1]*n:
    print("pairwise coprime")
    quit()
m = max(a)
l = [-1]*(m+3)
for i in range(2,m+1):
    if l[i] != -1:
        continue
    l[i] = i
    j = 2
    while i*j <= m:
        if l[i*j] == -1:
            l[i*j] = i
        j += 1
def fastfact(i,lst):
    if l[i] == -1:
        return lst
    while i > 1:
        lst.append(l[i])
        i //= l[i]
    return lst
check = [0]*(m+1)
for i in range(n):
    if a[i] == 1:
        continue
    s = set(fastfact(a[i],[]))
    for j in s:
        check[j] += 1
M = max(check)
if M == 1:
    print("pairwise coprime")
elif M == n:
    print("not coprime")
else:
    print("setwise coprime")

Solution (Python):
from math import gcd 
 
n = int(input())
maxA = 10**6+1
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 = A[0]
for a in A[1:]:
    g = gcd(g, a)
if g == 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 = A[0]
for a in A[1:]:
    g = gcd(g, a)
if g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
c=[0]*6**8
for a in[*open(0)][1].split():c[int(a)]+=1
m=max(sum(c[i::i])for i in range(2,6**8))
print(m<sum(c)and'psaeitr'[m>1::2]+'wise'or'not','coprime')

Solution (Python):
c=[0]*6**8
for a in[*open(0)][1].split():c[int(a)]+=1
m=max(sum(c[i::i])for i in range(2,6**8))
print(m<sum(c)and'psaeitr'[m>1::2]+'wise'or'not','coprime')

Solution (Python):
c=[0]*6**8
n,a=open(0)
for a in a.split():c[int(a)]+=1
m=max(sum(c[i::i])for i in range(2,6**8))
print(('not','psaeitr'[m>1::2]+'wise')[m<int(n)],'coprime')

Solution (Python):
c=[m:=0]*6**8
n,a=open(0)
for a in a.split():c[int(a)]+=1
print(('not','psaeitr'[any([(m:=max(m,sum(c[i::i])))>1for i in range(2,6**8)])::2]+'wise')[m<int(n)],'coprime')

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


class Osa_k:
    def __init__(self, maximum):
        self.table = [-1] * (maximum+1)
        for i in range(2, maximum+1):
            if self.table[i] != -1:
                continue
            self.table[i] = i
            for k in range(i*i, maximum+1, i):
                if self.table[k] == -1:
                    self.table[k] = i

    def factorize(self, n):
        res = Counter()
        b = n
        while 1:
            if self.table[b] == -1:
                break
            res[self.table[b]] += 1
            b //= self.table[b]
        if b != 1:
            res[b] += 1
        return res


N = int(input())
*A, = map(int, input().split())
def f():
    cnt = Counter()
    ins = Osa_k(max(A))
    for i in A:
        res = ins.factorize(i)
        for j in res.keys():
            cnt[j] += 1
            if cnt[j] >= 2:
                return False
    return True

cond1 = f()
cond2 = (reduce(gcd, A)==1)

if cond1:
    print("pairwise coprime")
elif cond2:
    print("setwise coprime")
else:
    print("not coprime")

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


class Osa_k:
    def __init__(self, maximum):
        self.table = [-1] * (maximum+1)
        for i in range(2, maximum+1):
            if self.table[i] != -1:
                continue
            for j in range(2, int(i**0.5)+1):
                if i%j == 0:
                    self.table[i] = j
                    for k in range(2*i, maximum+1, i):
                        if self.table[k] != -1:
                            self.table[k] = j
                    break

    def factorize(self, n):
        res = Counter()
        b = n
        while 1:
            if self.table[b] == -1:
                break
            res[self.table[b]] += 1
            b //= self.table[b]
        res[b] += 1
        return res


N = int(input())
*A, = map(int, input().split())
def f():
    cnt = Counter()
    ins = Osa_k(max(A))
    for i in A:
        res = ins.factorize(i) if i!=1 else {}
        for j in res.keys():
            cnt[j] += 1
            if cnt[j] >= 2:
                return False
    return True

cond1 = f()
cond2 = (reduce(gcd, A)==1)

if cond1:
    print("pairwise coprime")
elif cond2:
    print("setwise coprime")
else:
    print("not coprime")

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


class Osa_k:
    def __init__(self, maximum):
        self.table = [-1] * (maximum+1)
        for i in range(2, maximum+1):
            if self.table[i] != -1:
                continue
            for j in range(2, int(i**0.5)+1):
                if i%j == 0:
                    self.table[i] = j
                    for k in range(2*i, maximum+1, i):
                        if self.table[k] != -1:
                            self.table[k] = j
                    break

    def factorize(self, n):
        res = Counter()
        b = n
        while 1:
            if self.table[b] == -1:
                break
            res[self.table[b]] += 1
            b //= self.table[b]
        res[b] += 1
        return res


N = int(input())
*A, = map(int, input().split())
def f():
    cnt = Counter()
    ins = Osa_k(10**6)
    for i in A:
        res = ins.factorize(i) if i!=1 else {}
        for j in res.keys():
            cnt[j] += 1
            if cnt[j] >= 2:
                return False
    return True

cond1 = f()
cond2 = (reduce(gcd, A)==1)

if cond1:
    print("pairwise coprime")
elif cond2:
    print("setwise coprime")
else:
    print("not coprime")

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


class Osa_k:
    def __init__(self, maximum):
        self.table = [-1] * (maximum+1)
        for i in range(2, maximum+1):
            for j in range(2, int(i**0.5)+1):
                if i%j == 0:
                    self.table[i] = j
                    break

    def factorize(self, n):
        res = Counter()
        b = n
        while 1:
            if self.table[b] == -1:
                break
            res[self.table[b]] += 1
            b //= self.table[b]
        res[b] += 1
        return res


N = int(input())
*A, = map(int, input().split())
def f():
    cnt = Counter()
    ins = Osa_k(10**6)
    for i in A:
        res = ins.factorize(i) if i!=1 else {}
        for j in res.keys():
            cnt[j] += 1
            if cnt[j] >= 2:
                return False
    return True

cond1 = f()
cond2 = (reduce(gcd, A)==1)

if cond1:
    print("pairwise coprime")
elif cond2:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
c=[0]*6**8
n,a=open(0)
for a in a.split():c[int(a)]+=1
print(('not','psaeitr'[any(c:=[max(0,sum(c[i::i])-1)for i in range(2,6**8)])::2]+'wise')[max(c)+1<int(n)],'coprime')

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


class Osa_k:
    def __init__(self, maximum):
        self.table = [-1] * (maximum+1)
        for i in range(2, maximum+1):
            for j in range(2, int(i**0.5)+1):
                if i%j == 0:
                    self.table[i] = j
                    break

    def factorize(self, n):
        res = Counter()
        b = n
        while 1:
            if self.table[b] == -1:
                break
            res[self.table[b]] += 1
            b //= self.table[b]
        res[b] += 1
        return res


N = int(input())
*A, = map(int, input().split())
def f():
    cnt = Counter()
    ins = Osa_k(max(A))
    for i in A:
        res = ins.factorize(i) if i!=1 else {}
        for j in res.keys():
            cnt[j] += 1
            if cnt[j] >= 2:
                return False
    return True

cond1 = f()
cond2 = (reduce(gcd, A)==1)

if cond1:
    print("pairwise coprime")
elif cond2:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
m=6**8
c=[0]*m
n,a=open(0)
for a in a.split():c[int(a)]+=1
print(('not','psaeitr'[any(c:=[max(0,sum(c[i::i])-1)for i in range(2,m)])::2]+'wise')[max(c)+1<int(n)],'coprime')

Solution (Python):
import math
m=6**8
c=[g:=0]*m
for a in[*open(0)][1].split():g=math.gcd(g,a:=int(a));c[a]+=1
print(('not','psaeitr'[any(sum(c[i::i])>1for i in range(2,m))::2]+'wise')[g<2],'coprime')

Solution (Python):
n,*a=map(int,open(0).read().split())
m=6**8
c=[0]*m
p=[1,1]+c[:]
for i in range(m):
  if p[i]<1:
    for j in range(i,m,i):p[j]=i
for a in a:
  s={a}
  while a!=p[a]:
    s|={p[a]}
    a//=p[a]
    s|={a}
  for i in s:c[i]+=1
print(('not','psaeitr'[max(c[2:])>1::2]+'wise')[max(c[2:])<n],'coprime')

Solution (Python):
from functools import reduce
from math import gcd, sqrt,ceil


n = int(input())
a = list(map(int,input().split()))
m = 10**6

a_gcd = reduce(gcd,a)
if a_gcd != 1:
    print("not coprime")
    exit(0)
isset = a_gcd == 1
hurui = [i for i in range(m+1)]
for i in range(2,ceil(sqrt(m))+1):
    for j in range(2,ceil(sqrt(i))+1):
        if i==2:
            continue
        if i%j == 0:
            break
    else:
        for k in range(i+i,m,i):
            if hurui[k] != k:
                continue
            hurui[k] = i
    continue
s = set()
p_f = True
for ai in a:
    t = set()
    while(ai > 1):
        t.add(hurui[ai])
        ai //= hurui[ai]
    for ti in t:
        if ti in s:
            p_f = False
        else:
            s.add(ti)

if p_f:
    print("pairwise coprime")
elif isset:
    print("setwise coprime")

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


def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

primes=primes(int(1000))
points=[0]*1000001

from math import gcd
pairprime_flag=True
allgcd=A[0]
allprime=set()

for a in A:
    allgcd=gcd(allgcd,a)
    if pairprime_flag:
        for i in primes:
            if a%i==0:
                if points[i]==1:
                    pairprime_flag=False
                points[i]=1
                while a%i==0:
                    a//=i
            if a==1:
                break
        if a!=1:
            if points[a]!=0:
                pairprime_flag=False
            else:
                points[a]=1

if pairprime_flag:
    print('pairwise coprime')
elif allgcd==1:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
import math

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

A_max = max(A)

D = [i for i in range(1+A_max)]

for i in range(2,1+int(A_max**(1/2))):
    if D[i] == i:
        for j in range(2,1+A_max//i):
            D[i*j] = i

prime = {}

for i in range(2,1+A_max):
    if D[i] == i:
        prime[i] = 0

for a in A:
    X = []
    aa = a
    while aa > 1:
        X.append(D[aa])
        aa //= D[aa]
    
    X = set(X)

    for x in X:
        prime[x] += 1

if all([v<=1 for v in prime.values()]):
    print('pairwise coprime')

else:
    g = A[0]
    for i in range(1,N):
        g = math.gcd(g,A[i])
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Solution (Python):
import sys, math
from functools import lru_cache
import numpy as np
import heapq
from collections import defaultdict
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def sieve(n):
    res = [i for i in range(n)]

    i = 2
    while i*i < n:
        if res[i] < i:
            i += 1
            continue
        j = i*i
        while j < n:
            if res[j] == j:
                res[j] = i
            j += i
        i += 1

    return res

def factor(n, min_factor):
    res = set()
    while n > 1:
        res.add(min_factor[n])
        n //= min_factor[n]

    return res

def main():
    N = ii()
    A = np.array(list(mi()))

    m = max(A)
    s = sieve(m+1)
    d = defaultdict(bool)
    
    g = np.gcd.reduce(A)
    if g > 1:
        print('not coprime')
        return

    for a in A:
        f = factor(a, s)
        for v in f:
            if d[v]:
                print('setwise coprime')
                return
            d[v] = True

    print('pairwise coprime')



if __name__ == '__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

if reduce(gcd, A) != 1:
    print("not coprime")
    exit()
ma = max(A)
p = list(range(ma+1))

for x in range(2, int(ma ** 0.5) + 1):
    if p[x]:
        
        for i in range(2 * x, ma + 1, x):
            p[i] = x

s = [set() for _ in range(N)]
t = set()

for i, x in enumerate(A):
    while x != 1:
        s[i].add(x)
        t.add(x)
        
        x //= p[x]
l = sum(len(x) for x in s)
print("pairwise coprime" if l == len(t) else "setwise coprime")

Solution (Python):
from math import gcd
from functools import reduce
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))

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

def primes(x):
  ret=[]
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      ret.append(i)
      if x//i!=i:
        ret.append(x//i)
  ret.sort()
  return ret[1:]
      
s=set()
for q in a:
  p=primes(q)
  for j in p:
    if j in s:
      print("setwise coprime")
      exit()
    s.add(j)
print("pairwise coprime")

Solution (Python):
from math import gcd
from functools import reduce
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))

g=reduce(gcd,a)
if g!=1:
  print("not coprime")
  exit()

def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
  
def primes(x):
  ret=[]
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      ret.append(i)
      if x//i!=i:
        ret.append(x//i)
  ret.sort()
  return ret[1:]
      
d=defaultdict(int)
for q in a:
  
  p=primes(q)
  for j in p:
    if d[j]==1:
      print("setwise coprime")
      exit()
    d[j]+=1
print("pairwise coprime")

Solution (Python):
from math import gcd
from functools import reduce
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))

g=reduce(gcd,a)
if g!=1:
  print("not coprime")
  exit()

def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

s=set()
for q in a:
  p=primeFactor(q)
  for j in p:
    if j in s:
      print("setwise coprime")
      exit()
    s.add(j)
print("pairwise coprime")

Solution (Python):
from math import gcd
from functools import reduce
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))

g=reduce(gcd,a)
if g!=1:
  print("not coprime")
  exit()

def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
d=defaultdict(int)
s=set()
for q in a:
  p=primeFactor(q)
  for j in p:
    if d[j]==1:
      print("setwise coprime")
      exit()
    d[j]+=1
print("pairwise coprime")

Solution (Python):
from math import gcd
from functools import reduce
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))

g=reduce(gcd,a)
if g!=1:
  print("not coprime")
  exit()

def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
d=defaultdict(int)
for q in a:
  p=primeFactor(q)
  for j in p:
    d[j]+=1

for _,di in d.items():
  if di>=2:
    print("setwise coprime")
    exit()
print("pairwise coprime")

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


def main():
    N = int(input())
    A = [int(i) for i in input().split()]

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

    if not g == 1:
        print('not coprime')
        return


    limit = int(10 ** 3)
    F = [0] * (10 ** 6 + 1)
    M = [0] * (10 ** 6 + 1)
    for i in range(2, limit + 1):
        if F[i] > 0:
            continue
        v = 2 * i
        while v <= 10 ** 6:
            if F[v] == 0:
                F[v] = i
            v += i

    pc = True
    for v in A:
        S = set()
        x = v
        while True:
            if F[x] > 0:
                S.add(F[x])
                x //= F[x]
            else:
                S.add(x)
                break

        for s in S:
            if s == 1:
                continue
            if M[s] == 1:
                pc = False
                break
            M[s] += 1

        if not pc:
            break

    if pc:
        print('pairwise coprime')
    else:
        print('setwise coprime')


if __name__ == '__main__':
    main()

Solution (Python):

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

R = max(A)
prime_factor_counter = [0]*(R+1)



D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i



for a in A:
    tmp = a
    while tmp > 1:
        prime_factor = D[tmp]
        prime_factor_counter[prime_factor] += 1
        while tmp%prime_factor == 0:
            tmp //= prime_factor


if max(prime_factor_counter) < 2:
    print('pairwise coprime')
elif max(prime_factor_counter) - A.count(1) < N:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
from collections import defaultdict

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

Ones = A.count(1)
R = max(A)
nums = [0]*(R+1)


D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i


for a in A:
    tmp = a
    while tmp > 1:
        prime_factor = D[tmp]
        nums[prime_factor] += 1
        while tmp%prime_factor == 0:
            tmp //= prime_factor
y = max(nums)
if y < 2:
    print('pairwise coprime')
elif y-Ones < N:
    print('setwise coprime')
else:
    print('not coprime')