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 math
from functools import reduce






N = int(input())



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





































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

if gcd_list(A) > 1:
    print("not coprime")
    exit()


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

st = set()
for a in A:
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
    for p in tmp:
        if p in st:
            print('setwise coprime')
            exit()
        st.add(p)
print('pairwise coprime')

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
m=max(l)

from math import gcd
g=gcd(l[0],l[1])
for i in range(2,n):
  g=gcd(g,l[i])
if g!=1:
  print('not coprime')
  exit()

prime=[True]*(m+1)
prime[0]=False
prime[1]=False
d=[0]*(m+1)
for i in range(2,int(m**0.5)+1):
  if prime[i]:
    for j in range(i*2,m+1,i):
      prime[j]=False
      d[j]=i
s=[i for i in range(m+1) if prime[i]]
for ss in s:
  d[ss]=ss

sl=set()
for i in range(n):
  div=set()
  ll=l[i]
  while ll>1:
    div.add(d[ll])
    ll//=d[ll]
  div=list(div)
  for dd in div:
    if dd not in sl:
      sl.add(dd)
    else:
      print('setwise coprime')
      exit()

print('pairwise coprime')

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

f1 = True
f2 = True

c = [0] * (10**6+5)
for a in A:
  c[a] += 1
for i in range(2, 10**6+5):
  cnt = 0
  for j in range(i, 10**6+5, i):
    cnt += c[j]
  if cnt > 1:
    f1 = False


g = 0
for i in range(len(A)):
  g = gcd(g, A[i])
if g != 1:
  f2 = False

if f1:
  print("pairwise coprime")
elif f2:
  print("setwise coprime")
else:
  print("not coprime")

Solution (Python):
N=int(input())
from math import gcd
from functools import reduce
l=list(map(int,input().split()))
sw=0
c=[0]*1000001
for i in l:
   c[i]+=1
if all(sum(c[i::i])<=1 for i in range(2,1000001)):
  print("pairwise coprime")
elif reduce(gcd,l)==1:
   print("setwise coprime")
else:
   print("not coprime")

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

n = int(input())
A = list(map(int, input().split()))
res = ['pairwise coprime', 'setwise coprime', 'not coprime']

MAX = 10 ** 6 + 1000
dp = [i for i in range(MAX)]

for x in range(2, MAX):
    if dp[x] < x: continue
    for y in range(x + x, MAX, x):
        if dp[y] == y:
            dp[y] = x

def get_factor(n):
    factors = []
    while n > 1:
        factors.append(dp[n])
        n //= dp[n]
    return factors

prime_factors = []
for a in A:
    factor = get_factor(a)
    factor_set = list(set(factor))
    prime_factors.extend(factor_set)

if len(prime_factors) == len(set(prime_factors)):
    print(res[0])
elif reduce(gcd, A) == 1:
    print(res[1])
else:
    print(res[2])

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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

A_max = max(A)
prime = [[] for _ in range(A_max + 1)]
for i in range(2,A_max + 1):
    if prime[i] == []:
        n = i
        while n <= A_max:
            prime[n].append(i)
            n += i

li = [0] * (A_max + 1)
for a in A:
    for p in prime[a]:
        li[p] += 1


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

Solution (Python):
from collections import defaultdict
from math import gcd

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

num = 10 ** 6
primes = [0] * (num + 1)
primes[0] = 1
primes[1] = 1

for i in range(2, num + 1):
    if primes[i] != 0:
        continue

    cnt = 1
    while i * cnt <= num:
        primes[i * cnt] = i
        cnt += 1


def func(n):
    res_dic = defaultdict(int)
    while n > 1:
        x = primes[n]
        res_dic[x] += 1
        n //= x

    return res_dic


pairwise = True
cnt_dic = defaultdict(int)
for a in A:
    dic = func(a)

    for k in dic.keys():
        cnt_dic[k] += 1
        if cnt_dic[k] > 1:
            pairwise = False
            break

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

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

Solution (Python):
import math

def eratosthenes():
    erat = [0 for _ in range(max_a+1)]
    
    pair = True
    
    for i in range(2, max_a+1):
        cnt = 0
        if not erat[i]:
            for res in range(i, max_a+1, i):
                if res in set_a:
                    cnt += 1
                erat[res] = i
                if cnt > 1:
                    pair = False
                    break
        if not pair:
            break
    return pair


n = int(input())
a = [int(x) for x in input().split()]
max_a = max(a)
set_a = set(a)

if eratosthenes() and len(set_a) == n - max(0, a.count(1)-1):
    print('pairwise coprime')
else:
    res = a[0]
    for i in range(n):
        res = math.gcd(res, a[i])
    if res == 1:
        print('setwise coprime')
    else:
        print('not coprime')

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

N = int(input())
A = list(map(int, input().split()))
era = [-1]*(10**6+1)

for i in range(2, 10**6+1):
    if era[i]==-1:
        era[i] = i

        for j in range(2*i, 10**6+1, i):
            if era[j]==-1:
                era[j] = i

s = set()
flag = True

for Ai in A:
    f = []
    t = Ai
    
    while t>1:
        f.append(era[t])
        t //= era[t]
    
    for fi in f:
        if fi in s:
            flag = False
    
    for fi in f:
        s.add(fi)

if flag:
    print('pairwise coprime')
    exit()

G = 0

for Ai in A:
    G = gcd(G, Ai)

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)    

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

pairwise_flg = True
for num in A:
    table[num] += 1

for i in range(2, 10**6+5):
    cnt = 0
    for j in range(i, 10**6+5, i):
        cnt += table[j]
    if cnt > 1:
        pairwise_flg = False    
if pairwise_flg:
    print("pairwise coprime")
    exit()

gcd_val = 0
for num in A:
    gcd_val = gcd(gcd_val, num)

if gcd_val == 1:
    print("setwise coprime")
    exit()
print("not coprime")

Solution (Python):
from collections import *
def gcd(a,b):
    if a%b==0:return(b)
    else:return(gcd(b,a%b))

def soinsuu(n):
    visited=defaultdict(int)
    for i in range(2,round(n**.5)+1):
        while n%i==0:
            n//=i
            visited[i]+=1
    if n>1:
        visited[n]+=1
    return(visited)

N=int(input())
A=list(map(int,input().split()))
visited=set()
flg=False
for a in A:
    for i in soinsuu(a):
        if i in visited:
            flg=True
            break
        else:
            visited.add(i)

    if flg:
        break
else:
    print("pairwise coprime")
    exit()

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



if n>1:
    print("not coprime")
else:
    print("setwise coprime")

Solution (Python):

from math import sqrt
from collections import Counter

def gen_primes(X):
    D = [0] * (X+1)
    is_prime = [True for _ in range(0, X+1)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for n in range(2, int(sqrt(X))+1):
        if is_prime[n]:
            primes.append(n)
            j = n*2
            D[n] = n
            while j <= X:
                is_prime[j] = False
                if D[j] == 0:
                    D[j] = n
                j += n
    for n in range(int(sqrt(X)), X+1):
        if is_prime[n]:
            D[n] = n
            primes.append(n)
    return primes, D


def solve(A):
    N = len(A)
    primes, D = gen_primes(10**6)
    C = [0] * (primes[-1]+1)

    for a in A:
        a_ = a
        while a > 1:
            d = D[a]
            while a % d == 0:
                a //= d
            C[d] += 1
        
    M = max(C)
    if M <= 1:
        print("pairwise coprime")
    elif M != N:
        print("setwise coprime")
    else:
        print("not coprime")


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

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

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

L = [0]*(M+1)
for a in A:
    L[a] += 1

num = 0
for i in range(2, M+1):
    if P[i] > -1:
        continue
    cnt = 0
    j = i
    while j <= M:
        cnt += L[j]
        j += i
    num = max(num, cnt)


if num == 1 or max(A) == 1:
    print("pairwise coprime")
elif num == N:
    print("not coprime")
else:
    print("setwise coprime")

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

c = [0]*(10**6 + 3)
for i in a:
    c[i] += 1

pairwise = True
for i in range(2,10**6+1):
    if sum(c[::i])>1:
        pairwise = False

g = 0
for i in a:
    g = math.gcd(g,i)
if g == 1:
    setwise = True
else:
    setwise = False

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

Solution (Python):
from sys import stdin

input = stdin.readline
import math

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

    cur = 0
    for i in a:
        cur = math.gcd(i, cur)
    if cur > 1:
        print('not coprime')
        return
    m = max(a)
    prime = [True] * (m+1)
    c = {}
    for i in a:
        c[i] = c.get(i,0) + 1
    for i in range(2,m+1):
        if prime[i]:
            cnt = 0
            for j in range(i,m+1,i):
                prime[j] = False
                cnt += c.get(j,0)
                if cnt > 1:
                    print('setwise coprime')
                    return
    print('pairwise coprime')
if __name__ == '__main__':
    solve()

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

MAX = max(A)


AR = [0] * (MAX+1)
V = [False] * (MAX+1)
for i in range(N): AR[A[i]] += 1
pairwise, setwise = True, True


for i in range(2, MAX+1):
    if V[i]: continue
    cnt, j = 0, i
    while j < MAX+1:
        cnt += AR[j]
        V[j] = True
        j += i
    if cnt > 1: pairwise = False
    if cnt == len(A): setwise = False

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

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

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



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)
    a.sort()
    return a


primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i])
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1


if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())


if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")

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

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



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)
    a.sort()
    return a


primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i])
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1


if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())


if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")

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



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




def prime_factorize(n, prime_list):
    a = []
    for p in prime_list:
        if p * p > n:
            break
        while True:
            if n % p == 0:
                a.append(p)
                n //= p
            else:
                break
    if n != 1:
        a.append(n)
    a.sort()
    return a



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

data = set(get_sieve_of_eratosthenes(10**6))

primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i], data)
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1



if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):

"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

"""
コーナーケース１:
    重複があるとき　not coprime(※これが誤り)
    ただし、1の重複は除く

コーナーケース:
    重複があるとき　pairwise coprime ではない
    setwise coprimeの可能性はある
    ただし、１の重複は
"""
import math
C = 10**6

N = int(input())
judge = [0]+[False]*C
A =list()
f = True
for a in input().split():
    if judge[int(a)] == True and int(a) != 1:
        f = False
    judge[int(a)]=True
    A.append(int(a))
d = [False]+[True]*C


def solve(f):
    flag = True
    
    for i in range(2,C+1):
        count = 0
        if d[i] == True:
            for j in range(i,C+1,i):
                if judge[j] == True:
                    count += 1
                if count == 2:
                    flag = False
                    break
                d[j] = False
        if not flag:
            break
    
    if flag == True and f == True:
        return "pairwise coprime"
    ans = A[0]
    
    for i in range(N):
        ans = math.gcd(ans,A[i])
    
    if ans == 1:
        return "setwise coprime"
    return "not coprime"

print(solve(f))

Solution (Python):

"""
Created on Fri Sep 18 07:10:00 2020

@author: liang
"""



"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

"""
コーナーケース１:
    重複があるとき　not coprime
    ただし、1の重複は除く
"""
import math
C = 10**6
N = int(input())
judge = [False]*(C+1)
A = [int(x) for x in input().split()]

f = True
for a in A:
    if judge[a] == True and a != 1:
        f = False
    judge[int(a)]=True



def solve(f):
    
    ans = A[0]
    
    for i in range(N):
        ans = math.gcd(ans,A[i])
    
    if ans != 1:
        return "not coprime"
    
    flag = True
    
    for i in range(2,C+1):
        count = 0
       
        for j in range(i,C+1,i):
            if judge[j] == True:
                count += 1
            if count == 2:
                flag = False
                break
        
        if not flag:
            break
    
    if flag == True and f == True:
        return "pairwise coprime"
    
    return "setwise coprime"

print(solve(f))

Solution (Python):

"""
Created on Fri Sep 18 07:10:00 2020

@author: liang
"""



"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

"""
コーナーケース１:
    重複があるとき　not coprime
    ただし、1の重複は除く
"""
import math
C = 10**6
N = int(input())
judge = [False]*(C+1)
A = [int(x) for x in input().split()]

f = True
for a in A:
    if judge[a] == True and a != 1:
        f = False
    judge[int(a)]=True



def solve(f):
    
    ans = A[0]
    
    for i in range(N):
        ans = math.gcd(ans,A[i])
    
    if ans != 1:
        return "not coprime"
    
    flag = True
    
    for i in range(2,C+1):
        count = 0
       
        for j in range(i,C+1,i):
            if judge[j] == True:
                count += 1
            if count == 2:
                flag = False
                break
        
        if not flag:
            break
    
    if flag == True and f == True:
        return "pairwise coprime"
    
    return "setwise coprime"

print(solve(f))

Solution (Python):
from sys import exit

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


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

is_prime = [True]*(10**6+10)
is_prime[0] = False
is_prime[1] = False

for i in range(2,10**6+10):
    if not is_prime[i]:
        continue
    else:
        for j in range(i*i,10**6+10,i):
            is_prime[j] = False

g = 0
for i in A:
    g = gcd(g,i)

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

prime = [p for p in A if is_prime[p]]
used = [False]*(10**6+10)
notprime = [np for np in A if not is_prime[np]]
small_prime = [p for p in range(10**3+10) if is_prime[p]]


for p in prime:
    used[p] = True

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

print("pairwise coprime")

Solution (Python):
import sys
import re
import queue
import collections
import math
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext

def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

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

def main():
	N = i_input()
	A = i_list()

	d = dict()

	max_A = max(A)
	count_list = []

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


	for i in range(0,max(A)):
		count_list.append(0)

	for a in A:
		tmp = set()
		while a > 1:
			tmp.add(sieve[a])
			a //= sieve[a]

		for p in tmp:
			count_list[p-1] += 1


	if (max(count_list)<=1):
		print("pairwise coprime")
	elif(gcd_list(A)==1):
		print("setwise coprime")
	else:
		print("not coprime")

	return

if __name__ == '__main__':
	main()

Solution (Python):
import math

N = int(input())
a = list(map(int,input().split()))
m = max(a)
c = [0] * (m+1)

for i in a:
  c[i] += 1

pairwise = True
for i in range(2, m+1, 1):
  cnt = 0
  for j in range(i, m+1, i):
    cnt += c[j]
    if cnt > 1:
      pairwise = False
      break
if pairwise:
  print("pairwise coprime")
  exit()

g = 0
for i in range(N):
  g = math.gcd(g, a[i])
if g == 1:
  print("setwise coprime")
  exit()

print("not coprime")

Solution (Python):
def gcc(x, y):
    if x == 0:return y
    return gcc(y % x, x)

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

g = 0

A.sort()

for item in A:
    g = gcc(g, item)

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

primes = []
is_prime = [True] * 1100000

is_prime[0] = is_prime[1] = False

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

A_prime = [item for item in A if is_prime[item]]
A_notprime = [item for item in A if not is_prime[item]]

used = [False] * 1100000

for item in A_prime:
    used[item] = True

for a in A_notprime:
    for p in primes:
        if a == 1:break
        if a % p != 0:continue

        if used[p]:
            print("setwise coprime")
            
            exit()

        used[p] = True

        while a % p == 0:
            a //= p

print("pairwise coprime")

Solution (Python):
def gcc(x, y):
    if x == 0:return y
    return gcc(y % x, x)

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

g = 0

A.sort()

for item in A:
    g = gcc(g, item)

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

primes = []

is_prime = [True] * 1100000

is_prime[0] = is_prime[1] = False

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

A_prime = [item for item in A if is_prime[item]]
A_notprime = [item for item in A if not is_prime[item]]

primes = [p for p in range(1100) if is_prime[p]]
used = [False] * 1100000

for item in A_prime:
    used[item] = True

for a in A_notprime:
    for p in primes:
        if a == 1:break
        if a % p != 0:continue

        if used[p]:
            print("setwise coprime")
            
            exit()

        used[p] = True

        while a % p == 0:
            a //= p

    if a > 1:
        if used[a]:
            print("setwise coprime")
            exit()
        used[a] = True


print("pairwise coprime")

Solution (Python):
import math

N = int(input())
A = list(map(int, input().split()))
m = max(A)
c = [0] * (m+1)
for i in A:
  c[i] += 1

pairwise = True
for i in range(2,m+1,1):
  cnt = 0
  for j in range(i,m+1,i):
    cnt += c[j]
  if cnt > 1:
    pairwise = False
if pairwise:
  print("pairwise coprime")
  exit()

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

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

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

c = [0]*(10**6 + 3)
for i in a:
    c[i] += 1

pairwise = True
for i in range(2,10**6+1):
    if sum(c[::i])>1:
        pairwise = False

g = 0
for i in a:
    g = gcd(g,i)
if g == 1:
    setwise = True
else:
    setwise = False

if pairwise == True:
    print("pairwise coprime")
    exit()
if setwise == True:
    print("setwise coprime")
    exit()
print("not coprime")

Solution (Python):
from math import sqrt, gcd
import sys


def osk_a(M):
    p = [i for i in range(M+1)]
    for x in range(2, int(sqrt(M))+1):
        if p[x] == x:
            for y in range(2*x, M+1, x):
                if p[y] == y:
                    p[y] = x
    return p


def main():
    n = int(sys.stdin.buffer.readline())
    a = list(map(int, sys.stdin.buffer.readline().split()))

    def g(a):
        g = 0
        for x in a:
            g = gcd(g, x)
        return g

    if g(a) > 1:
        print("not coprime")
        exit()
    p = osk_a(10**6)
    chk = set()
    while a[0] > 1:
        chk.add(p[a[0]])
        a[0] //= p[a[0]]
    for x in a[1:]:
        tmp = set()
        while x > 1:
            tmp.add(p[x])
            x //= p[x]
        if not chk.isdisjoint(tmp):
            print("setwise coprime")
            exit()
        chk |= tmp
    print("pairwise coprime")


if __name__ == "__main__":
    main()

Solution (Python):
import math
n=int(input())
a=list(map(int,input().split()))
A=max(a)
l=[i for i in range(A+1)]
for i in range(2,A+1):
  if l[i]==i:
    for j in range(1,A//i+1):
      if i*j<=A:
        l[i*j]=i

L=set()
f=0
for i in range(n):
  x=a[i]
  L2=set()
  while x!=1:
    L2.add(l[x])
    x//=l[x]
  L2=list(L2)
  for j in range(len(L2)):
    if L2[j] in L:
      f=1
    else:
      L.add(L2[j])
  if f==1:
    break
if f==0:
  print('pairwise coprime')
  exit()

y=a[0]
for i in range(1,n):
  y=math.gcd(y,a[i])
if y==1:
  print('setwise coprime')
else:
  print('not coprime')

Solution (Python):
import math
N = int(input())
A = list(map(int, input().split()))
ans1 = "pairwise coprime"
ans2 = "setwise coprime"
ans3 = "not coprime"

a = math.gcd(A[0], A[1])
for i in range(2, N):
    a = math.gcd(a, A[i])

if a==1:
    b = True
    l = [0]*(10**6+1)
    x = [0]*(10**6+1)
    x[0]=1
    x[1]=1
    for i in range(2, 10**6+1):
        if x[i]==0:
            for j in range(i, 10**6+1, i):
                x[j]=i

    for y in A:
        s=set()
        if y==1:
            continue
        elif y==x[y]:
            s |= {y}        
        else:
            while y!=x[y]: 
                s|={x[y]}  
                y//=x[y]
                if y==x[y]:
                    s|={x[y]}
                    break
        for i in s:
            l[i]+=1
            if l[i]>=2:
                b=False
                break
                
        
    if b:
        print(ans1)
    else:
        print(ans2)
        
        
    
else:
    print(ans3)

Solution (Python):

from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


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





def LI(): return list(map(int, sys.stdin.buffer.readline().split()))




def I(): return int(sys.stdin.buffer.readline())





def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()




def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')







def IR(n): return [I() for i in range(n)]







def LIR(n): return [LI() for i in range(n)]







def SR(n): return [S() for i in range(n)]







def LSR(n): return [LS() for i in range(n)]







def SRL(n): return [list(S()) for i in range(n)]


n = I()
a = LI()

mx = max(a)
table = [0] * (mx + 1) 
for x in a:
  table[x] += 1
g = 0

for x in a:
  g = gcd(g, x)
for i in range(2, mx + 1):
  c = 0

  for j in range(i, mx + 1, i):
    c += table[j]

  if c > 1:
    if g == 1:
      print("setwise coprime")
    else:
      print("not coprime")
    exit(0)
print("pairwise coprime")

Solution (Python):

import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000


def primeNumList(n):
    d = [d for d in range(0, n+1)]
    if n < 2:
        return [[],d]
    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
            d[j] = i
    return [[i for i in range(n + 1) if is_prime[i]], d]

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

    
    amax = max(aList)
    pl = primeNumList(amax)
    countList = [0] * (amax+1)

    if pl[0] != []:
        for a in aList:
            at = a
            sl = []
            while at != 1:
                s = pl[1][at]
                sl.append(s)
                at = int(at / s)
            sl2 = list(set(sl))
            for s in sl2:
                countList[s] += 1
        m = max(countList)
    else:
        m = 0

    
    if m == len(aList):
        print("not coprime")
    elif m >= 2:
        print("setwise coprime")
    else:
        print("pairwise coprime")


if __name__ == '__main__':
    main()

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

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

for x in a:
    num[x] += 1

f = 1
for i in range(2, 10**6+1):
    s = sum(num[i::i])
    if s == n:
        print("not coprime")
        exit()
    if s > 1 :
        f = 0
if f == 0:
    print("setwise coprime")
else:
    print("pairwise coprime")

Solution (Python):
def f1(n):
    max_p = int(n ** 0.5)
    p = 0  
    pl = []  
    el = [i for i in range(2, n + 1)]  
    D = [i for i in range(n + 1)]
    while p <= max_p:
        nxt = []
        p = el[0]
        pl.append(p)
        for e in el:
            if e % p == 0:
                D[e] = p
            else:
                nxt.append(e)
        el = nxt
    for e in el:
        D[e] = e
    pl.extend(el)
    return D, pl


def f2(n, D):
    s = set()
    x = n
    while x > 1:
        p = D[x]
        s.add(p)
        x = x // p
    return s


from math import gcd


def is_nc(n, al):
    g = al[0]
    for i, a in enumerate(al):
        if i == 0:
            continue
        else:
            g = gcd(g, a)
            if g == 1:
                return False
    return True


def is_sc(n, al):
    max_al = max(al)
    if max_al == 1:
        return False
    D, pl = f1(max_al)
    count = {p: 0 for p in pl}
    for a in al:
        p_s = f2(a, D)
        for p in p_s:
            if count[p] == 1:
                return True
            else:
                count[p] += 1
    return False


n = int(input())
al = list(map(int, input().split()))
if is_nc(n, al):
    print('not coprime')
elif is_sc(n, al):
    print('setwise coprime')
else:
    print('pairwise coprime')

Solution (Python):
from math import gcd

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


ans = 0
cnt = [0] * (max(a) + 1)
for ai in a:
    ans = gcd(ans, ai)
    cnt[ai] += 1

if ans != 1:
    print('not coprime')
elif any(sum(cnt[i::i]) > 1 for i in range(2, max(a) + 1)):
    print('setwise coprime')
else:
    print('pairwise coprime')

Solution (Python):
from math import gcd

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


ans = 0
cnt = [0] * (max(a) + 1)
for ai in a:
    ans = gcd(ans, ai)
    cnt[ai] += 1

if ans != 1:
    print('not coprime')
elif any(sum(cnt[i::i]) > 1 for i in range(2, max(a) + 1)):
    print('setwise coprime')
else:
    print('pairwise coprime')