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

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import sys
import numpy as np

def solve(N, A):
    def osa_k_construct(n_max):
        min_factor = np.arange(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
        return min_factor

    def osa_k_factorize(min_factor, n):
        min_factor = min_factor
        
        
        
        res = [0]*0
        while n > 1:
            p = min_factor[n]
            res.append(p)
            n //= p
        return res

    osa_k = osa_k_construct(1010101)
    Factors = [osa_k_factorize(osa_k, a) for a in A]
    factors = Factors[0]
    st0 = set(factors)  
    st1 = set(factors)  
    pairwise = True
    for factors in Factors[1:]:
        st = set(factors)
        for f in st:
            if f in st1:
                pairwise = False
            else:
                st1.add(f)
        st0 &= st
    if pairwise:
        print("pairwise coprime")
    elif not st0:
        print("setwise coprime")
    else:
        print("not coprime")

numba_compile([
    [solve, "void(i8,i8[:])"]
])

def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    A = np.array(input().split(), dtype=np.int64)
    solve(N, A)

main()

Solution (Python):
from math import gcd
def fastprimes(n):
    p = [i for i in range(n+1)]
    for i in range(2,int(n**0.5+1)):
        if p[i] == i:
            for j in range(i,n+1,i):
                p[j] = i
    return p
p = fastprimes(10**6)
n = int(input())
a = list(map(int,input().split()))
c = [0]*10**6
g = 0
for i in a:
    g = gcd(g,i)
    b = {0}
    while p[i] != i:
        b.add(p[i])
        i //= p[i]
    b.add(p[i])
    for j in b:
        c[j] += 1
f = 1
for i in c[2:]:
    if i>1:
        f = 0

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

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from functools import reduce
from math import gcd
def resolve():
    n = int(input())
    A = list(map(int, input().split()))

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

    M = max(A)
    sieve = list(range(M + 1))
    sieve[0] = sieve[1] = INF
    for p in range(2, M + 1):
        if sieve[p] != p:
            continue
        for i in range(2 * p, M + 1, p):
            sieve[i] = min(sieve[i], p)

    used = set()
    for a in A:
        primes = set()
        while a > 1:
            p = sieve[a]
            primes.add(p)
            a //= p
        for p in primes:
            if p in used:
                print("setwise coprime")
                return
            used.add(p)

    print("pairwise coprime")
resolve()

Solution (Python):
def arrayF(n): 
    F=[0]*(n+1) 
    i=2 
    while i*i<=n:
        if F[i] == 0: 
            k=i*i
            while k <= n:
                if F[k] == 0:
                    F[k] = i
                k += i
        i += 1 
    return F


def factorization(x, F): 
    primeFactors = []
    while F[x] > 0:
        primeFactors.append(F[x])
        x //= F[x] 
    if x != 1:
        primeFactors.append(x)
    return set(primeFactors)

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

amax = max(A)
F  = arrayF(amax)

P = [0] *  (amax+1)
for a in A:
    for p in factorization(a,  F):
        P[p] += 1
p_max = max(P)
if  p_max <= 1:
    print('pairwise coprime')
elif  p_max <  n:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
N = int(input())
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in map(int, input().split()):
  counts[a] += 1

max_count = 0
for i in range(2,M):
  max_count = max(max_count,sum(counts[i::i]))

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

Solution (Python):
def gcd(n,m):
    while n:
        m,n = n,m%n
    return m

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

maxA = max(A)
B = [0]*(maxA+1)
for i in range(2,maxA+1):
    if B[i] == 0:
        B[i] = i
        for j in range(2*i,maxA+1,i):
            B[j] = i

soinsu = set()
a,b = 0,0

def pariwise():
    global N,A,soinsu,a,b
    for i in range(N):
        a = A[i]
        b = set()
        while a != 1:
            b.add(B[a])
            a //= B[a]
        for j in b:
            if j in soinsu:
                return False
            soinsu.add(j)
    return True

def setwise():
    global N,A,soinsu,a,b
    a = A[0]
    for i in range(1,N):
        a = gcd(a,A[i])
    return (a == 1)

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

Solution (Python):
N = int(input())
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in map(int, input().split()):
  counts[a] += 1

max_count = 0
for i in range(2,M):
  max_count = max(max_count,sum(counts[i::i]))

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1
from math import gcd

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

M=10**6

D=[-1]*(M+1)
D[0]=D[1]=1
for i in range(2,int(M**0.5)+1):
    if D[i]!=-1:
        continue
    for j in range(i*2,M+1,i):
        if D[j]==-1:
            D[j]=i

f=[False]*(M+1)

for x in A:
    l=[]
    while x>1:
        if f[x]==True:
            break
        if D[x]>1:
            l.append(D[x])
            x//=D[x]
        else:
            l.append(x)
            x=1
    else:
        for y in l:
            f[y]=True
        continue
    break
else:
    print('pairwise coprime')
    exit()

tmp=A[0]
for x in A[1:]:
    tmp=gcd(tmp,x)
    if tmp==1:
        print('setwise coprime')
        exit()
else:
    print('not coprime')

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
r = max(a)+1
s = []
t = [0]*r
for i in range(r):
    s.append([])
for i in range(2,r):
    if(s[i] == []):
        for j in range(1,-(-r//i)):
            s[i*j].append(i)
for i in range(n):
    for j in range(len(s[a[i]])):
        t[s[a[i]][j]] += 1
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    print('pairwise coprime')
else:
    print('setwise coprime')

Solution (Python):
N = int(input())
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in map(int, input().split()):
  counts[a] += 1

max_count = 0
for i in range(2,M):
  max_count = max(max_count,sum(counts[i::i]))

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

Solution (Python):
N = int(input())
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in map(int, input().split()):
  counts[a] += 1

max_count = 0
for i in range(2,M):
  count = 0
  for j in range(i,M,i):
    count += counts[j]
  max_count = max(max_count,count)

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    M = max(A)
    X = [i for i in range(M+1)]
    S = [True for i in range(M+1)]
    S[0] = False
    S[1] = False

    for i in range(1, M+1):
        if S[i]:
            for j in range(i, M+1, i):
                if S[j]:
                    S[j] = False
                    X[j] = i
    flag = True
    s = set()
    ls = 0
    for x in A:
        tmp = set()
        while(X[x] != 1):
            tmp.add(X[x])
            x //= X[x]
        l = len(tmp)
        s |= tmp
        if len(s) == ls + l:
            ls += l
            continue
        else:
            flag = False
            break

    if flag:
        print("pairwise coprime")
    else:
        for x in A[1:]:
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()

Solution (Python):
import math
def eratos(n):
    isprime = [i for i in range(n+1)]
    
    isprime[1] = 1
    for i in range(2, int(math.sqrt(n))+1):
        if isprime[i] == i:
            j = i
            while j <= n:
                if isprime[j] == j:
                    isprime[j] = i
                j = j + i
    return isprime

N = int(input())
A = list(map(int, input().split()))
isprime = eratos(10**6)
count = [0 for i in range(10**6+1)]
for ai in A:
    primes = {}
    while ai != 1:
        p = isprime[ai]
        primes[p] = 1
        ai //= p
    for p in primes.keys():
        count[p] += 1
max_c = max(count)
if max_c <= 1:
    print('pairwise coprime')
elif max_c == N:
    print('not coprime')
else:
    print('setwise coprime')

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


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):
import math

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



n=int(input())

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

gcd=A[0]

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

d=[0 for i in range(10**6+1)]

for i in range(2,10**6+1):
  if d[i]==0:
    j=1
    while i*j<=10**6:
      d[i*j]=i
      j+=1

nglis=[0 for i in range(10**6+1)]

if gcd!=1:
  print("not coprime")
else:
  check=0
  for i in range(n):
    if nglis[A[i]]==1:
      check=1
      break
    else:
      ai=A[i]
      while ai!=1:
        j=1
        while d[ai]*j<=10**6:
          nglis[d[ai]*j]=1
          j+=1
        ai=ai//d[ai]
  if check==1:
    print("setwise coprime")
  else:
    print("pairwise coprime")

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

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

def sieve_optimized(limit):
    
    n = limit
    
    sievebound = (n-1)//2
    sieve = [-1]*(sievebound + 1)
    
    crosslimit = (int(sievebound**0.5) - 1)
    for i in range(1, crosslimit + 1):
        if sieve[i] == -1:
            for j in range(2*i*(i+1), sievebound + 1, 2*i+1):
                sieve[j] = 2*i + 1
    return sieve

def factorization(n, sieve):
    
    divs = [1]
    while n!=1:
        if n&1:
            div = sieve[(n-1)//2]
            if div == -1:
                divs.append(n)
                break
            else:
                n //= div
                divs.append(div)
        else:
            n >>= 1
            divs.append(2)

    return divs

maxnum = 10**6 + 1
sieve = sieve_optimized(maxnum)

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

seen = dict()
maxval = 0
for i in nums:
    factors = factorization(i, sieve)
    if len(factors) <= 1: continue
    for f in set(factors[1:]):
        if f in seen:
            seen[f] += 1
            maxval = max(maxval, seen[f])
        else:
            seen[f] = 1


if maxval == n:
    print('not coprime')

elif 1 < maxval < n:
    print('setwise coprime')

else:
    print('pairwise coprime')

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()


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

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

from math import gcd
from functools import reduce
def resolve():
    n = int(input())
    A = list(map(int, input().split()))

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

    used = set()
    for a in A:
        for p in primeFactor(a):
            if p in used:
                print("setwise coprime")
                return
            used.add(p)

    print("pairwise coprime")
resolve()

Solution (Python):
M=10**6+1
f=lambda p: exit(print(['pairwise','setwise','not'][p]+' coprime'))
n,*l=map(int,open(0).read().split())
from math import *
g=l[0]
for x in l: g=gcd(g,x)
if g>1: f(2)
C=[0]*M
for x in l: C[x]=1
for i in range(2,M):
  if sum(C[j] for j in range(i,M,i))>1: f(1)
f(0)

Solution (Python):
from functools import reduce
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    maxA = 10**6

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

    def getMinPFs(n):
        isPrimes = [False]*2 + [True]*(n-1)
        minPFs = [1] + list(range(1, n+1))
        for d in range(2, int(n**0.5)+1):
            if isPrimes[d]:
                minPFs[d] = d
                for x in range(d*d, n+1, d):
                    isPrimes[x] = False
                    if minPFs[x] == x:
                        minPFs[x] = d
        return minPFs

    def getPrimeFactors(x, minPFs):
        anss = set()
        while minPFs[x] > 1:
            anss.add(minPFs[x])
            x //= minPFs[x]
        return anss

    minPFs = getMinPFs(maxA)

    useds = [0] * (maxA+1)
    for A in As:
        PFs = getPrimeFactors(A, minPFs)
        for PF in PFs:
            if useds[PF]:
                break
            useds[PF] = 1
        else:
            continue
        break
    else:
        print('pairwise coprime')
        return

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

    g = reduce(gcd, As)

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


solve()

Solution (Python):
import sys, math

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 == [] and n != 1:
        arr.append([n, 1])

    return arr

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

ok = True
S = set()
for a in A:
    arr = factorization(a)
    
    for b, _ in arr:
        if b in S:
            ok = False
            break
        else:
            S.add(b)
    if ok is False:
        break
if ok:
    print("pairwise coprime")
else:
    tmp = A[0]
    for a in A[1:]:
        tmp = math.gcd(a, tmp)
    if tmp != 1:
        print("not coprime")
    else:
        print("setwise coprime")

Solution (Python):
import sys
import math
N=int(input())
alist=list(map(int,input().split()))

all_GCD=alist[0]
for i in range(1,N):
  all_GCD=math.gcd(all_GCD,alist[i])
  if all_GCD==1:
    break
else:
  print("not coprime")
  sys.exit(0)

max_a=max(alist)  
dlist=[i for i in range(max_a+1)]
for i in range(2,int(max_a**0.5)+1):
  if dlist[i]<i:
    continue
  else:
    for j in range(i**2,max_a+1,i):
      dlist[j]=i  


fact_set=set()
for i in range(N):
  ai=alist[i]
  facts=set()
  while ai>1:
    facts.add(dlist[ai])
    ai//=dlist[ai]    
  
  
  for f in facts:
    if f in fact_set:
      print("setwise coprime")
      sys.exit(0)
    else:
      fact_set.add(f)
else:
  print("pairwise coprime")

Solution (Python):
N = int(input())
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in map(int, input().split()):
  counts[a] += 1

integers = [0,0] + [1 for _ in range(M-2)]
max_count = 0
for i in range(M):
  if integers[i] >= 1:
    count = 0
    for j in range(i,M,i):
      count += counts[j]
      integers[j] = 0
    max_count = max(max_count,count)

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

Solution (Python):
N = int(input())
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in list(map(int, input().split())):
  counts[a] += 1

integers = [0,0] + [1 for _ in range(M-2)]
max_count = 0
for i in range(M):
  if integers[i] >= 1:
    count = 0
    for j in range(i,M,i):
      count += counts[j]
      integers[j] = 0
    max_count = max(max_count,count)

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

Solution (Python):
import os
import heapq
import sys,threading
import math
import operator
from collections import defaultdict,deque
from io import BytesIO, IOBase
import math as mt
sys.setrecursionlimit(10 ** 5)
threading.stack_size(2**27)


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


"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""


def inpt():
    return [int(k) for k in input().split()]

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

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

    for i in range(3, mt.ceil(mt.sqrt(MAXN))):
        if (prime[i] == i):
            for j in range(i * i, MAXN, i):
                if (prime[j] == j):
                    prime[j] = i
    n=int(input())
    ar=inpt()
    d=defaultdict(int)
    ok=True
    for i in range(n):
        x=ar[i]
        while(x!=1):
            tp=prime[x]
            x=x//prime[x]
            if(tp in d and d[tp]!=(ar[i],i)):
                ok=False
                break
            d[tp]=(ar[i],i)

    if(ok):
        print('pairwise coprime')
    else:
        gcd=ar[0]
        for i in range(1,n):
            gcd=mt.gcd(gcd,ar[i])

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




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    
    threading.Thread(target=main).start()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in A:
  counts[a] += 1

integers = [0,0] + [1 for _ in range(M-2)]
max_count = 0
for i in range(M):
  if integers[i] >= 1:
    count = 0
    for j in range(i,M,i):
      count += counts[j]
      integers[j] = 0
    max_count = max(max_count,count)

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

Solution (Python):
from math import gcd, sqrt


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


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

    s_tmp = A[0]
    p_flag = True
    p_dic = [0] * (10**6+1)
    for a in A:
        s_tmp = gcd(s_tmp, a)
        if p_flag:
            tmp = list(set(prime_factorize(a)))
            for t in tmp:
                if p_dic[t] == 0:
                    p_dic[t] = 1
                else:
                    p_flag = False
                    continue

    if p_flag:
        print('pairwise coprime')
    elif s_tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in A:
  counts[a] += 1

integers = [1 for _ in range(M)]
integers[0] = 0
integers[1] = 0
max_count = 0
for i in range(M):
  if integers[i] >= 1:
    count = 0
    for j in range(i,M,i):
      count += counts[j]
      integers[j] = 0
    max_count = max(max_count,count)

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

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

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

sa = set()
for a in A:
    if a==1: continue
    if a in sa:
        print('setwise coprime')
        exit()
    sa.add(a)

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
small_primes = []
while p*p <= MAXN:
    if sieve[p]:
        small_primes.append(p)
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1

st = set()
for a in A:
    for p in small_primes:
        found = False
        while a%p==0:
            a //= p
            found = True
        if found:
            if p in st:
                print('setwise coprime')
                exit()
            st.add(p)
        if a==1: break
    else:
        if a in st:
            print('setwise coprime')
            exit()
        st.add(a)

print('pairwise coprime')

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

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

sa = set()
for a in A:
    if a==1: continue
    if a in sa:
        print('setwise coprime')
        exit()
    sa.add(a)

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
small_primes = []
while p*p <= MAXN:
    if sieve[p]:
        small_primes.append(p)
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1

st = set()
for a in A:
    for p in small_primes:
        found = False
        while a%p==0:
            a //= p
            found = True
        if found:
            if p in st:
                print('setwise coprime')
                exit()
            st.add(p)
        if a==1: break
    else:
        if a in st:
            print('setwise coprime')
            exit()
        st.add(a)

print('pairwise coprime')

Solution (Python):
from math import gcd


N = int(input())
A = list(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]

primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2

def factorization(n):
  M = n
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if counter[p] == 0:
          counter[p] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)


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