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):
n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    if sum(C[2:MAX_A:2]) > 1: pairwise = False
    for i in range(3, MAX_A, 2):
        if sum(C[i:MAX_A:i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')

Solution (Python):

from math import gcd
N=int(input())
A=list(map(int,input().split()))
GCD=A[0]
for i in range(1,N):
    GCD=gcd(GCD,A[i])
    
def Fast_PFact(n):
    List=[0 for i in range(n+1)]
    List[1]=1
    for i in range(2,n+1):
        if List[i]==0:
            cnt=1
            while i*cnt<=n:
                List[i*cnt]=i
                cnt+=1
    return List

if GCD==1:
    P=Fast_PFact(10**6)
    L=[False for i in range(10**6+1)]
    flag=False
    for i in range(N):
        a=A[i]
        while a>1:
            if L[P[a]]:
                flag=True
                break
                
            else:
                L[P[a]]=True
                divisor=P[a]
                while divisor==P[a]:
                    a=int(a/divisor)        
    if flag:
        ans="setwise coprime"
    else:
        ans="pairwise coprime"
else:
    ans="not coprime"
print(ans)

Solution (Python):
n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for i in range(2, MAX_A):
        if sum(C[i:MAX_A:i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')

Solution (Python):
N=int(input())
*A,=map(int,input().split())
M=max(A)
B=[1]*(M+1)
B[0]=B[1]=1
i=2
while i<=M:
    if B[i]:
        j=2
        while i*j<=M:
            B[i*j]=0
            j+=1
    i+=1

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

from math import*
now=A[0]
for a in A:
    now=gcd(now,a)
if now==1:
    ans='pairwise coprime'
    i=2
    while i<=M:
        if B[i]:
            count=0
            j=1
            while i*j<=M:
                count+=C[i*j]
                j+=1
            if count>1:
                ans='setwise coprime' 
        i+=1
    print(ans)
else:
    print('not coprime')

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

M = max(a)
biggest_prime = [0] * (M+10)
for i in range(2, M+10):
    if biggest_prime[i] == 0:
        biggest_prime[i] = i
        for j in range(i*i, M+1, i):
            biggest_prime[j] = i

def fact(n):
    arr=[]
    while n>1:
        now=n
        cnt=0
        p=biggest_prime[now]
        while now % p == 0:
            now//=p
            cnt+=1
        arr.append([p,cnt])
        n=now
    return arr

from collections import defaultdict
cntd=defaultdict(int)
for i in range(len(a)):
    lis = fact(a[i])
    for num,cnt in lis:
        if num==1:
            continue
        cntd[num]+=1
flg=False
for c in cntd.values():
    if c==n:
        print("not coprime")
        exit()
    if c>1:
        flg=True
if flg:
    print("setwise coprime")
else:
    print("pairwise coprime")

Solution (Python):
import math

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

a=max(A)
def era(n):
  prime=[]
  furui=list(range(2,n+1))
  while furui[0]<math.sqrt(n):
    prime.append(furui[0])
    furui=[i for i in furui if i%furui[0]!=0]
  return prime+furui

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

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

furui=era(10**6+7)
minfac=list(range(10**6+7))
for i in furui:
  for j in range(i,(10**6+7)//i):
    if minfac[i*j]==i*j:
      minfac[i*j]=i
      
dummy=[False]*(10**6+7)
for i in range(N):
  k=A[i]
  while k!=1:
    if dummy[minfac[k]]==True:
      print("setwise coprime")
      exit()
    else:
      dummy[minfac[k]]=True
      f=minfac[k]
      while k%f==0:
        k//=f
print("pairwise coprime")

Solution (Python):
import math
def div(s):
    i=1
    while(i<=math.sqrt(s)):
        if(s%i==0):
            if(s//i==i):
                if(i!=1):
                    if(i in d):
                        return False
                    else:
                        d[i]=1
            else:
                if(i!=1):
                    if(i in d):
                        return False
                    else:
                        d[i]=1
                if(s//i!=1):
                    if(s//i in d):
                        return False
                    else:
                        d[s//i]=1
        i+=1
    
    return True
                

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

d=dict()

setwise=False
pairWise=True
pairWise&=div(l[0])
pairWise&=div(l[1])
val=math.gcd(l[0],l[1])

for i in range(2,n):
    pairWise&=div(l[i])
    val=math.gcd(val,l[i])
if(pairWise):
    print('pairwise coprime')
elif(val==1):
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
M=max(a)
biggest_prime = [0] * (M+10)
for i in range(2, M+10):
    if biggest_prime[i] == 0:
        biggest_prime[i] = i
        for j in range(i*i, M+1, i):
            biggest_prime[j] = i

from collections import defaultdict
cntd=defaultdict(int)
for i in range(len(a)):
    num = a[i]
    while num>1:
        p=biggest_prime[num]
        cntd[p]+=1
        while num % p == 0:
            num//=p

flg=False
for c in cntd.values():
    if c==n:
        print("not coprime")
        exit()
    if c>1:
        flg=True
if flg:
    print("setwise coprime")
else:
    print("pairwise coprime")

Solution (Python):
import math

def sieve_of_erastosthenes(num):
    is_prime = [True for i in range(num+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(num**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, num + 1, i):
            is_prime[j] = False
    return [i for i in range(num + 1) if is_prime[i]]

N = int(input())
A = [int(i) for i in input().split()]
ans = math.gcd(A[0], A[1])
tmp = math.gcd(A[0], A[1])
for i in range(2, N):
    ans = math.gcd(ans, A[i])
if ans > 1:
    print('not coprime')
    exit()
maxA = max(A)
l = sieve_of_erastosthenes(maxA)
B = [False for i in range(maxA+1)]
for i in range(N):
    B[A[i]] = True
flag = False
for each in l:
    tmp = each
    counter = 0
    while True:

        if B[tmp]:
            counter += 1
        tmp += each
        if tmp > maxA:
            break
    if counter > 1:
        flag = True
        break


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

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(10**9)


INF=10**18

def solve(N,A):
    maxim = 10**6+10
    spf = np.zeros(maxim+1,dtype=np.int64)

    
    for i in range(maxim):
        spf[i] = i
    
    i = 2
    while i*i <= maxim:
        if spf[i] != i: i += 1; continue
        j = i*i
        while j <= maxim:
            if spf[j] != j: j += i; continue
            spf[j] = i
            j += i
        
        i += 1

    pairwise = True
    allP = set()
    for a in A:

        m  = set()
        n = a
        while n > 1:
            m.add(spf[n])
            n //= spf[n]

        P = m

        no_collapse = len(allP) + len(P)
        for p in P:
            allP.add(p)
        
        res = len(allP)
        if no_collapse != res:
            pairwise = False
            break


    return pairwise

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)]  

    pairwise = solve(N, np.array(A))

    if pairwise:
        print("pairwise coprime")
    else:
        gcm = np.gcd.reduce(A)
        if gcm == 1:
            print("setwise coprime")
        else:
            print("not coprime")


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    
    cc.export('solve', '(i8,i8[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()

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


def facs(n):
    """試し割り法における割る数を生成する。"""
    yield 2
    for x in range(3, n, 2):
        yield x


def main():
    input()  
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 1
    histogram = [0] * MAX_A
    for x in array:
        histogram[x] += 1

    for divider in facs(MAX_A):
        count = sum(histogram[divider::divider])
        if count > 1:
            break
    else:
        return 'pairwise coprime'

    gcd_total = reduce(gcd, array)
    if gcd_total == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


if __name__ == '__main__':
    print(main())

Solution (Python):
import math
from functools import reduce

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

N=int(input())
A=list(map(int,input().split()))
mA = max(A)
D = [-1]*(mA+1)
D[0]=1
D[1]=1
for i in range(2,mA+1):
  if D[i] != -1: continue
  D[i] = i
  cnt = 2*i
  while cnt < mA+1:
    if D[cnt] == -1:
      D[cnt]=i
    cnt += i
done = set()
for a in A:
  tmp = set()
  while a > 1:
    tmp.add(D[a])
    a //= D[a]
  if len(done&tmp) > 0:
    if gcd_list(A) == 1: print('setwise coprime')
    else: print('not coprime')
    exit()
  done |= tmp
print('pairwise coprime')

Solution (Python):
import math
def GCD(a):
    gcd = a[0]
    N = len(a)
    for i in range(1, N):
        gcd = math.gcd(gcd, a[i])
    return gcd


def fact(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
A = list(map(int, input().split()))
hst = [0] * (max(A) + 1)

for a in A:
    F = fact(a)
    for f in F:
        hst[f[0]] += 1
        if hst[f[0]] > 1 and f[0] != 1:
            
            if GCD(A) == 1:
                print("setwise coprime")
            else:
                print("not coprime")
            exit()

print("pairwise coprime")

Solution (Python):
import sys
from math import gcd
input = sys.stdin.readline
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()

def factorize(n):
    d = set()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d.add(m)
        m += 1
    if n > 1:
        d.add(n)
    return d

st = set()
for a in A:
    fac = factorize(a)
    if fac.intersection(st) :
        print('setwise coprime')
        exit()
    st.update(fac)
print('pairwise coprime')

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


MAX_A = 1000000
lowerst_prime = [0] * (MAX_A + 1) 
primes = [] 
count = [0] * (MAX_A + 1) 
for i in range(2, MAX_A + 1): 
    if lowerst_prime[i] == 0:
        lowerst_prime[i] = i
        primes.append(i)
    for p in primes:
        if p > lowerst_prime[i] or i * p > MAX_A:
            break
        lowerst_prime[i * p] = p 

N = int(input())
A = [*map(int, input().split())]
if reduce(gcd, A) != 1:
    print("not coprime")
    exit(0)
for i in range(N):
    while A[i] > 1:
        divide = lowerst_prime[A[i]]
        if count[divide]:
            
            print("setwise coprime")
            exit(0)
        count[divide] += 1
        while A[i] % divide == 0: 
            A[i] //= divide
print("pairwise coprime")

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


MAX_A = 1000000
lowerst_prime = [0] * (MAX_A + 1) 
primes = [] 
count = [0] * (MAX_A + 1) 
for i in range(2, MAX_A + 1): 
    if lowerst_prime[i] == 0:
        lowerst_prime[i] = i
        primes.append(i)
    for p in primes:
        if p > lowerst_prime[i] or i * p > MAX_A:
            break
        lowerst_prime[i * p] = p 

N = int(input())
A = [*map(int, input().split())]
if reduce(gcd, A) != 1:
    print("not coprime")
    exit(0)
for i in range(N):
    while A[i] > 1:
        divide = lowerst_prime[A[i]]
        if count[divide]:
            
            print("setwise coprime")
            exit(0)
        count[divide] += 1
        while A[i] % divide == 0: 
            A[i] //= divide
print("pairwise coprime")

Solution (Python):
from math import gcd

N = int(input())
A = list(map(int,input().split()))
 
flg = 0
l = [0]*(max(A)+1)
for i in A:
  l[i] += 1
a = gcd(A[0],A[1])
for i in range(2,N):
  a = gcd(a,A[i])
for i in range(2,max(A)+1):
  if sum(l[i::i]) > 1:
    flg = 1
    break



if a == 1 and flg == 0:
  print("pairwise coprime ")
elif a == 1 and flg == 1:
  print("setwise coprime")
else:
  print("not coprime")

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
maxA=max(A)
pn=list(range(maxA+1))
n=2
while n*n <= maxA:
  if n == pn[n]:
    for m in range(n, len(pn), n):
      if pn[m] == m:
        pn[m] = n
  n+=1

s=set()
for a in A:
  st = set()
  while a > 1:
    st.add(pn[a])
    a//=pn[a]
  if not s.isdisjoint(st):
    break
  s |= st
else:
  print("pairwise coprime")
  exit()

from math import gcd

n = gcd(A[0], A[1])
for a in A[2:]:
  n=gcd(n,a)
if n == 1:
  print("setwise coprime")
else:
  print("not coprime")

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


MAX_A = 1000000
lowerst_prime = [0] * (MAX_A + 1) 
primes = [] 
count = [0] * (MAX_A + 1) 
for i in range(2, MAX_A + 1): 
    if lowerst_prime[i] == 0:
        lowerst_prime[i] = i
        primes.append(i)
    for p in primes:
        if i * p > MAX_A:
            break
        lowerst_prime[i * p] = p 

N = int(input())
A = [*map(int, input().split())]
if reduce(gcd, A) != 1:
    print("not coprime")
    exit(0)
for i in range(N):
    while A[i] > 1:
        divide = lowerst_prime[A[i]]
        if count[divide]:
            
            print("setwise coprime")
            exit(0)
        count[divide] += 1
        while A[i] % divide == 0: 
            A[i] //= divide
print("pairwise coprime")

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

    M = 10**6+1
    mp = [0]*M
    for a in A:
        mp[a] += 1

    pairwise = 1
    for i in range(2,M):
        if sum(mp[i::i])>1:
            pairwise = 0
            break

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

if __name__ == '__main__':
    main()

Solution (Python):
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

def primes(n):
    is_prime = [-1] * (n + 1)
    is_prime[1]=1
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]!=-1:
            continue
        for j in range(i * 2, n + 1, i):
            if is_prime[j]==-1:
                is_prime[j] = i
    for i in range(n):
        if is_prime[i+1]==-1:
            is_prime[i+1]=i+1
    return is_prime


def factorize(N,prime_list):  
    lst = []
    
    
    while prime_list[N]!=1:
        lst.append(prime_list[N])
        N//=prime_list[N]
    return lst

tmp=a[0]
for i in range(n):
    tmp=math.gcd(tmp,a[i])
if tmp!=1:
    print("not coprime")
    exit()
dic={}
plst=primes(10**6)
for i in range(n):
    lst=factorize(a[i],plst)
    for j in lst:
        if j in dic:
            print("setwise coprime")
            exit()
    for j in lst:
        dic[j]=1
print("pairwise coprime")

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


MAX_A = 1000000
lowerst_prime = [0] * (MAX_A + 1) 
count = [0] * (MAX_A + 1) 

for i in range(2, MAX_A + 1): 
    if lowerst_prime[i] != 0:
        continue
    lowerst_prime[i] = i
    for j in range(i * i, MAX_A + 1, i): 
        if lowerst_prime[j] == 0:
            lowerst_prime[j] = i

N = int(input())
A = [*map(int, input().split())]

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

for i in range(N):
    while A[i] > 1:
        divide = lowerst_prime[A[i]]
        count[divide] += 1
        while A[i] % divide == 0: 
            A[i] //= divide

for i in range(MAX_A + 1):
    if count[i] >= 2:
        print("setwise coprime")
        exit(0)
print("pairwise coprime")

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


MAX_A = 1000000
lowerst_prime = [10**9] * (MAX_A + 1) 
count = [0] * (MAX_A + 1) 

for i in range(2, MAX_A + 1): 
    if lowerst_prime[i] != 10**9:
        continue
    lowerst_prime[i] = i
    for j in range(i * i, MAX_A + 1, i): 
        if lowerst_prime[j] == 10**9:
            lowerst_prime[j] = i

N = int(input())
A = [*map(int, input().split())]

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

for i in range(N):
    while A[i] > 1:
        divide = lowerst_prime[A[i]]
        count[divide] += 1
        while A[i] % divide == 0: 
            A[i] //= divide

for i in range(MAX_A + 1):
    if count[i] >= 2:
        print("setwise coprime")
        exit(0)
print("pairwise coprime")

Solution (Python):

from collections import defaultdict 
import sys
import math 

def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

sys.setrecursionlimit(10**6) 



N = 1000005

lpf = [0 for i in range(N)] 
mobius = [0 for i in range(N)] 



def least_prime_factor(): 

	for i in range(2, N): 

		
		if (lpf[i] == 0): 

			for j in range(i, N, i): 

				
				
				if (lpf[j] == 0): 
					lpf[j] = i 



def Mobius(): 

	for i in range(1, N): 

		
		if (i == 1): 
			mobius[i] = 1
		else: 

			
			if (lpf[ (i // lpf[i]) ] == lpf[i]): 
				mobius[i] = 0

			
			else: 
				mobius[i] = -1 * mobius[i // lpf[i]] 



def gcd_pairs(a, n): 

	
	maxi = 0

	
	fre = [0 for i in range(N)] 

	
	for i in range(n): 
		fre[a[i]] += 1
		maxi = max(a[i], maxi) 

	least_prime_factor() 
	Mobius() 

	
	ans = 0

	
	for i in range(1, maxi + 1): 
		if (mobius[i] == 0): 
			continue

		temp = 0
		for j in range(i, maxi + 1, i): 
			temp += fre[j] 

		ans += temp * (temp - 1) // 2 * mobius[i] 

	
	return ans 



n = int(input())

a = get_array() 
if gcd_pairs(a,n) == (n*(n-1))//2:
    print("pairwise coprime")
else:
    gs = a[0]
    for i in range(1,n):
        gs = math.gcd(gs,a[i])
    if gs == 1:
        print("setwise coprime")
    else:
        print("not coprime")

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


def prime_factor_table(n):
    
    sieve = [i for i in range(n+1)]
    
    for i in range(2, int(n**0.5)+1):
        if sieve[i] == i:
            for j in range(2*i, n+1, i):
                if sieve[j] == j:
                    sieve[j] = i
    return sieve

sieve = prime_factor_table(10**6+1)

def prime_factor(n):
    
    prime = set()
    while n > 1:
        prime.add(sieve[n])
        n //= sieve[n]
    return prime

for i, v in enumerate(a):
    if i == 0:
        tmp = prime_factor(v)
    else:
        prime = prime_factor(v)
        for j in prime:
            if j in tmp:
                if reduce(gcd, a) == 1:
                    print("setwise coprime")
                    exit()
                else:
                    print("not coprime")
                    exit()
            tmp.add(j)
print("pairwise coprime")

Solution (Python):
import math
L = 10**6 + 1

N = int(input())
A = list(map(int, input().split()))
memo = [0] * L
flag = 0 

for a in A:
    memo[a] += 1

for i in range(2, L):
    if sum(memo[i::i]) > 1:
        flag = 1
        break

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

if flag == 0:
    answer = 'pairwise coprime'
elif flag == 1 and g == 1:
    answer = 'setwise coprime'
else:
    answer = 'not coprime'

print(answer)

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

def eratosthenes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    
    return [i for i in range(n+1) if is_prime[i]]

primecount = {}
primenum = [-1] * (A_MAX+1)
for p in eratosthenes(A_MAX):
    primecount[p] = 0
    for i in range(p, A_MAX+1, p):
        primenum[i] = p
    
for a in A:
    while a > 1:
        p = primenum[a]
        while a % p == 0:
            a //= p
        primecount[p] += 1

primecount[1] = 1
cnt = max(primecount.values())

if cnt == 1:    
    print('pairwise coprime')
elif cnt < N:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
M = max(a)+1
if M == 2:
    print("pairwise coprime")
    exit()
count = [0]*(M)
prime = [2,3,5,7,11,13]
for i in range(14,int(M**0.5)+2):
    check = True
    for j in prime:
        if i%j == 0:
            check = False
            break
    if check:
        prime.append(i)

for i in a:
    for j in prime:
        if i < j:
            break
        if i%j==0:
            while i%j == 0:
                i //= j
            count[j] += 1
    if i > 1:
        count[i] += 1

ans = max(count)

if ans == 1:
    print("pairwise coprime")
elif ans == n:
    print("not coprime")
else:
    print("setwise coprime")

Solution (Python):
n=int(input())
import copy
a= [int(x) for x in input().split()]
MAX_A = 10 ** 6 + 1
histogram = [0] * MAX_A
for x in a:
  histogram[int(x)] += 1
for divider in range(2, MAX_A):
  count = 0
  for counted in histogram[divider::divider]:
    count += counted
  if count > 1:
    break
else:
  print('pairwise coprime')
  exit()
from math import gcd
g=gcd(a[0],a[1])
if n==2:
  print('setwise coprime' if g==1 else 'not coprime')
  exit()
for i in range(2,n):
  g=gcd(g,a[i])
if g==1:
  print('setwise coprime')
else:
  print('not coprime')

Solution (Python):
import math

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

def get_primenumber(number):
    prime_list = []
    search_list = list(range(2,number+1))
    
    while search_list[0] <= math.sqrt(number):
        
        
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        
        for i in range(number // head_num):
            index = head_num * (i + 1)
            if D[index] == index:
                D[index] = head_num
        search_list = [num for num in search_list if num % head_num != 0]
    
    prime_list.extend(search_list)
    return prime_list


def factrization_prime(number):
    div = D[number]
    s = math.sqrt(number)
    div_set = set()
    while number > 1:
        number //= div
        div_set.add(div)
        div = D[number]
    if number > 1:
        div_set.add(div)
    for div in div_set:
        ans_array[div] += 1



thre = max(a_array) + 1
ans_array = [0] * thre
D = list(range(thre + 1))

prime_list = get_primenumber(thre)

for a in a_array:
    factrization_prime(a)


max_ans_array = max(ans_array)
if max_ans_array <= 1:
    print('pairwise coprime')
elif max_ans_array < n:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
import sys
import math

if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    check_pairwise()
    check_set()
    return


def check_pairwise():
    active = set()
    for i in range(0, n):
        pp = getprimes(a[i])
        for p in pp:
            if p in active:
                return
            else:
                active.add(p)
    print("pairwise coprime")
    exit()



def check_set():
    active = getprimes(a[0])
    for i in range(1, n):
        if not a[i] % a[i-1] == 0:
            rm = []
            for act in active:
                if not a[i] % act == 0:
                    rm.append(act)
            for r in rm:
                active.remove(r)
                if not active:
                    print("setwise coprime")
                    exit()
    if not active:
        print("setwise coprime")
        exit()
    print("not coprime")
    exit()




def getprimes(num):
    if not num:
        return set()
    if num in primes:
        return set([num])
    pp = set()
    for p in iterprimes:
        if p > int(math.sqrt(num)+2):
            break
        if num % p == 0:
            pp.add(p)
            if num // p in primes:
                pp.add(num // p)

    return pp




def n_primes(n):
    nums = list(range(0, n + 1))
    primes = []
    for i in range(2, n + 1):
        num = nums[i]
        if num != 0:
            primes.append(num)
            for i in range(0, n // num + 1):
                nums[i * num] = 0
    return primes


n = RN()
a = sorted(RA())
iterprimes = n_primes(10 ** 6)
primes = set(iterprimes)
solve()

Solution (Python):
from math import gcd
def eratosthenes(N):
    from collections import deque
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    ret = []
    for i in range(N+1):
        if work[i]:
            ret.append(i)
            for j in range(2* i, N+1, i):
                work[j] = False
    return ret






def main():
    N = int( input())
    A = list( map( int, input().split()))
    g = A[0]
    for a in A:
        g = gcd(a, g)
    if g > 1:
        print("not coprime")
        return
    E = eratosthenes(10**3)
    EE = [0]*len(E)
    R = []
    for a in A:
        for i, e in enumerate(E):
            if a%e == 0:
                if EE[i] > 0:
                    print("setwise coprime")
                    return
                EE[i] = 1
            while a%e == 0:
                a //= e
        if a > 1:
            R.append(a)
    R.sort()
    for i in range(len(R)-1):
        if R[i] == R[i+1]:
            print("setwise coprime")
            return
    print("pairwise coprime")
    
    
if __name__ == '__main__':
    main()

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


class Osak:
    def __init__(self, max_number=10 ** 6):
        self.max_number = max_number
        self.table = list(range(max_number + 1))
        self.calc_minimum_prime()

    def calc_minimum_prime(self):
        self.table[1] = 0
        for base in range(2, self.max_number + 1):
            if self.table[base] != base:
                continue
            for num in range(base, self.max_number+1, base):
                self.table[num] = base

    def judge_is_prime(self, num):
        return self.table[num] == num

    def get_factors(self, num):
        factors = set()
        while num > 1:
            prime = self.table[num]
            factors.add(prime)
            num //= prime
        return factors

    def factorize(self, num):
        factors = defaultdict(int)
        while num > 1:
            prime = self.table[num]
            factors[prime] += 1
            num //= prime
        return factors


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

    osak = Osak(max(A))
    prime_count = defaultdict(int)
    for a in A:
        factors = osak.get_factors(a)
        for factor in factors:
            prime_count[factor] += 1
    
    if not prime_count:
        ans = 1
    else:
        ans = max(prime_count.values())

    if ans == 1:
        print("pairwise coprime")
    elif ans < n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Solution (Python):
import math
L = 10**6 + 1

N = int(input())
A = list(map(int, input().split()))
memo = [0] * L
flag = 0 

for a in A:
    memo[a] += 1

for i in range(2, L): 
    if sum(memo[i::i]) > 1: 
        flag = 1
        break

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

if flag == 0:
    answer = 'pairwise coprime'
elif flag == 1 and g == 1:
    answer = 'setwise coprime'
else:
    answer = 'not coprime'

print(answer)

Solution (Python):
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
pc="pairwise coprime"
sc="setwise coprime"
nc="not coprime"
a.sort()
tmp=a[0]

for i in range(n):
    tmp=math.gcd(tmp,a[i])
if tmp!=1:
    print(nc)
    exit()

dic={}
for i in range(n):
    if a[i] in dic:
        dic[a[i]]+=1
    else:
        dic[a[i]]=1

ans=0
for i in range(a[-1]):
    now=i+1
    cnt=0
    
    for j in range(a[-1]//now):
        if now in dic:
            cnt+=dic[now]
        now+=i+1
    if cnt>1:
        ans=i+1

if ans!=1:
    print(sc)
else:
    print(pc)