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

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, AS):
    num_division = 0
    maxAS = max(AS)
    eratree = [0] * (maxAS + 10)
    for p in range(2, maxAS + 1):
        if eratree[p]:
            continue
        
        x = p
        while x <= maxAS:
            if not eratree[x]:
                eratree[x] = p
            x += p

    from collections import defaultdict
    count = defaultdict(int)
    for a in AS:
        factors = []
        while a > 1:
            d = eratree[a]
            factors.append(d)
            a //= d
            num_division += 1
        
        for f in set(factors):
            count[f] += 1

    
    if any(x == N for x in count.values()):
        return "not coprime"
    if any(x >= 2 for x in count.values()):
        return "setwise coprime"
    return "pairwise coprime"


def main():
    
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))



T1 = """
3
3 4 5
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
pairwise coprime
"""

T2 = """
3
6 10 15
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
setwise coprime
"""

T3 = """
3
6 10 16
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
not coprime
"""

T4 = """
3
100000 100001 100003
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
pairwise coprime
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):
from collections import defaultdict
import math

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 = list(range(n+1))
    m = int(math.sqrt(n))
    for i in range(2, m + 1):
        if sieve[i] < i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve

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

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

sieve = sieve_of_eratosthenes(max(a_list))
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(a, sieve).keys())
        pairwise = primes.isdisjoint(factor)
        primes |= factor

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

Solution (Python):
from math import gcd


def factorization(n):
    global Ans, flag
    if n == 1:
        return
    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
            Ans[i] += 1
            if Ans[i] == 2:
                flag = True


    if temp != 1:
        Ans[temp] += 1
        if Ans[temp] == 2:
            flag = True

    return


N = int(input())
A = list(map(int, input().split()))
a = A[0]
flag = False
for b in A[1:]:
    a = gcd(a, b)

if a != 1:
    print('not coprime')
    exit()
ma = max(A) + 1
Ans = [0] * (ma)

Ans[0] = 1
for a in A:
    factorization(a)
    if flag:
        print('setwise coprime')
        exit()
print('pairwise coprime')

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
def Dlist(BIG):
    D=[1]*(BIG+1)
    for p in range(2,BIG+1):
        if D[p]!=1:
            continue
        for i in range(p,BIG+1,p):
            if D[i]==1:
                D[i]=p
    return D

D=Dlist(max(A))
def SOINSU(num,D): 
    now=num ; ans=set()
    while now>1:
        ans.add(D[now])
        now//=D[now]
    return ans

seen=[0]*(10**6+10)
flag=1
for num in A:
    for i in SOINSU(num,D):
        if seen[i]!=0: flag=0
        seen[i]+=1
if flag:
    print("pairwise coprime")
elif max(seen)!=n:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
gcd=math.gcd

def is_primes(n):
    primes = [1]*n
    primes[0] =0
    primes[1] =0
    for i in range(2,int(n**0.5)+2):
        if primes[i] ==1:
            for j in range(2*i,n,i):
                primes[j] = 0
    return primes
def factorize(n,primes):
    fct = [(1,1)]
    for b in primes:
        if b**2 > n:
            break
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
    if n > 1:
        fct.append((n,1))
    return fct

n =ni()
A = lma()
mx= 10**6+10
prms = is_primes(mx)
prms2=[i for i in range(mx) if prms[i]]

d=collections.Counter()
for a in A:
    fct = factorize(a,prms2)
    
    for fc,cnt in fct:
        if fc==1:continue
        d[fc]+=1

f1=True 
f2=True 
for num,cnt in d.items():
    if cnt==n:
        f2=False 
        break
    else:
        if cnt==1:
            pass
        else:
            f1=False

if f2==False:
    print("not coprime")
elif f1:
    print("pairwise coprime")
else:
    print("setwise 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 eratosthenes_sieve(n):

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

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

    d = Counter()
    while num != table[num]:
        d[table[num]] += 1
        num //= table[num]
    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


table = eratosthenes_sieve(10**6)

is_pc = 1
se = set()
for a in A:
    fact = factorize(table, 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 math import gcd, sqrt
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 = int(input())
a = list(map(int, input().split()))
b = a[0]
for i in range(1, n): b = gcd(b, a[i])
if b != 1: print("not coprime")
else:
    data = primes(10**6)
    c = [1]*(10**6+1)
    for i in range(1, 10**6+1):
        for j in range(len(data)):
            if i < data[j]**2: break
            if i%data[j] == 0: c[i] = data[j]; break
        if c[i] == 1: c[i] = i
    d = [0]*(10**6+1)
    for i in range(n):
        while a[i] > 1:
            d[c[a[i]]] += 1
            e = c[a[i]]
            while a[i]%e == 0: a[i] //= e
    print("setwise coprime") if max(d[2:]) > 1 else print("pairwise coprime")

Solution (Python):
class prime_factorize_by_osa_k():
    def __init__(self, max_val):
        '''
        割ることが出来る最小の値を格納したリストを返す
        :param max_val:
        :return:
        '''
        self.minFactor = [-1] * (max_val + 1)
        for i in range(2, max_val + 1):
            if self.minFactor[i] == -1:
                self.minFactor[i] = i
                
                for j in range(i * i, max_val + 1, i):
                    if self.minFactor[j] == -1:
                        self.minFactor[j] = i

    def osa_k(self, n):
        '''
        preprocessをしたあと、O(logN)で素因数分解を行う。nの最大値をn_maxとする。
        :param n:
        :return:
        '''
        from collections import defaultdict
        d = defaultdict(int)
        now = n
        while now > 1:
            d[self.minFactor[now]] += 1
            now //= self.minFactor[now]
        return d
def gcd(a, b):
    while b: a, b = b, a % b
    return a

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


ob = prime_factorize_by_osa_k(10 ** 6)
pairwise = False
prime_key = set(ob.osa_k(A[-1]).keys())
break_flag = False
prime_flags = [False] * (10 ** 6 + 1)
for i in range(N):
    for key in ob.osa_k(A[i]).keys():
        if prime_flags[key]:
            break_flag = True
            break
        else:
            prime_flags[key] = True
    if break_flag:
        break
else:
    pairwise = True
if pairwise:
    print('pairwise coprime')
    exit()
work = gcd(A[0], A[1])
for i in range(2, N):
    work = gcd(work, A[i])
if work != 1:
    print('not coprime')
else:
    print('setwise coprime')

Solution (Python):
from collections import defaultdict
import math

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 = list(range(n+1))
    sieve[0] = 1 
    sieve[1] = 1 
    m = int(math.sqrt(n))
    for i in range(2, m + 1):
        if sieve[i] < i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve

def factorize_by_sieve(x, sieve):
    factor = defaultdict(int)
    while sieve[x] != 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(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):
class prime_factorize_by_osa_k():
    def __init__(self, max_val):
        '''
        割ることが出来る最小の値を格納したリストを返す
        :param max_val:
        :return:
        '''
        self.minFactor = [-1] * (max_val + 1)
        for i in range(2, max_val + 1):
            if self.minFactor[i] == -1:
                self.minFactor[i] = i
                
                for j in range(i * i, max_val + 1, i):
                    if self.minFactor[j] == -1:
                        self.minFactor[j] = i

    def osa_k(self, n):
        '''
        preprocessをしたあと、O(logN)で素因数分解を行う。nの最大値をn_maxとする。
        :param n:
        :return:
        '''
        from collections import defaultdict
        d = defaultdict(int)
        now = n
        while now > 1:
            d[self.minFactor[now]] += 1
            now //= self.minFactor[now]
        return d
def gcd(a, b):
    while b: a, b = b, a % b
    return a

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


ob = prime_factorize_by_osa_k(10 ** 6)
pairwise = False
prime_key = set(ob.osa_k(A[-1]).keys())
break_flag = False
prime_flags = [False] * (10 ** 6 + 1)
for i in range(N):
    for key in ob.osa_k(A[i]).keys():
        if prime_flags[key]:
            break_flag = True
            break
        else:
            prime_flags[key] = True
    if break_flag:
        break
else:
    pairwise = True
if pairwise:
    print('pairwise coprime')
    exit()
work = gcd(A[0], A[1])
for i in range(2, N):
    work = gcd(work, A[i])
if work != 1:
    print('not coprime')
else:
    print('setwise coprime')

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


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


@njit
def solve(arr):
    cnt = np.bincount(arr)
    for i in range(2, 10**6 + 1):
        if (cnt[i::i]).sum() > 1:
            return False
    else:
        return True


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

Solution (Python):

import sys
import collections
from math import gcd
from functools import reduce

from random import randint

def lcm(a, b):
    return abs(a*b) // gcd(a, b)

def find_gcd(list):
    x = reduce(gcd, list)
    return x

def find_lcm(list):
    x = reduce(lambda a,b: lcm(a,b)% MOD, list)
    return x

D = [None for _ in range(10**6)]
MOD = 10**9 + 7
def solve(N: int, A: "List[int]"):

    q1 = reduce(gcd, A) == 1

    def SieveOfEratosthenes(n): 
        prime = [i for i in range(n + 1)] 
        p = 2
        while (p * p <= n): 
            if (prime[p] == p): 
                for i in range(p * 2, n + 1, p): 
                    prime[i] = p
            p += 1
        prime[0]= 0
        prime[1]= 1
        return prime

    D = SieveOfEratosthenes(10**6)
    s = set([])
    q2 = True
    for a in A:
        facs = set([])
        while True:            
            facs.add(D[a])
            a = a // D[a]
            if D[a] == a:
                facs.add(D[a])
                break

        for fac in facs:
            if fac in s:
                if fac != 1 and fac != 0:
                    q2 = False
            s.add(fac)


    if q1 and q2:
        print('pairwise coprime')
    elif q1:
        print('setwise coprime')
    else:
        print('not coprime')
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  

    solve(N, A)

if __name__ == '__main__':
    main()

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 eratosthenes_sieve(n):

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

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

    d = Counter()
    while num != table[num]:
        d[table[num]] += 1
        num = num // table[num]
    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

table = eratosthenes_sieve(10**6)

is_pc = 1
se = set()
for a in A:
    fact = factorize(table, 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):
def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        x, y = y, x % y
    return y


def gcd3(ll):
    ans = ll[0]
    for i in range(1, len(ll)):
        ans = gcd(ans, ll[i])
    return ans


D = {}
def prime_div(n, A):
    if len(D) == 0:
        for a in range(2, A + 1, 2):
            D[a] = 2
        for a in range(3, A + 1):
            if a in D:
                continue
            now = a
            while now <= A:
                if now not in D:
                    D[now] = a
                now += a * 2
    result = []
    while n > 1:
        result.append(D[n])
        n = n // D[n]
    return result
    

def checkPairwise(ll):
    dic = {}
    for n in ll:
        primes = list(set(prime_div(n, 1000000)))
        
        for p in primes:
            if p not in dic:
                dic[p] = 1
            else:
                return False
    return True


def main():
    N = int(input())
    A = [int(n) for n in input().split(" ")]
    a1 = checkPairwise(A)
    if a1:
        print("pairwise coprime")
    else:
        a2 = gcd3(A)
        if a2 == 1:
            print("setwise coprime")
        else:
            print("not coprime")


if __name__ == "__main__":
    main()

Solution (Python):
import sys

from collections import defaultdict
from functools import lru_cache


@lru_cache(None)
def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


def merge_dict(d1, d2):
    for k, v in d2.items():
        d1[k] += v
    return d1


def input():
    return sys.stdin.readline().strip()


def gen_prime_table(last: int, first=2) -> list:
    if last < 1:
        return [None]
    elif last < 2:
        return [None, None]
    table = [None] * (last + 1)

    for i in range(first, last + 1):
        if not table[i]:
            table[i] = i
            for j in range(i * 2, last + 1, i):
                table[j] = i
    return table


def prime_factorization(N: int, min_factor: list) -> dict:
    if N < 2:
        return {1: 1}
    primes = dict()
    primes[1] = 1
    while N != 1:
        p = min_factor[N]
        if p in primes.keys():
            primes[p] += 1
        else:
            primes[p] = 1
        N = N // p
    return primes


def main():
    n = int(input())
    A = [int(i) for i in input().split()]
    primes = defaultdict(int)
    is_pair_gcd = True
    set_gcd = A[0]
    min_factor = gen_prime_table(max(A))  
    for i in range(n):
        set_gcd = gcd(set_gcd, A[i])
        p = prime_factorization(A[i], min_factor)
        if is_pair_gcd:
            for k, v in p.items():
                if k == 1:
                    continue
                if k in primes.keys():
                    is_pair_gcd = False
                else:
                    primes[k] += v

    if is_pair_gcd:
        print("pairwise coprime")
        return

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

    return


if __name__ == "__main__":
    main()

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

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

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

n=int(input())
arr=list(map(int,input().split()))
cnt=collections.defaultdict(int)
tmp=arr[0]
for val in arr:
  tmp=gcd(tmp,val)
if tmp==1:
  is_setwise=True
else:
  is_setwise=False
is_pairwise=True
for val in arr:
  divisor=divisors(val)
  for val2 in divisor:
    cnt[val2]+=1
    if cnt[val2]==2:
      is_pairwise=False
      break
  if is_pairwise==False:
    break
if is_pairwise==True:
  print('pairwise coprime')
elif is_setwise==True:
  print('setwise coprime')
else:
  print('not coprime')

Solution (Python):
import math
from functools import reduce

def gcd(nums):
    return reduce(math.gcd, nums)

N = int(input())
A = list(map(int, input().split()))
S = [0 for i in range(1000001)]

for i in range(N):
    S[ A[i] ] += 1

pairwise = True
for i in range(2, 1000001):
    cnt = sum(S[i*j] for j in range(1000000//i + 1))
    pairwise &= (cnt <= 1)

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

Solution (Python):
import sys

from collections import defaultdict
from functools import lru_cache


@lru_cache(None)
def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


def merge_dict(d1, d2):
    for k, v in d2.items():
        d1[k] += v
    return d1


def input():
    return sys.stdin.readline().strip()


def gen_prime_table(last: int, first=2) -> list:
    if last < 1:
        return [None]
    elif last < 2:
        return [None, None]
    table = [None] * (last + 1)

    for i in range(first, last + 1):
        if not table[i]:
            table[i] = i
            for j in range(i * 2, last + 1, i):
                table[j] = i
    return table


def prime_factorization(N: int, min_factor: list) -> dict:
    if N < 2:
        return {1: 1}
    primes = dict()
    primes[1] = 1
    while N != 1:
        p = min_factor[N]
        if p in primes.keys():
            primes[p] += 1
        else:
            primes[p] = 1
        N = N // p
    return primes


def main():
    n = int(input())
    A = [int(i) for i in input().split()]
    primes = defaultdict(int)
    is_pair_gcd = True
    set_gcd = A[0]
    min_factor = gen_prime_table(max(A))  
    for i in range(n):
        set_gcd = gcd(set_gcd, A[i])
        if is_pair_gcd:
            p = prime_factorization(A[i], min_factor)
            for k, v in p.items():
                if k == 1:
                    continue
                if k in primes.keys():
                    is_pair_gcd = False
                else:
                    primes[k] += v

    if is_pair_gcd:
        print("pairwise coprime")
        return

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

    return


if __name__ == "__main__":
    main()

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

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

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

n=int(input())
arr=list(map(int,input().split()))
cnt=[False]*(max(arr)+1)
is_pairwise=True
tmp=arr[0]
for val in arr:
  tmp=gcd(tmp,val)
  if is_pairwise==False:
    continue
  divisor=divisors(val)
  for val2 in divisor:
    if cnt[val2]==True:
      is_pairwise=False
      break
    cnt[val2]=True
if tmp==1:
  is_setwise=True
else:
  is_setwise=False
if is_pairwise==True:
  print('pairwise coprime')
elif is_setwise==True:
  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 min_div(n):
    if n <= 1:
        return []
    elif n == 2:
        return [0, 1, 2]
    D = [0] * (n+1)
    D[1] = 1
    D[2::2] = [2] * (n//2)
    len_list = (n + 1) // 2
    len_sqrt = int(len_list ** 0.5) + 1
    flags = [True] * len_list
    for i in range(1, len_sqrt):
        if flags[i]:
            p = i*2 + 1
            start = (p ** 2) // 2
            for j in range(start, len_list, p):
                flags[j] = False
                D[j*2 + 1] = p
    
    for i in range(1, len_list):
        if flags[i]:
            p = i*2 + 1
            D[p] = p
    
    return D

D = min_div(10**6)
appeared = [False] * (10**6 + 1)
for a in A:
    if a == 1:
        continue
    s = set()
    while a != D[a]:
        d = D[a]
        if appeared[d]:
            print('setwise coprime')
            quit()
        s.add(d)
        a //= d
    
    if appeared[a]:
        print('setwise coprime')
        quit()
    
    for d in s:
        appeared[d] = True
    
    if a != 1:
        appeared[a] = True

print('pairwise coprime')

Solution (Python):
from math import gcd

n = int(input())
a = list(map(int, input().split()))
g = a[0]
for aa in a:
    g = gcd(aa, g)
if g != 1:
    print('not coprime')
    exit()


def Eratosthenes_sieve(n):
    table = [True] * (n + 1)
    table[0] = False
    table[1] = False
    for i in range(n + 1):
        if table[i]:
            for j in range(2 * i, n + 1, i):  
                table[j] = False
    return table


primes = [i for i, p in enumerate(Eratosthenes_sieve(1000)) if p]

s = set()
for aa in a:
    if aa == 1:
        continue
    if aa in s:
        print('setwise coprime')
        exit()
    for pp in primes:
        if aa < pp:
            break
        if aa % pp == 0:
            if pp in s:
                print('setwise coprime')
                exit()
            s.add(pp)
            aaa = aa // pp
            if aaa > 1000:
                if aaa in s:
                    print('setwise coprime')
                    exit()
                s.add(aaa)
    s.add(aa)
print('pairwise coprime')

Solution (Python):
from math import gcd
from bisect import insort

N = int(input())
A = list(map(int, input().split()))
mA = max(A)
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 binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    
    return False

primecounter = [0 for _ in range(len(primenum))]
biggerprime = []
def factorization(n):
  M = n
  for k in range(len(primenum)):
    p = primenum[k]
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if primecounter[k] == 0:
          primecounter[k] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if binary_search(biggerprime, M):
      return False
    else:
      insort(biggerprime, M)
  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 == False:
    if g == 1:
      break


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

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_max(n):
    sieve = [0] * (n+1)
    sieve[0] = 0 
    sieve[1] = 1 
    for i in range(2, n+1):
        if sieve[i] == 0:
            for j in range(1, n // i + 1):
                sieve[i * j] = i
    return sieve

def factorize_by_sieve_of_eratosthenes(x, sieve):
    factor = defaultdict(int)
    while sieve[x] != 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_max(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):
from math import gcd

n = int(input())
a = list(map(int, input().split()))
g = a[0]
for aa in a:
    g = gcd(aa, g)
if g != 1:
    print('not coprime')
    exit()


def Eratosthenes_sieve(n):
    table = [True] * (n + 1)
    table[0] = False
    table[1] = False
    for i in range(n + 1):
        if table[i]:
            for j in range(2 * i, n + 1, i):  
                table[j] = False
    return table


primes = [i for i, p in enumerate(Eratosthenes_sieve(1000)) if p]

s = set()
for aa in a:
    if aa == 1:
        continue
    if aa in s:
        print('setwise coprime')
        exit()
    for pp in primes:
        if aa < pp:
            break
        if aa % pp == 0:
            if pp in s:
                print('setwise coprime')
                exit()
            s.add(pp)
            aaa = aa // pp
            if aaa > 1000:
                if aaa in s:
                    print('setwise coprime')
                    exit()
                s.add(aaa)
    s.add(aa)
print('pairwise coprime')

Solution (Python):
from math import gcd


def create_sieve(n):
    sieve = [0] * (n + 1)

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

    return sieve


def fast_factorization(n, sieve):
    from collections import Counter
    arr = Counter()
    while n > 1:
        p = sieve[n]
        if p == 0:
            arr[n] += 1
            break
        else:
            arr[p] += 1
            n //= p
    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 = create_sieve(M)
done = set()
isPairwise = True
for a in A:
    arr = fast_factorization(a, sieve)
    for p in arr.keys():
        if p in done:
            isPairwise = False
        else:
            done.add(p)


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