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):
from math import gcd
n = int(input())
a = list(map(int, input().split()))
g = a[0]
for i in range(1, n):
    g = gcd(g, a[i])
if g == 1:
    p = [1] * (10 ** 6 + 1)
    r = [0] * (10 ** 6 + 1)
    p[0], p[1] = 0, 0
    r[0] = 0
    r[1] = 1
    for i in range(2, 10 ** 6 + 1):
        if p[i]:
            r[i] = i
            for j in range(i * 2, 10 ** 6 + 1, i):
                p[j] = 0
                if r[j] == 0:
                    r[j] = i
    t = [0] * (10 ** 6 + 1)
    for x in a:
        ps = []
        while x > 1:
            if t[r[x]]:
                print('setwise coprime')
                exit(0)
            ps.append(r[x])
            x //= r[x]
        for p in ps:
            t[p] = 1
    print('pairwise coprime')
else:
    print('not coprime')

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

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

is_prime = [True] * 1100000

is_prime[0] = is_prime[1] = False

for i in range(2, 1100000):
    if not is_prime[i]:continue
    for j in range(i*i, 1100000, i):
        is_prime[j] = False

small_prime = [p for p in range(1100) if is_prime[p]]
        
g = 0

for a in A:
    g = gcd(g, a)

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

used = [False] * 1100000
primes = [a for a in A if is_prime[a]]
for p in primes:
    used[p] = True

not_primes = [a for a in A if not is_prime[a]]

for a in not_primes:
    for p in small_prime:
        if a == 1:break
        if a % p != 0:continue
        if used[p]:
            print("setwise coprime")
            exit()
        used[p] = True
        while a % p == 0:
            a //= p
    if a > 1:
        if used[a]:
            print("setwise coprime")
            exit()
        used[a] = True

print("pairwise coprime")

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

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

import math

gall=a[0]
for i in a:
    gall=math.gcd(gall,i)

M=10**6
if gall==1:
    check=True
    sa=set()
    for i in a:
        if not i in sa:
            sa.add(i)
        else:
            if not i==1:
                check=False
    for i in range(2,M+1):
        temp=i
        count=0
        while temp<=M:
            if temp in sa:
                count+=1
            temp+=i
        if count>=2:
            check=False

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

else:
    print('not coprime')

Solution (Python):
def main():
    N = int(input())
    *A, = map(int, input().split())

    B = [0] * (10 ** 6 + 1)
    for x in A:
        B[x] += 1

    setwise = False

    d = 2
    e = d
    cnt = 0
    while e <= 10 ** 6:
        if B[e]:
            cnt += B[e]
        e += d
    if cnt == N:
        print('not coprime')
        return
    elif cnt > 1:
        setwise = True

    d = 3
    while d <= 10 ** 6:
        e = d
        cnt = 0
        while e <= 10 ** 6:
            if B[e]:
                cnt += B[e]
            e += d
        if cnt == N:
            print('not coprime')
            return
        elif cnt > 1:
            setwise = True
        d += 2

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


if __name__ == '__main__':
    main()

Solution (Python):
import math
n=int(input())
a=list(map(int,input().split()))
m=(10**6+1)
b=[-1]*m
g=a[0]
for i in a:
    g=math.gcd(g,i)
for i in range(2,m):
    tmp=i
    while tmp<m:
        if b[tmp]==-1:
            b[tmp]=i
        tmp+=i
def factorize(k):
    l=[]
    while k>1:
        l.append(b[k])
        k//=b[k]
    return l
p=set()
for i in a:
    l=factorize(i)
    for j in l:
        if j in p:
            if g==1:
                print('setwise coprime')
            else:
                print('not coprime')
            exit()
    for j in l:
        p.add(j)
print('pairwise coprime')

Solution (Python):
import sys
from math import gcd
input = sys.stdin.buffer.readline

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


def primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

p = primes(1003)



g = a[0]

for e in a:
    g = gcd(g,e)


if g != 1:
    print("not coprime")
else:
    s = set()
    for e in a:
        if e == 1:
            continue
        if e in s:
            print("setwise coprime")
            exit()
        for d in p:
            if e < d:
                break
            if e%d == 0:
                d2 = e//d
                if d in s:
                    print("setwise coprime")
                    exit()
                s.add(d)
                if d2 > 1003:
                    if d2 in s:
                        print("setwise coprime")
                        exit()
                    s.add(d2)
        s.add(e)
    print("pairwise coprime")

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


N = I()
A = LI()

from math import gcd

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

if g != 1:
    print('not coprime')
    exit()

B = []
for i in range(N):
    if A[i] != 1:
        B.append(A[i])
N = len(B)

if N == 0:
    print('pairwise coprime')
    exit()

primes = [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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

if N > 78498:
    print('setwise coprime')
    exit()


C = [0]*(10**6+1)

for i in range(N):
    b = B[i]
    for p in primes:
        if b % p == 0:
            if C[p] == 1:
                print('setwise coprime')
                exit()
            else:
                C[p] = 1
            while b % p == 0:
                b //= p
    if b != 1:
        if C[b] == 1:
            print('setwise coprime')
            exit()
        else:
            C[b] = 1

print('pairwise coprime')

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


X = A[:]
while len(X) > 1:
    X.append(gcd(X.pop(), X.pop()))


def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


S = set()
pairwise_coprime_flg = True
for a in A:
    s = set(prime_factorization(a))
    for v in s:
        if v in S:
            pairwise_coprime_flg = False
        S.add(v)
    if not pairwise_coprime_flg:
        break

if pairwise_coprime_flg:
    print('pairwise coprime')
elif X[0] == 1:
    print('setwise coprime')
else:
    print('not coprime')

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

s=set()
f=1
for x in a:
	if f==0:
		break
	if x>1:
		r=int(x**0.5+1e-8)+1
		for i in range(2,r):
			if x%i==0:
				while x%i==0:
					x//=i
				if i in s:
					f=0
					break
				else:
					s.add(i)
		if x>1:
			if x in s:
				f=0
				break
			else:
				s.add(x)

if f:
	print("pairwise coprime")
	exit()
p=a[0]
from math import gcd
for x in a:
	p=gcd(p,x)
if p==1:
	print("setwise coprime")
else:
	print("not coprime")

Solution (Python):
from math import gcd

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


gcd_num = a[0]
for ai in a[1:]:
    gcd_num = gcd(gcd_num,ai)

if(gcd_num > 1):
    print('not coprime')
    exit()

def sieve(n):
    if( n <= 1):
        return []
    elif(n==2):
        return [2]

    primes = [2]
    len_list = (n+1)//2
    len_sqrt = int(len_list**0.5) + 1
    flags = [True] * len_list
    flags[0] = False
    for i in range(len_sqrt):
        if(flags[i]):
            start = ((i*2+1)**2)//2
            for j in range( start, len_list, i*2+1):
                flags[j] = False
    return [2] + [i*2+1 for i in range(len_list) if flags[i]]

p_6 = set(sieve(10**6))
p_3 = sieve(10**3)

use = [0] * (10**6+1)

for ai in a:
    if(ai==1):
        continue
    divs = []
    for p in p_3:
        if(ai%p==0):
            divs.append(p)
            while(ai%p==0):
                ai//=p
    if(ai != 1):
        divs.append(ai)

    for di in divs:
        if(use[di] != 0):
            print('setwise coprime')
            exit()
        use[di] = 1

print('pairwise coprime')

Solution (Python):
def examA():
    D,T,S = LI()
    if (D-1)//S<T:
        ans = "Yes"
    else:
        ans = "No"
    print(ans)
    return

def examB():
    S = SI()
    T = SI()
    s = len(S)
    t = len(T)
    ans = t
    for i in range(s-t+1):
        cnt = 0
        for j in range(t):
            if S[i+j]!=T[j]:
                cnt += 1
        ans = min(ans,cnt)

    print(ans)
    return

def examC():
    N = I()
    A = LI()
    S = sum(A)
    cnt = 0
    for a in A:
        cnt += (S-a)*a
        cnt %= mod
    ans = cnt * pow(2,mod-2,mod) % mod
    print(ans)
    return

def examD():
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            

        def reset(self):
            self.parent = [-1] * len(self.parent)

        def find(self, x):
            
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            
            return self.find(x) == self.find(y)

        def size(self, x):
            
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            
            return self.parent[x] < 0

        def roots(self):
            
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            
            return len(self.roots())

        def all_group_members(self):
            
            return {r: self.members(r) for r in self.roots()}
    N, M = LI()
    uf = UnionFind(N)
    for _ in range(M):
        a, b = LI()
        a -= 1; b -= 1
        uf.unite(a,b)
    cnt = 0
    for i in range(N):
        cnt = max(cnt,uf.size(i))

    ans = cnt
    print(ans)
    return

def examE():
    def gcd(x, y):
        if y == 0:
            return x
        while (y != 0):
            x, y = y, x % y
        return x

    def primes(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]]

    N = I()
    A = LI()
    cur = A[0]
    for i in range(1,N):
        cur = gcd(cur,A[i])
        if cur==1:
            break
    if cur!=1:
        print("not coprime")
        return

    n = max(A)

    P = primes(n)

    

    D = [False]*(n+1)
    for a in A:
        if a==1:
            continue
        if D[a]:
            print("setwise coprime")
            return
        D[a] = True

    for p in P:
        flag = False
        cur = 1
        while (cur * p <= n):
            if D[cur*p]:
                if flag:
                    print("setwise coprime")
                    return
                flag = True

            cur += 1

    print("pairwise coprime")
    return

def examF():

    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
from collections import Counter


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


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

m = max(a)
is_prime = [True] * (m + 1)
cnt_a = [0] * (m + 1)
for i in range(n):
    cnt_a[a[i]] += 1

is_pairwise_coprime = True
for i in range(2, m // 2 + 1):
    if is_prime[i]:
        cnt = cnt_a[i]
        for j in range(2, m // i + 1):
            cnt += cnt_a[i * j]
            is_prime[i * j] = False
        if cnt > 1:
            is_pairwise_coprime = False
            break

gcd_all = a[0]
for i in range(1, n):
    gcd_all = GCD(gcd_all, a[i])
is_setwise_coprime = gcd_all == 1

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

Solution (Python):
from math import gcd
from functools import reduce
def osa_k(n=10**6):
  p=list(range(n+1))
  for i in range(2,int(n**.5)):
    if p[i]<i:continue
    for j in range(i*i,n+1,i):
      if p[j]==j:p[j]=i
  return p
def fact_o(n):
  a=[]
  f=0
  while n>1:
    if f!=p[n]:ans[p[n]]+=1
    f=p[n]
    n//=p[n]
  return 0
p=osa_k()
n=int(input())
a=list(map(int,input().split()))
ans=[0]*(10**6+1)
for i in a:
  fact_o(i)
if max(ans)<=1:print('pairwise coprime')
elif reduce(gcd,a)==1:print('setwise coprime')
else:print('not coprime')

Solution (Python):
from math import gcd

















def factorization(n):
    from collections import Counter
    arr = Counter()
    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[i] = cnt

    if temp != 1:
        arr[temp] = 1

    if len(arr.keys()) == 0 and n != 1:
        arr[n] = 1

    return arr


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


tmp = 0
for a in A:
    tmp = gcd(tmp, a)
isSetwise = (tmp == 1)



M = 10 ** 6
sieve = [0] * (M + 1)
for a in A:
    if sieve[a] == 1:
        isPairwise = False
        break
    else:
        arr = factorization(a)
        for p in arr.keys():
            np = p
            while np <= M:
                sieve[np] = 1
                np += p
else:
    isPairwise = True


if isPairwise:
    ans = 'pairwise coprime'
elif isSetwise:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

Solution (Python):
import math


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


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):
        def f(x): return (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


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

a = A[0]
p = set(primeFactor(A[0]).keys())
flg = False

for i in range(1, N):
    a = math.gcd(a, A[i])
    for x in primeFactor(A[i]):
        if x in p:
            flg = True
        else:
            p.add(x)


if a >= 2:
    print('not coprime')
elif flg:
    print('setwise coprime')
else:
    print('pairwise coprime')

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

def factors(n):
    f=set()
    i=2
    while i*i<=n:
        if n%i==0:
            n//=i
            f.add(i)
        else:
            i+=1
    if n>1:
        f.add(n)
    return f

def list_gcd(A:list):
    return reduce(gcd,A)

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

A_gcd=list_gcd(A)

p=set()
coprime=False
for a in A:
    f=factors(a)
    if len(f&p)>0:
        coprime=True
        break
    else:
        p|=f

if A_gcd==1:
    if coprime:
        print("setwise coprime")
    else:
        print("pairwise coprime")
else:
    print("not coprime")

Solution (Python):

import sys
input = sys.stdin.buffer.readline
from math import gcd

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


def primes(M):
    B = set(A)
    if (1 in B and len(A) != len(B) + A.count(1)-1) or (not 1 in B and len(A) != len(B)):
        return False
    ok = True
    is_prime = [-1 for _ in range(M+1)]
    for m in range(2, M+1):
        if is_prime[m] == -1:
            is_prime[m] = 1
            cnt = 0
            if m in B: cnt += 1
            l = 2
            while m*l <= M:
                if m*l in B:
                    cnt += 1
                is_prime[m*l] = 0
                l += 1
            if cnt > 1:
                ok = False
                break
    return ok

def check():
    k = A[0]
    for a in A:
        k = gcd(a, k)
    return k == 1

if primes(10**6):
    ans = "pairwise coprime"
elif check():
    ans = "setwise coprime"
else:
    ans = "not coprime"
print(ans)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))

import math

def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = math.gcd(a,l[i])
        if a == 1:
            return 1
    return a

res = gcdlist(lst1)
if res != 1:
    print("not coprime")
    exit()


def eratosthenes(n): 
    if n < 2: 
        return []
    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] 
"""素因数分解"""
def get_prime(n):
    b = 2
    fct = []
    while b*b <= n:
        while n % b == 0:
            n //= b
            if not b in fct:
                fct.append(b)
        b += 1
    if n > 1:
        fct.append(n)
    return fct
prime = eratosthenes(10**6)
prime_arr = [0]*10**6
for i in prime:
    prime_arr[i] = 1

for i in lst1:
    if prime_arr[i] == 1:
        prime_arr[i] = -1
    elif prime_arr[i] == -1:
        print("setwise coprime")
        exit()
    else:
        ret = get_prime(i)
        for i in ret:
            if prime_arr[i] == 1:
                prime_arr[i] = -1
            else:
                print("setwise coprime")
                exit()

print("pairwise coprime")

Solution (Python):
def gcd(a, b):
    while b: a, b = b, a % b
    return a
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 = {}
    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:return {n} 
    return set(ret)
def main():
    n=int(input())
    a=list(map(int,input().split()))
    g=a[0]
    for i in a[1:]:g=gcd(g,i)
    if g!=1:
        print("not coprime")
        exit()
    ans=0
    s=set()
    for i in a:
        p=primeFactor(i)
        ans+=len(p)
        s|=p
    if ans!=len(s):print("setwise coprime")
    else:print("pairwise coprime")
if __name__ == "__main__":
    main()

Solution (Python):
def main():

    from math import gcd
    import sys
    input = sys.stdin.buffer.readline
    n = int(input())
    alst = list(map(int, input().split()))
    aa = alst[0]
    for a in alst:
        aa = gcd(aa, a)
    if aa != 1:
        print("not coprime")
        exit()
    
    max_n = 10 ** 3 + 1
    div = [True for _ in range(max_n)]
    div[0] = div[1] = False
    prime_lst = []
    for i in range(2, int(max_n ** 0.5 + 1)):
        if not div[i]:
            continue
        prime_lst.append(i)
        for j in range(i * 2, max_n, i):
            div[j] = False
    tf = [False for _ in range(max_n)]
    for i in range(n):
        for pr in prime_lst:
            if alst[i] % pr == 0:
                if tf[pr]:
                    print("setwise coprime")
                    exit()
                while alst[i] % pr == 0:
                    alst[i] //= pr
                    tf[pr] = True
    alst.sort()
    bef = 1
    for a in alst:
        if a == 1:
            continue
        elif a == bef:
            print("setwise coprime")
            exit()
        bef = a
    print("pairwise coprime")
main()

Solution (Python):
from itertools import groupby

class Osa_k:
    def __init__(self, n_max):
        self.min_factor = min_factor = list(range(n_max+1))
        for i in range(2, int(n_max**0.5)+1):
            if min_factor[i] == i:
                for j in range(i*i, n_max+1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1  
        res = [2] * n_twoes
        n >>= n_twoes
        while n > 1:
            p = min_factor[n]
            res.append(p)
            n //= p
        return res

def main():
    N = int(input())
    A = list(map(int, input().split()))
    osa_k = Osa_k(1010101)
    Factors = [osa_k(a) for a in A]
    factors = Factors[0]
    st0 = set(factors)  
    st1 = set(factors)  
    pairwise = True
    for factors in Factors[1:]:
        st = []
        for f, _ in groupby(factors):
            if f in st1:
                pairwise = False
            else:
                st1.add(f)
            st.append(f)
        st0 &= set(st)
    if pairwise:
        print("pairwise coprime")
    elif not st0:
        print("setwise coprime")
    else:
        print("not coprime")

main()

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

class Factorize:
    def __init__(self):
        self.primes = Counter()

    def add_target(self, n):
        for i in range(2, int(n**0.5)+1):
            while n%i==0:
                self.primes[i] += 1
                n //= i
            if not n:
                break
        if n>1:
            self.primes[n] += 1
    
    def get_result(self):
        return dict(self.primes)

N = int(input())
*A, = map(int, input().split())
def f():
    cnt = Counter()
    for i in A:
        ins = Factorize()
        ins.add_target(i)
        res = ins.get_result()
        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 *

def gcd2(array):
    temp = array[0]
    for a in array[1:]:
        temp = gcd(temp, a)
    return temp

def prime_factors(n):       
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i             
    if n > 1:
        yield n

N = int(input())
A = list(map(int, input().split()))
f1 = False
if gcd2(A) == 1:
    f1 = True
A.sort()
M = A[-1]
P = set()
f2 = True
for a in A:
    Q = set(prime_factors(a))
    if P & Q:
        f2 = False
        break
    P |= Q
if f2:
    print("pairwise coprime")
elif f1:
    print("setwise coprime")
else:
    print("not coprime")

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

def prime_factor(x) :
  ret = dict()
  if x % 2 == 0 :
    ret[2] = 0
    while x % 2 == 0 :
      x //= 2
      ret[2] += 1
          
  i = 3
  while i * i <= x :
    if x % i == 0 :
      ret[i] = 0
      
      while x % i == 0 :
        x //= i
        ret[i] += 1
    i += 2
      
  if x != 1 :
    ret[x] = 1
  
  return ret

def pairwise() :
  done = set()
  for a in A :
    for k in prime_factor(a).keys() :
      if not k in done :
        done.add(k)
      else :
        return False
  return True
    
def setwise() :
  done = set(prime_factor(A[0]).keys())
  for a in A[1:] :
    done &= set(prime_factor(a).keys())
    if len(done) == 0 :
      return True
  return False
  
if pairwise() :
  print('pairwise coprime')
elif setwise() :
  print('setwise coprime')
else :
  print('not coprime')

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def enum_primes(n):
    flag_num = (n + 1) // 2
    prime_flag = [True] * flag_num

    for num in range(3, int(n ** 0.5) + 1, 2):
        idx = (num - 1) // 2 - 1
        if prime_flag[idx]:
            for j in range(idx + num, flag_num, num):
                prime_flag[j] = False

    primes = [2]
    temp = [(i + 1) * 2 + 1 for i in range(flag_num) if prime_flag[i]]
    primes.extend(temp)

    return primes


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    primes = enum_primes(10 ** 6 + 1)

    def judge():
        seq = [False] * (10 ** 6 + 1)
        A.sort()

        for x in A:
            if x == 1:
                continue
            if seq[x]:
                return False
            seq[x] = True

        for prime in primes:
            cnt = 0
            for i in range(prime, 10 ** 6 + 1, prime):
                if seq[i]:
                    cnt += 1
            if cnt > 1:
                return False
        return True

    if judge():
        print("pairwise coprime")
    else:
        from math import gcd
        cur = A[0]
        for x in A[1:]:
            cur = gcd(cur, x)

        if cur == 1:
            print("setwise coprime")
        else:
            print("not coprime")


if __name__ == '__main__':
    main()