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 main():
    N = int(input())
    A = list(map(int, input().split()))
    maxA = max(A)
    
    sieve = [0] * (maxA + 1)
    sieve[0] = sieve[1] = -1
    for i in range(maxA+1):
        if sieve[i] != 0:
            continue
        for j in range(i, maxA+1, i):
            if sieve[j] == 0:
                sieve[j] = i

    
    primelist = []
    lenprimelist = 0
    for i in range(N):
        tmpset = set()
        j = A[i]
        for _ in range(N):
            tmp = sieve[j]
            if tmp <= 0:
                break
            tmpset.add(tmp)
            j = j//tmp
        lenprimelist += len(tmpset)
        primelist.append(tmpset)
    
    
    
    
    
    
    

    primeset = set()
    primeintersection = set(range(2, maxA+1))
    for s in primelist:
        primeset.update(s)
        primeintersection.intersection_update(s)
    if len(primeset) == lenprimelist:
        print('pairwise coprime')
        return
    if len(primeintersection) == 0:
        print('setwise coprime')
        return
    print('not coprime')
    return

if __name__ == "__main__":
    main()

Solution (Python):
import math
n=int(input())
a=list(map(int,input().split()))
pflag=True
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
sosu=[1]*(10**6+1)
sosu[0]=0

k=2
while k<(10**6+1)**0.5+1:
  for i in range(2*k,10**6+1,k):
    sosu[i]=0
  if k==2:
    k+=1
  else:
    k+=2
gu=0
import copy
ans=copy.deepcopy(sosu)

for i in range(n):
  if gu>1:
    pflag=False
  if ans[a[i]]==0:
    ai = set(prime_factorize(a[i]))
    for j in ai:
      if ans[j]==0:
        pflag=False
        break
      else:
        ans[j]=0
  else:
    ans[a[i]]=0
  if a[i]%2==0:
    gu+=1
  ans[a[i]]=0
    
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

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

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def eratosthenes(n):
    prime = [2]
    if n == 2:
        return prime
    limit = int(n ** 0.5)
    data = [i + 1 for i in range(2, n, 2)]
    res = [0] * (n + 1)
    res[1] = 1
    for i in range(2, n + 1, 2):
        res[i] = 2
    while True:
        p = data[0]
        if limit <= p:
            for e in data:
                res[e] = e
            return res
        prime.append(p)
        res[p] = p
        for e in data:
            if e % p == 0:
                res[e] = p
        data = [e for e in data if e % p != 0]


def solve():
    _ = int(rl())
    A = list(map(int, rl().split()))
    
    prime_fact = eratosthenes(10 ** 6)
    p_flg = True
    prime_fact_set = set()
    for ai in A:
        num = ai
        prime_fact_ai = set()
        while num != 1:
            prime_fact_ai.add(prime_fact[num])
            num //= prime_fact[num]
        for p in prime_fact_ai:
            if p in prime_fact_set:
                p_flg = False
                break
            prime_fact_set.add(p)
        if not p_flg:
            break
    
    if p_flg:
        print('pairwise coprime')
        return
    
    gcd_a = reduce(gcd, A)
    if gcd_a == 1:
        print('setwise coprime')
        return
    
    print('not coprime')


if __name__ == '__main__':
    solve()

Solution (Python):
INF=10**9+7
D = [INF]*(10**6+1)
L = [True]*(10**6+1)
L[0] = False
L[1] = False
D[1] = 1
for i in range(2, 10**6+1):
    if L[i]:
        D[i] = i
        for j in range(i*2, 10**6+1, i):
            L[j] = False
            D[j] = min(i, D[j])



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


def factorization(n):
    ans = set()
    if n == 1:
        ans.add(1)
        return ans
    while n>1:
        ans.add(D[n])
        n//=D[n]
    return ans


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

s = set(factorization(A[0])-{1})
for i in range(1, N):
    tmp = factorization(A[i])-{1}
    if tmp & s != set():
        break
    s |= tmp
else:
    print('pairwise coprime')
    exit()

L1 = A
while len(L1) > 1:
    l = len(L1)//2
    k = [0]*l
    for i in range(l):
        k[i] = egcd(L1[2*i], L1[2*i+1])
    if len(L1) % 2 == 1:
        k.append(L1[-1])
    L1 = k

if L1[0] == 1:
    print('setwise coprime')
else:
    print('not coprime')

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

def sieve(n):
    A = list(range(n+1))
    for i in range(2, n+1 ,2):
        A[i] = 2
    for j in range(3, ceil(sqrt(n+1))+1, 2)[::-1]:
        for i in range(j, n+1, j):
            A[i] = j
    return A

def factorize(n, A):
    factors = set()
    while n != 1:
        f = A[n]
        factors.add(f)
        n //= f
    return factors


















_, *aa = map(int, open(0).read().split())

def main(aa):
    pair_co = True
    A = sieve(10**6)
    all_factors = set()
    for a in aa:
        factors = factorize(a, A)
        for factor in factors:
            if factor in all_factors:
                pair_co = False
                break
            else:
                all_factors.add(factor)
        if not pair_co:
            break
    if pair_co:
        return 'pairwise coprime'
    elif reduce(gcd, aa) == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'

print(main(aa))

Solution (Python):
from math import gcd

n = int(input())
a = list(map(int, input().split()))
MAX = max(a)
d = {}; g = 0
for i in a:
    d[i] = 1 if i not in d else d[i] + 1
    g = gcd(g, i)

if g > 1:
    print('not coprime')
else:
    for i in range(2, MAX + 1):
        f = 0
        for j in range(i, MAX + 1, i):
            f += d[j] if j in d else 0
        if f > 1:
            print('setwise coprime')
            break
    else:
        print('pairwise coprime')

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


















def factorize(n):
    factors = set()
    if n % 2 == 0:
        factors.add(2)
        n //= 2
    while n % 2 == 0:
        n //= 2
    for i in range(3, ceil(sqrt(n + 1)) + 1):
        if n % i == 0:
            factors.add(i)
            n //= i
        while n % i == 0:
            n //= i
    if n > 2:
        factors.add(n)
    return factors

_, *aa = map(int, open(0).read().split())

def main(aa):
    pair_co = True


    all_factors = set()
    for a in aa:
        factors = factorize(a)

        for factor in factors:
            if factor in all_factors:
                pair_co = False
                break
            else:
                all_factors.add(factor)
        if not pair_co:
            break
    if pair_co:
        return 'pairwise coprime'
    elif reduce(gcd, aa) == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'

print(main(aa))

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

c=[0]*(10**6+5)

isPairwise=True
isSetwise=True
for i in range(N):
    c[A[i]]+=1

for i in range(2,1000005):
    cnt=0
    for j in range(i,1000005,i):
        cnt+=c[j]
    
    if cnt>1:
        isPairwise=False

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

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

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

Solution (Python):
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    mylist = LI()
    max_num = max(mylist)
    max_num2 = math.ceil(math.sqrt(max_num))
    D = [True]* (max_num+1)
    D[0] = D[1] = False
    mylist = Counter(mylist)
    setwise = True
    pairwise = True

        
    for i in range(2, max_num+1):
        temp = 0
        if D[i]:
            for j in range(i, max_num+1, i):
                D[j] = False
                
                try:
                    temp+=mylist[j]
                except:
                    pass

            if temp == N:
                print("not coprime")
                sys.exit()
            if temp >= 2:
                pairwise = False

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

            
    
    
if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
from numba import njit


n = int(input())
arr = np.array(list(map(int, input().split())))


n = 10**6 + 1
primes = set(range(3, n+1, 2))

for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)


@njit
def solve(arr, primes):
    cnt = np.bincount(arr)
    for p in primes:
        if (cnt[p::p]).sum() > 1:
            return False
    else:
        return True


if np.gcd.reduce(arr) != 1:
    print("not coprime")
elif solve(arr, primes):
    print("pairwise coprime")
else:
    print("setwise coprime")

Solution (Python):
from math import gcd
n = int(input())
a = [int(i) for i in input().split()]

g = a[0]
for i in range(n):
    g = gcd(g,a[i])
if g != 1:
    print("not coprime")
    exit()

m = max(a)
fac = [1]*(m+1)
for i in range(2,m+1):
    if fac[i] != 1:
      continue
    for j in range(i,m+1,i):
      fac[j] = i
      
s = set()
for i in range(n):
    x = fac[a[i]]
    if x == 1: 
      continue
    if x in s:
      print("setwise coprime")
      exit()
    s.add(x)
print("pairwise coprime")

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

from fractions import gcd
from math import sqrt
def pfact(num):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

n = inp()
x = ip()
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)

Solution (Python):
import math

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

dp=[0 for _ in range(1000001)]

for d in a:
  dp[d]+=1
  
ch1=0
for i in  range(2,1000001):
  ch=0
  x=i
  while x<=1000000:
    ch+=dp[x]
    x+=i
  if ch>1:
    ch1+=1
    
if ch1==0:
  print('pairwise coprime')
  
else:
  g=a[0]
  for h in range(1,n):
    g=math.gcd(g,a[h])
    
  if g==1:
    print('setwise coprime')
    
  else:
    print('not coprime')

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


















def factorize(n):
    factors = set()
    if n % 2 == 0:
        factors.add(2)
        n //= 2
    while n % 2 == 0:
        n //= 2
    for i in range(3, ceil(sqrt(n + 1)) + 1):
        if n % i == 0:
            factors.add(i)
            n //= i
        while n % i == 0:
            n //= i
    if n > 2:
        factors.add(n)
    return factors

_, *aa = map(int, open(0).read().split())

def main(aa):
    pair_co = True

    all_factors = [0] * (10**6+1)
    for a in aa:
        factors = factorize(a)

        for factor in factors:
            if all_factors[factor]:
                pair_co = False
                break
            else:
                all_factors[factor] = 1
        if not pair_co:
            break
    if pair_co:
        return 'pairwise coprime'
    elif reduce(gcd, aa) == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'

print(main(aa))

Solution (Python):
import math
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
MAX = 10**6 + 1

cut = [2 for _ in range(MAX)]
for i in range(3, MAX, 2):
    if cut[i] != 2:
        continue
    for j in range(i, MAX, i):
        cut[j] = i

if reduce(math.gcd, A) != 1:
    print('not coprime')
    exit()

already = set()
for a in A:
    now = set()
    while a != 1:
        if cut[a] in already:
            print('setwise coprime')
            exit()
        now.add(cut[a])
        a //= cut[a]
    already |= now

print('pairwise coprime')

Solution (Python):
import math


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    M = max(A) + 1
    C = [0 for i in range(M)]
    for a in A:
        C[a] += 1

    pairwise = True
    for i in range(2, M):
        cnt = 0
        for j in range(i, M, i):
            cnt += C[j]

        if cnt > 1:
            pairwise = False

    if pairwise:
        print("pairwise coprime")
        return

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

    if g == 1:
        print("setwise coprime")
        return

    print("not coprime")

resolve()

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]



def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

n = inp()
x = ip()
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)

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

def sieve(n):
    A = list(range(n+1))
    for i in range(2, n+1 ,2):
        A[i] = 2
    for j in range(3, ceil(sqrt(n+1))+1, 2)[::-1]:
        for i in range(j, n+1, j):
            A[i] = j
    return A

def factorize(n, A):
    factors = set()
    while n != 1:
        f = A[n]
        factors.add(f)
        n //= f
    return factors

_, *aa = map(int, open(0).read().split())

def main(aa):
    pair_co = True
    A = sieve(10**6)
    all_factors = [0] * (10**6+1)
    for a in aa:
        factors = factorize(a, A)
        for factor in factors:
            if all_factors[factor]:
                pair_co = False
                break
            else:
                all_factors[factor] = 1
        if not pair_co:
            break
    if pair_co:
        return 'pairwise coprime'
    elif reduce(gcd, aa) == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'

print(main(aa))

Solution (Python):

def f2(n,A):
    s=[int(i) for i in range(0,n+1)]
    a={}
    for i in range(2,int(n**0.5)+1):
        if s[i]!=i:
            continue
        for j in range(i,n+1,i):
            s[j]=i

    for i in range(2,n+1):
        if s[i]==i:
            a[i]=1

    l=len(A)
    p=[[] for i in range(l)]
    for i in range(l):
        x=A[i]
        while x!=1:
            p[i].append(s[x])
            if a[s[x]]==0:
                return False
            x//=s[x]


        for j in p[i]:
            a[j]=0

    return True

from math import gcd
N=int(input())
A=[int(i) for i in input().split()]
a=max(A)
p=f2(a,A)


if p:
    print('pairwise coprime')
else:
    g=A[0]
    for i in range(1,len(A)):
        g=gcd(g,A[i])
        if g==1:
            break
    if g==1:
        print('setwise coprime')
    else:
        print('not coprime')

Solution (Python):
from math import gcd

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

g_all = A[0]
for a in A[1:]:
    g_all = gcd(g_all, a)

if g_all > 1:
    print('not coprime')
    quit()

def sieve(n):
    if n <= 1:
        return []
    elif n == 2:
        return [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]:
            w = i*2 + 1
            start = (w ** 2) // 2
            for j in range(start, len_list, w):
                flags[j] = False
    return [2] + [i*2+1 for i in range(len_list) if flags[i]]



appeared = [False] * (10**6 + 1)
primes = sieve(10**3)
for a in A:
    if a == 1:
        continue
    for p in primes:
        if a % p == 0:
            if appeared[p]:
                print('setwise coprime')
                quit()
            appeared[p] = True
            while a % p == 0:
                a //= p
    
    if a != 1:
        if appeared[a]:
            print('setwise coprime')
            quit()
        
        appeared[a] = True

print('pairwise coprime')

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

input = sys.stdin.readline

ub = 10 ** 6

smallest_prime_factor = list(range(ub + 1))
for p in reversed(range(2, len(smallest_prime_factor))):
    if p == smallest_prime_factor[p]:
        for i in range(2 * p, len(smallest_prime_factor), p):
            smallest_prime_factor[i] = p


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

ans = ""
prime_factors = set()
for ai in a:
    tmp = ai
    while tmp != 1:
        p = smallest_prime_factor[tmp]
        if p in prime_factors:
            break
        prime_factors.add(p)
        while tmp % p == 0:
            tmp //= p
    else:
        continue
    break
else:
    ans = "pairwise coprime"

if ans == "":
    if reduce(gcd, a) == 1:
        ans = "setwise coprime"
    else:
        ans = "not coprime"
print(ans)

Solution (Python):
from collections import defaultdict

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

def sieve_of_eratosthenes(n):
    sieve = [0] * (n+1)
    sieve[0] = 1 
    sieve[1] = 1 
    for i in range(2, n):
        if sieve[i] == 0:
            for j in range(2, n // i + 1):
                sieve[i * j] = i
    return sieve

def factorize_by_sieve_of_eratosthenes(x, sieve):
    factor = defaultdict(int)
    while sieve[x]:
        factor[sieve[x]] += 1
        x //= sieve[x]
    factor[x] += 1
    return factor

n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()

sieve = sieve_of_eratosthenes(a_list[-1])
pairwise = True
setwise = True
primes = set()
x = a_list[0]
for a in a_list:
    x = gcd(x, a)
    if pairwise and a != 1:
        factor = set(factorize_by_sieve_of_eratosthenes(a, sieve).keys())
        if not primes.isdisjoint(factor):
            pairwise = False
        else:
            primes |= factor

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

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

A = sorted(A,reverse = True)
prime = [0] * (10**6+1)
eratos = [True] * (A[0] + 1)
D = [0] * (A[0]+1)
D[1] = 1
for i in range(2,A[0] + 1):
  if not eratos[i]:
    continue
  else:
    for j in range(i,A[0] + 1,i):
      if not D[j]:
        D[j] = i
      if j!=i:
      	eratos[j] = False
  
for a in A:
  while a!=1:
    x = D[a]
    while a%x==0:
      a//=x
    prime[x] += 1

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

Solution (Python):
from collections import defaultdict
import math

def Sieve_of_Eratosthenes(maxA):
    lst = [-1]*(maxA+1)
    lst[0] = 0
    lst[1] = 1
    for i in range(2, maxA+1):
        if lst[i] == -1:
            for g in range(i, maxA+1, i):
                if lst[g] == -1:
                    lst[g] = i
    return lst

def factorization(n):  
    d = defaultdict(int)
    now = n
    while True:
        if now == lst[now]:
            if now != 1:
                d[now] += 1
            break
        r = lst[now]
        while now % r == 0:
            now //= r
            d[r] += 1
    return d

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

g = a[0]
for i in range(1, n):
    g = math.gcd(g, a[i])

if g == 1:
    d = defaultdict(int)
    maxA = max(a)
    lst = Sieve_of_Eratosthenes(maxA)
    for m in a:
        fs = factorization(m)
        for f in fs.keys():
            d[f] += 1
    for f in d.values():
        if f != 1:
            print("setwise coprime")
            exit()
    print("pairwise coprime")
else:
    print("not coprime")

Solution (Python):
from math import gcd

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

g_all = A[0]
for a in A[1:]:
    g_all = gcd(g_all, a)

if g_all > 1:
    print('not coprime')
    quit()

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


appeared = [False] * (10**6 + 1)
primes = sieve(10**3)[1]
for a in A:
    if a == 1:
        continue
    for p in primes:
        if a % p == 0:
            if appeared[p]:
                print('setwise coprime')
                quit()
            appeared[p] = True
            while a % p == 0:
                a //= p
    
    if a != 1:
        if appeared[a]:
            print('setwise coprime')
            quit()
        
        appeared[a] = True

print('pairwise coprime')

Solution (Python):
import sys
N = int(input())
A = list(map(int, input().split())) 
MAX = 10**6

not_pairwise_coprime = False 


Ct = [0 for _ in range(MAX+1)]
for a in A:
  Ct[a] += 1 
if max(Ct[2:MAX+1]) > 1:
  not_pairwise_coprime = True
  
if max(Ct[2:MAX+1]) == N: 
  print("not coprime")
  sys.exit()
  
A = set(A) 
N = len(A)

for p in range(2,MAX+1):
  ct = 0 
  for q in range(p,MAX+1,p): 
    if q in A:
      ct += 1
  
  
  if ct == N:
    print("not coprime")
    sys.exit()
  
  
  
  elif ct >= 2:
    not_pairwise_coprime = True
  
  
  
  
  


print("setwise coprime" if not_pairwise_coprime else "pairwise 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)

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

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

    return set(arr)

import math
N=int(input())
A=list(map(int,input().split()))
ans=['pairwise coprime','setwise coprime','not coprime']
k=0
s=factorization(A[0])
for a in A[1:]:
    tmp=factorization(a)-{1}
    if s&tmp==set():
        s|=tmp
    else:
        k=-1
        break
if k==-1:
    g=A[0]
    for a in A[1:]:
        g=math.gcd(g,a)
    if g==1:
        k=1
    else:
        k=2
print(ans[k])

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

def g(ais): return reduce(gcd, ais) == 1

def f(ais):
	seen = set()
	for ai in ais:
		factor =2
		oi = ai
		while(ai != 1 and factor * factor <= oi):
			if ai % factor == 0:
				if factor in seen:
					return False
				while(ai % factor == 0):
					ai /= factor
				seen.add(factor)
			factor +=1
		if ai != 1:
			if ai in seen: return False
			seen.add(ai) 
	return True

ais = map(int, raw_input().split())

if f(ais):
	print 'pairwise coprime'
elif g(ais):
	print 'setwise coprime'
else:
	print 'not coprime'

Solution (Python):
from math import gcd
n = int(input())
a = [int(i) for i in input().split()]

g = a[0]
for i in range(n):
    g = gcd(g,a[i])
if g != 1:
    print("not coprime")
    exit()

m = max(a)
fac = [1]*(m+1)
for i in range(2,m+1):
    if fac[i] != 1: continue
    for j in range(i,m+1,i): fac[j] = i
s = set()
for i in range(n):
    x = fac[a[i]]
    if x == 1: continue
    if x in s:
        print("setwise coprime")
        exit()
    s.add(x)
print("pairwise coprime")

Solution (Python):
import sys
from math import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    for i in range(2, int(sqrt(num))+1):
        while num % i == 0:
            num //= i
            d[i] += 1
        if num == 1:
            break
    if num != 1:
        d[num] += 1
    return d

N = INT()
A = LIST()

def check(se, fact):
    for k in fact:
        if k not in se:
            se.add(k)
        else:
            return False
    return True

is_pc = 1
se = set()
for a in A:
    fact = factorize(a)
    if not check(se, fact):
        is_pc = 0
        break

is_sc = 1
g = 0
for a in A:
    g = gcd(g, a)
if g != 1:
    is_sc = 0

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

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
countA = Counter(A)


memo = [1]*(10**6+1)
memo[0] = 0
memo[1] = 0
for i in range(2,10**6+1):
    if memo[i] == 1:
        flag = False
        if i in countA:
            if countA[i] >= 2:
                break
            flag = True
        for j in range(i*2,10**6+1,i):
            if j in countA:
                if countA[j] >= 2:
                    break
                if flag:
                    break
                else:
                    flag = True
            memo[j] = 0
        else:
            continue
        break
else:
    print("pairwise coprime")
    exit()




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

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

Solution (Python):


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

n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
ans2 = a_list[0]
for i in range(1, n):
    ans2 = gcd(ans2, a_list[i])
    if ans2 == 1:
        break

if ans2 != 1:
    print("not coprime")
else:
    flag = 1
    max_a = a_list[n - 1] + 1
    num_flag_list = [True] * max_a
    d_list = list(range(0, max_a))
    d_list[0] = 1
    num_flag_list[0] = num_flag_list[1] = False
    for i in range(2, int(max_a**0.5) + 1):
        if num_flag_list[i]:
            for j in range(i**2, max_a, i):
                if num_flag_list[j] == True:
                    num_flag_list[j] = False
                    d_list[j] = i
    p_set = set()
    for a in a_list:
        if a == 1:
            continue
        temp_p_set = set()
        while True:
            p = d_list[a]
            if p not in temp_p_set:
                if p in p_set:
                    flag = 0
                    break
            temp_p_set.add(p)
            p_set.add(p)
            a = a // p
            if a == 1:
                break
        if flag == 0:
            break
        
    if flag == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Solution (Python):
import math

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = [True] * (V + 1)
        self.primes = []
        for i in range(2, V + 1):
            if self.is_prime[i]:
                self.primes.append(i)
                for j in range(i * i, V + 1, i):
                    self.is_prime[j] = False
    
    def factorize(self, x):
        assert x > 1
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        return result


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

    if all(a == 1 for a in A):
        return 'pairwise coprime'

    gcd_all = 0
    for a in A:
        gcd_all = math.gcd(gcd_all, a)

    if gcd_all > 1:
        return 'not coprime'
    
    sieve = SieveOfEratosthenes(max(A))
    used_primes = set()
    for a in A:
        if a != 1:
            factors = sieve.factorize(a)
            for (p, e) in factors:
                if p in used_primes:
                    return 'setwise coprime'
                used_primes.add(p)
    
    return 'pairwise coprime'

print(solve())