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
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union


from math import gcd








from collections import Counter              




















def main():
    Num = Union[int, float]
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    
        
    class Eratos:
        def __init__(self, num: int):
            '''
            O(nlglgn) で num までの素数判定テーブルを作る
            >>> e = Eratos(10)
            >>> e.table
            [False, False, True, True, False, True, False, True, False, False, False]
            '''
            if num < 1:
                raise ValueError(f'Eratos.__init__(): argument should be >= 1. got {num}')
            self.table_max = num
            
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            i = 2
            while i ** 2 <= num:
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    
                        self.table[j] = False
                i += 1   


        def is_prime(self, num: int) -> bool:
            '''
            O(1) で素数判定を行う
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
            '''
            if num < 1:
                raise ValueError(f'Eratos.is_prime(): argument shoule be >= 1. got {num}')
            if num > self.table_max:
                raise ValueError(f'Eratos.is_prime(): exceed table_max({self.table_max}). got {num}')
            return self.table[num]

        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        


    def check_setwise(n, L):
        gcd_memo = L[0]        
        for i in range(n):
            gcd_memo = gcd(L[i], gcd_memo)
        return gcd_memo == 1


    def check_pairwise(n, L):
        eratos = Eratos(10**3+1)
        
        p_list = [p for p in range(2, 10**3+1) if eratos.is_prime(p)]
        
        divided = [0] * n
        memo = set()
        for i in range(n):
            num = L[i]
            for p in p_list:
                if num == 1:
                    break
                if num % p == 0:
                    while num % p == 0:
                        num //= p
                    if p in memo:
                        return False
                    else:
                        memo.add(p)
            divided[i] = num
        
        rem_one = [elm for elm in divided if elm != 1]
        return len(rem_one) == len(set(rem_one))


    n = ii()
    L = lmi()
    if check_pairwise(n, L):
        print('pairwise coprime')
    elif check_setwise(n, L):
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
*a,=map(int, input().split())
mapa=[0]*(10**6+1)

from bisect import bisect_left

n0 = 10**6
primes = set(range(2, n0+1))
for i in range(2, int(n0**0.5+1)):
    primes.difference_update(range(i*2, n0+1, i))
primeind=[0]*(10**6+1)
for p in primes:
    primeind[p]=1

def isPrime(m):
    return primeind[m]==1

def func(m):
    for i in range(2,int(m**0.5)+1):
        if isPrime(m):
            break
        if m%i==0:
            mapa[i]+=1
        while m%i==0:
            m//=i
        if m<i:
            break
    if m>1:
        mapa[m]+=1

for ai in a:
    func(ai)

tmp=max(mapa)

if tmp==n:
    print('not coprime')
elif tmp>1:
    print('setwise coprime')
else:
    print('pairwise coprime')

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

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

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

if gcd_list(A) > 1:
  print("not coprime")
  sys.exit()
  
union = set()
intersection = set()

visited = set()
A_set = set()

flag = False
MAX = 10**6
lim = math.ceil(math.sqrt(MAX))
for a in A:
  
  if a in visited: 
    print("setwise coprime")
    sys.exit()
    flag = True 
    break
  b = a
  p = 2
  while p <= lim and b > 1:
    if p in visited: 
      p += 1
      continue
    if b % p == 0:
      q = p
      for q in range(p,MAX+1,p): 
        visited.add(q)     
    while b % p == 0:
      b = b // p
    p += 1
  if b > 1:
    q = b
    p = b
    for q in range(p,MAX+1,p): 
      visited.add(q) 
      
      

print("pairwise coprime")



"""
def raise_prime(B):
  n = len(B)
  if n == 1:
    
  C = B[0: n//2]
  D = B[n//2:n]
"""


  
  
"""
for a in A:
  p = 2
  while p <= N:
    if p not in visited:
      
      
    
  
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    union.add()
    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
"""

Solution (Python):
MAXN = 1000001
spf = [i for i in range(MAXN)] 
hash1 = [0 for i in range(MAXN)] 

def sieve(): 
	for i in range(4, MAXN, 2): 
		spf[i] = 2

	for i in range(3, MAXN): 
		if i * i > MAXN: 
			break
		if (spf[i] == i): 
			for j in range(i * i, MAXN, i): 
				if (spf[j] == j): 
					spf[j] = i 

def getFactorization(x): 

	while (x != 1): 
		temp = spf[x] 
		if (x % temp == 0): 

			hash1[spf[x]] += 1
			x = x // spf[x] 

		while (x % temp == 0): 
			x = x // temp 

def hasValidNum(arr, n): 

	sieve() 

	for i in range(n): 
		getFactorization(arr[i]) 

	for i in hash1:
		if(i>1):
			return False
	return True

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

n=int(input())
arr=list(map(int,input().split()))
if (hasValidNum(arr, n)): 
	print("pairwise coprime") 
else: 
	g=arr[0]
	for i in range(1,n):
		g=gcd(g,arr[i])
	if(g==1):
		print("setwise coprime") 
	else:
		print("not coprime")

Solution (Python):




def factor_osa(A):
    Max = max(A) + 1
    IsPrime = [True] * Max
    MinFactor = [-1] * Max
    Primes = []
    prim = {}
    dica = {}
    mxa = 0
    IsPrime[0], IsPrime[1] = False, False
    MinFactor[0], MinFactor[1] = 0, 1
    for i in range(2, Max):
        if IsPrime[i]:
            MinFactor[i] = i
            Primes.append(i)
            for j in range(i*2, Max, i):
                IsPrime[j] = False
                if MinFactor[j] == -1:
                    MinFactor[j] = i
    ret = []
    for a in A:
        res = []
        while a != 1:
            prime = MinFactor[a]
            exp = 0
            while MinFactor[a] == prime:
                exp += 1
                a //= prime
            res.append((prime, exp))
            if not prime in dica:
                dica[prime] = 1
            else:
                dica[prime] += 1
            mxa = max(mxa, dica[prime])
        ret.append(res)
    return [ret, mxa]

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

aa = factor_osa(a)

from math import gcd        

def Gcd(lt):
    l = len(lt)
    ret = [1]*l
    ret[0] = lt[0]
    for i in range(1,l):
        ret[i] = gcd(ret[i-1], lt[i])
    return ret

if max(a) == 1:
    print('pairwise coprime')
    exit()

if aa[1] == 1:
    print('pairwise coprime')
elif Gcd(a)[-1]==1:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):

from math import gcd
from functools import reduce
from collections import defaultdict


def calc_factor(n):
    
    min_factor = list(range(n + 1))
    for i in range(2, n + 1):
        if min_factor[i] == i:
            for j in range(2 * i, n + 1, i):
                min_factor[j] = i
    return min_factor


def calc_prime_factor(n, min_factor):
    
    ctr = defaultdict(int)
    while n > 1:
        div = min_factor[n]
        while n % div == 0:
            ctr[div] += 1
            n //= div
    return ctr


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

min_factor = calc_factor(10 ** 6 + 10)
pairwise = True
appeared = set()
for v in X:
    primes = calc_prime_factor(v, min_factor)
    for n in primes:
        if n in appeared:
            pairwise = False
        appeared.add(n)

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

Solution (Python):





"""
"""

from collections import defaultdict
from itertools import accumulate
import bisect

import sys
input = sys.stdin.readline
import math as mt

MAXN = 10**6 +1
  


spf = [0 for i in range(MAXN)] 
  



def sieve(): 
    spf[1] = 1
    for i in range(2, MAXN): 
          
        
        
        spf[i] = i 
  
    
    
    for i in range(4, MAXN, 2): 
        spf[i] = 2
  
    for i in range(3, mt.ceil(mt.sqrt(MAXN))): 
          
        
        if (spf[i] == i): 
              
            
            
            for j in range(i * i, MAXN, i):  
                  
                
                
                if (spf[j] == j): 
                    spf[j] = i 


def getFactorization(x): 
    ret = set([]) 
    while (x != 1): 
        ret.add(spf[x]) 
        x = x // spf[x] 
  
    return ret 


def solve(n,a):
    sieve()
    gcd_primes = getFactorization(a[0])
    seen_primes = set([])
    flag_pcp = True
    for aa in a:
        ps = getFactorization(aa)
        if flag_pcp:
            if not (seen_primes & ps):
                seen_primes |= ps
            else:
                flag_pcp = False
        gcd_primes &= ps
    if flag_pcp:
        print('pairwise coprime')
    elif gcd_primes:
        print('not coprime')
    else:
        print('setwise coprime')





            


            

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import Counter

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

set_A = set(A)
set_flag = len(set_A) != N

counter = Counter(A)
if len(counter) == N or (1 in counter and len(counter) - 1 + counter[1] == N):
    co_prime = True
    max_a = max(A)
    
    coprime = True
    exists = set()
    for i in range(2, max_a + 1):
        flag = False
        for j in range(i, max_a + 1, i):
            if j in set_A:
                if not flag:
                    flag = True
                elif flag:
                    coprime = False
                    break
        if not coprime:
            break
else:
    coprime = False

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

setwise = False
tmp = A[0]
for i in range(N):
    tmp = math.gcd(tmp, A[i])
if tmp == 1:
    setwise = True

if setwise:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
def factorization(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







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



ansN = A[0]
for i in range(1, n):
    ansN = math.gcd(ansN, A[i])
if ansN > 1:
    print('not coprime')
else:
    ans2 = True
    C = [0 for _ in range(10**6+10)]
    for a in A:
        F = factorization(a)

        for f in F:
            if f[0] != 1:
                if C[f[0]] == 0:
                    C[f[0]] = 1
                else:
                    ans2 = False
                    break
        else:
            continue
        break
    if ans2:
        print('pairwise coprime')
    else:
        print('setwise coprime')

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

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

pri_0 = prime_decomposition(a[0])
pri_1 = prime_decomposition(a[1])
ans = pri_0&pri_1

if len(ans):
    for i in range(2, n):
        res = prime_decomposition(a[i])
        ans &= res
        if not ans:
            print('setwise coprime')
            sys.exit()
    print('not coprime')

else:
    ans = pri_0 | pri_1
    for i in range(2, n):
        res = prime_decomposition(a[i])
        for i in res:
            if i in ans:
                print('setwise coprime')
                sys.exit()
        ans |= res
    print('pairwise coprime')

Solution (Python):

import sys
from math import gcd
from functools import reduce
def input(): return sys.stdin.readline().rstrip()
 
def pairwaise(bools):
    for i in range(2,10**6):
        hantei=0
        for j in range(i,10**6+1,i):
            hantei+=bools[j]
        if hantei>1:
            return False
    return True
 
 
def main():
    n=int(input())
    A=list(map(int, input().split()))
    gcds=reduce(gcd,A)
    if gcds>1:
        print('not coprime')
    else:
        bools=[0]*(10**6+5)
        for AA in A:
            if bools[AA]==1 and AA!=1:
                print('setwise coprime')
                exit()
            bools[AA]+=1
        if pairwaise(bools):
            print('pairwise coprime')
        else:
            print('setwise coprime')
 
    
    
 
 
if __name__ == '__main__':
    main()

Solution (Python):
from math import gcd
from collections import defaultdict
def main():
    n = int(input())
    a = list(map(int,input().split()))
    dic = defaultdict(bool)
    pairW = True
    setW = a[0]
    for i in a:
        t = 1
        while t**2 <= i:
            if i % t == 0:
                if (t != 1 and dic[t]) or (i//t != 1 and dic[i//t]):
                    pairW = False
                    break
                else:
                    dic[t] = True
                    dic[i//t] = True
            t += 1
        setW = gcd(setW,i)
    

    if pairW:
        print("pairwise coprime")
        return
    elif setW == 1:
        print("setwise coprime")
        return
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N = getN()
A = getList()

pair = True
semi = True


judge = [0] * (10 ** 6 + 1)
num_list = [0] * (10 ** 6 + 1)

for i in A:
    judge[i] += 1

for i in range(2, 10 ** 6 + 1):
    if num_list[i] == 1:
        continue
    cnt = 0
    for j in range(i, 10 ** 6 + 1, i):
        num_list[j] = 1
        cnt += judge[j]
    if cnt > 1:
        if cnt == N:
            semi = False
        pair = False

if pair and semi:
    print('pairwise coprime')
elif semi:
    print('setwise coprime')
else:
    print('not coprime')

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

def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

A.sort()
M = A[-1]
d = {}
ans = 0

for i in range(N):
    if A[i] not in d:
        primes = prime_decomposition(A[i])
        for p in primes:
            for j in range(1,M//p+1):
                d[j*p] = 0
    else:
        ans = 1
        break
if ans == 0:
    print('pairwise coprime')
else:
    def gcd(a, b):
    	while b:
    		a, b = b, a % b
    	return a
    a = A[0]
    for i in range(N):
        a = gcd(a,A[i])
    if a==1:
        print('setwise coprime')
    else:
        print('not coprime')

Solution (Python):
def seachPrimeNum(N):
    max = int(N**.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

P=seachPrimeNum(5*10**5)

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

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)
    return arr

factorization(24) 

n=int(input())
A=[int(i) for i in input().split()]
DIC={i:0 for i in range(1,10**6+1)}
for ele in A:
    DIC[ele]+=1
pair=True
setw=True
if n!=len(A):
    pair=False

for pri in P:
    cnt=0
    for i in range(pri,10**6+1,pri):
        cnt+=DIC[i]
    if cnt>1:
        pair=False
    if cnt==len(A):
        setw=False

if pair:
    print("pairwise coprime")
elif setw:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):

import sys
from collections import defaultdict
from fractions import gcd
N=int(sys.stdin.readline().strip())
A=map(int, sys.stdin.readline().split())

def factorization(n):
    arr=set()
    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.add(i)

    if temp!=1:
        arr.add(temp)

    if arr==[]:
        arr.add(n)

    return arr

pairwise_coprime=True

SOINSU=defaultdict(lambda: 0)

setwise_coprime=None
for i,a in enumerate(A):
    
    if pairwise_coprime==False:
        pass
    else:
        f=factorization(a)
        for x in f:
            if SOINSU[x]==1:
                pairwise_coprime=False
                break
            SOINSU[x]=1
    
    if i==0:
        setwise_coprime=a
    else:
        setwise_coprime=gcd(setwise_coprime,a)

if pairwise_coprime==True:
    print "pairwise coprime"
elif setwise_coprime==1:
    print "setwise coprime"
else:
    print "not coprime"

Solution (Python):
import sys
n=int(input())
A=[int(i) for i in input().split()]

N=10**6
spf = [i for i in range(N+1)]

for i in range(2,N):
    if i**2>N:
        break
    if spf[i] == i:
        for j in range(i**2,N+1,i):
            if spf[j] == j:
                spf[j] = i

def get(n):
    ps = set()
    while n != 1:
        ps.add(spf[n])
        n //= spf[n]
    return ps


f2=True

n0 = list(get(A[0]))
K=set(n0)
J=set(n0)

for a in A[1:]:
    res = get(a)
    
    
    if len(res) != 0:
        K &= res
        
    if len(J & res) !=0:
        f2 = False
        
    if len(res) != 0:
        J |= res
        

        
if (1 in A) or len(K) == 0:
    f1 = True
else:
    f1 = False
    
if f1:
    if f2:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not 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 math import gcd



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

    return divisors

def solve():
    N = II()
    A = LI()
    mx = max(A)
    A = sorted(A, reverse=True)
    
    g = A[0]
    flag_pc = True
    F = [0] * (mx+1)
    ff = True
    for a in A:
        g = gcd(g, a)
        
        if g != 1:
            flag_pc = False
        
        
        if F[a] > 0 and a != 1:
            ff = False

        if ff:
            for j in range(1, int(a**0.5)+1):
                if a % j == 0:
                    if F[j] > 0 and j != 1:
                        ff = False
                        break
                    F[j] += 1

                    if j != (a//j):
                        if F[a//j] > 0 and (a//j) != 1:
                            ff = False
                            break
                        F[a//j] += 1
    
    

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


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


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

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

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

    return arr


def can_factorization(n: int):
    if n == 1:
        return []  
    
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  
        if temp % i == 0:
            arr.append(i)

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

    
    

    return arr


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
import random
from math import gcd


N = a_int()
A = ints()
random.shuffle(A)






g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  
for a in A:
    g_set = gcd(g_set, a)
    if flg:
        for p, n in factorization(a):
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n








if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Solution (Python):
import math as mt
I=lambda:list(map(int,input().split()))
mod=10**9
n,=I()
l=I()
x=0
y=0
temp=l[0]
for i in range(1,n):
	temp=mt.gcd(temp,l[i])
N=10**6+3
ss=[0]*(N)
ss[0]=1
for i in range(2,N):
	if ss[i]==0:
		ss[i]=i
		for j in range(2*i,N,i):
			ss[j]=i
if temp!=1:
	print("not coprime")
else:
	pos=1
	visi=[0]*N
	for i in range(n):
		now=l[i]
		while now>1:
			te=ss[now]
			if visi[te]:
				pos=0
				break
			while now%te==0:
				now//=te
			visi[te]=1
		if not pos:
			break
	if pos:
		print("pairwise coprime")
	else:
		print("setwise coprime")

Solution (Python):
import sys
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))


def main():
	MAXN = 1000001
	spf = [0 for i in range(MAXN)] 
	
	def sieve(): 
		spf[1] = 1
		for i in range(2, MAXN):  
			spf[i] = i 

		for i in range(4, MAXN, 2): 
			spf[i] = 2

		for i in range(3, ceil(sqrt(MAXN))): 
			
			if (spf[i] == i): 
				
				for j in range(i * i, MAXN, i): 
					
					if (spf[j] == j): 
						spf[j] = i
	sieve()
	n = int(input()); arr = read()
	gcd_ = arr[0]
	check = [0]*(10**6 +1)
	f1 = 0; f2 = 1
	for i in arr:
		gcd_ = gcd(gcd_, i)
		
		ret = []
		flag = 1
		while (i != 1):
			if check[spf[i]]:
				flag = 0
			ret.append(spf[i]) 
			i = i // spf[i]
		for j in ret:check[j] = 1
		
		
		f1 += flag; f2 &= flag

	

	if f2:print("pairwise coprime")
	elif gcd_ == 1:print("setwise coprime")
	else:print("not coprime")



	



if __name__ == "__main__":
	main()

Solution (Python):
import math
import numpy as np

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



def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

prime_num = set(get_sieve_of_eratosthenes_new(999984))

def pairwise_coprime():
    gcd = dict()
    for a in A:
        if a in prime_num:
            if not (a in gcd):
                gcd[a] = 1
            else:
                return False
        else:
            tmp = a
            for p in prime_num:
                if tmp == 1:
                    break
                

                if tmp % p == 0:
                    if not(p in gcd):
                        gcd[p] = 1
                    else:
                        return False
                    
                    while tmp % p == 0:
                        tmp //= p
    
    
    return True
                


def setwise_coprime():
    gcd = A[0]
    for i in range(1, N):
        gcd = math.gcd(gcd, A[i])
        
        if gcd == 1:
            break
    
    if gcd == 1:
        return True
    else:
        return False

if pairwise_coprime():
    print("pairwise coprime")
elif setwise_coprime():
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):


import copy
import random
import bisect 
import fractions 
import math
import sys
import collections
from decimal import Decimal 

mod = 10**9+7
sys.setrecursionlimit(mod) 

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

"""
pairwise coprime 1,3,7,10
setwise coprime 2,3,4,10


coprimeかどうかで全部やる
"""

def primes(n): 
    cnt=collections.defaultdict(int)
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            while n%i==0:
                cnt[i]+=1
                n//=i
    if n!=1:
        cnt[n]+=1
    return cnt


def solve():
    gcd = A[0]
    for a in A:
        gcd = math.gcd(gcd, a)
    if gcd != 1:
        return "not coprime"

    history = {}
    for i in range(10**6):
        history[i] = 0

    for a in A:
        d = primes(a)
        for key in d.keys():
            history[key] += 1
            if history[key] > 1:
                return "setwise coprime"
    return "pairwise coprime"
 
    
print(solve())

Solution (Python):
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy


MOD = 10 ** 9 + 7



n = int(input())
List = list(map(int, input().split()))
N = max(List)
A = defaultdict(int)
for e in List:
    A[e] += 1
furui = [True]*(N+1)

state = "pairwise coprime"
for i in range(2, N+1):
    if not furui[i]:
        continue
    count = 0
    k = i
    while k <= N:
        if k in A:
            count += A[k]
            if count >= 2:
                
                state = "setwise coprime"
            if count == n:
                print("not coprime")
                exit()

        furui[k] = False
        k += i

print(state)

Solution (Python):
from math import gcd
n=int(input())
a=list(map(int,input().split()))
a.sort()
lis=[False]*(10**6+1)
ok=True
d=dict()
for num in a:
    if num in d:
        d[num]+=1
    else:
        d[num]=1
for num in range(2,10**6+1):
    if lis[num]:
        continue
    cnt=0
    for i in range(num,10**6+1,num):
        lis[i]=True
        if i in d:
            cnt+=d[i]
    if cnt>=2:
        ok=False
if ok:
    print("pairwise coprime")
else:
    g=a[0]
    for num in a:
        g=gcd(g,num)
    if g==1:
        print("setwise coprime")
    else:
        print("not coprime")

Solution (Python):

import sys
from math import gcd
M = 10**6
def main(N, A):
    g = 0
    for a in A:
        g = gcd(g, a)
    if g > 1:
        print('not coprime')
        return

    u = [False] * (M + 1)
    cc = [0] * (M + 1)
    for a in A:
        cc[a] += 1
    for n in range(2, M + 1):
        if u[n]: continue
        c = 0
        for nn in range(n, M + 1, n):
            u[nn] = True
            c += cc[nn]
        if c >= 2:
            print('setwise coprime')
            return
    print('pairwise coprime')

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)