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

MOD = 10 ** 9 + 7
INFI = 10**10

import math
from collections import deque
import itertools
import heapq

from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint




def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default




def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def soinsubunkai_e(n,m):
    a = set()
    i = 1
    while n>1:
        a.add(m[n])
        n=n//m[n]
    nokori=n
    a.add(nokori)
    return a

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def era(n):
    b=[i for i in range(n+1)]
    for i in range(2,int(math.sqrt(n)+10)):
        j=1
        temp=i*j
        while temp<=n:
            b[temp]=min(i,b[temp])
            temp+=i
    return b


def main():
    
    n=int(input())
    a=list(map(int,input().split()))
    sosu=[]
    memo = defaultdict(int)
    ccc=era(10**6)
    for i in range(n):
        if a[i]!=1:
            temp=soinsubunkai_e(a[i],ccc)
        else:
            temp={}
        for j in temp:
            memo[j]+=1

    memo.pop(1,None)
 
 
 
    if len(memo)>=1:
        mmm=max(memo.values())
    else:
        mmm=1
    if mmm<=1:
        print("pairwise coprime")
    elif mmm<n:
        print("setwise coprime")
    else:
        print("not coprime")








if __name__ == "__main__":

    main()

Solution (Python):
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k
    if n > 1:return {n} 
    return set(ret)
def main():
    n=int(input())
    a=list(map(int,input().split()))
    g=a[0]
    for i in a[1:]:g=gcd(g,i)
    if g!=1:
        print("not coprime")
        exit()
    ans=0
    s=set()
    for i in a:
        p=primeFactor(i)
        ans+=len(p)
        s|=p
    if ans!=len(s):print("setwise coprime")
    else:print("pairwise coprime")
if __name__ == "__main__":
    main()

Solution (Python):
def max(a,b):
    if a>b:
        return a
    else:
        return b
 
def min(a,b):
    if a>b:
        return b
    else:
        return a
 
def gcd(a,b):
    a,b = max(a,b),min(a,b)
    while a%b!=0:
        a,b = b,a%b
    return b
 
 
def gcdl(A):
    if len(A)==2:
        return gcd(A[0],A[1])
    elif len(A)==1:
        return A[0]
    else:
        return gcd(gcdl(A[:len(A)//2]),gcdl(A[len(A)//2:]))


def sieve_of_eratosthenes(n):
    p = 2
    D = [0]*(n+1)
    while p**2<=n:
        if D[p]==0:
            k = p*p
            while k <= n:
                if D[k] == 0:
                    D[k] = p
                k += p
        p+=1
    return D

import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

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

    F = set([])
    flag = True
    for a in A:
        b = a
        fact = set([])
        while D[b]>0:
            fact.add(D[b])
            b//=D[b]
        if b!=1:
            fact.add(b)
        for p in fact:
            if p in F:
                flag=False
                break
            else:
                F.add(p)

    if flag:
        print("pairwise coprime")
    else:
        if gcdl(A)==1:
            print("setwise coprime")
        else:
            print("not coprime")

if __name__ == '__main__':
    main()

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

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

def erat():
    end = 10 ** 6 + 1
    t = [False if i == 0 or i == 1 else True for i in range(end)]
    ret = [0 for i in range(end)]

    for i in range(2, end):
        if t[i]:
            for j in range(i * 2, end, i):
                t[j] = False
                if not ret[j]:
                    ret[j] = i
            ret[i] = i
    return ret

tmp = A[0]
for i in A[1:]:
    tmp = gcd(tmp, i)
isS = True if tmp == 1 else False
isP = True

e = erat()

D = dict(iter([(i, False) for i in range(10 ** 6 + 1)]))
for i in A:
    tmp = set()
    while i != 1:
        tmp.add(e[i])
        i //= e[i]
    for i in tmp:
        if D[i]:
            isP = False
            break
        else:
            D[i] = True
    if not isP:
        break

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

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

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

def primes(n):
    is_prime = [False] * 2 + [True] * (n - 1)
    for i in range(2, int(n ** 0.5) + 1): 
        if not is_prime[i]: continue
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def pairwise_coprime(a):
    max_a = max(a)
    in_a = [False] * (max_a + 1)
    for num in a:
        if num >= 2 and in_a[num]:
            return False
        in_a[num] = True

    ps = primes(max_a)  

    for p in ps:
        cnt = 0
        for i in range(p, max_a + 1, p):
            if in_a[i]:
                cnt += 1
            if cnt > 1:
                return False

    return True



n = int(input())
a = [int(x) for x in input().split()]

if gcd_list(a) == 1:  
    if pairwise_coprime(a):
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
import math
def factorize(x):
    if x==0 or x==1:
        return set()
    return factorize(x//mind[x])|{mind[x]}

N=int(input())
A=sorted(map(int,input().split()))
m=max(A)
arr=[True]*(m+1)
mind=[i for i in range(m+1)]
arr[0],arr[1]=False,False
for i in range(2,m+1):
    if arr[i]==False:
        continue
    for j in range(2,m+1):
        if i*j>m:
            break
        arr[i*j]=False
        mind[i*j]=min(mind[i*j],i)
isok=True
s=set()
for i in range(N):
    t=factorize(A[i])
    for k in t:
        if k in s:
            isok=False
            break
        s.add(k)
    if not isok:
        break
if isok:
    print('pairwise coprime')
    exit()
T=A[0]
for i in range(1,N):
    T=math.gcd(T,A[i])

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

Solution (Python):
import numpy as np
from numba import njit
def main():
    N = int(input())
    nlist = list(map(int, input().split()))

    def gdc(x, y):
        b = max(x, y)
        s = min(x, y)
        r = b % s
        if r == 0:
            return s
        else:
            return gdc(s, r)

    scp = False
    pcp = False

    sgdc = nlist[0]
    for n in nlist:
        sgdc = gdc(sgdc, n)
        if sgdc == 1:
            scp = True
            break

    if not scp:
        print('not coprime')
        exit()

    pcheckl = [0] * (10**6+1)
    for n in nlist:
        pcheckl[n] = 1

    pcp = all([sum(pcheckl[i::i]) <= 1 for i in range(2, 10**6+1)])

    if pcp:
        print('pairwise coprime')
    elif scp:
        print('setwise coprime')

if __name__ == '__main__':
    main()

Solution (Python):

import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations


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


def primeFactors(n,l): 
    q=set()    
    f=0
    while n % 2 == 0: 
    	if l[2] and f==0:
    		return False
    	l[2]=True
    	n = n / 2     
    	f=1 

    for i in range(3,int(math.sqrt(n))+1,2): 
        f=0
        while n % i== 0:
        	if l[i] and f==0:
        		return False
        	l[i]=True
        	n = n / i 
        	f=1
              
    if n > 2: 
    	if l[n]:
    		return False
    	l[n]=True

    
    return True

n=int(input())
l=[int(x) for x in input().split()]

d={i:False for i in range(1,max(l)+1)}
ans=1
for i in range(n):
	f=primeFactors(l[i],d)
	if not f:
		ans=0
		break



if ans:
	print('pairwise coprime')
else:
	a=l[0]
	b=l[1]
	gc=gcd(a,b)
	for i in range(2,n):
		gc=gcd(gc,l[i])
		if gc==1:
			break
	if gc==1:
		print('setwise coprime')
	else:
		print('not coprime')

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

N = int(input())
A_lst = list(map(int, input().split()))
lst=[0]*(10**6+1)


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

ans = 'not coprime'
GCD = A_lst[0]
for i in range(N):
  GCD = math.gcd(GCD, A_lst[i])
  
if GCD != 1:
  print(ans)
else:
  ans = 'setwise coprime'
  post = 1
  visited = [0]*(10**6+1)
  for i in range(N):
    a = A_lst[i]
    while a > 1:
      dv = lst[a]
      if visited[dv]:
        post = 0
        break
      while a % dv == 0:
        a //= dv
      visited[dv] = 1
  
  if post:
    ans = 'pairwise coprime'
  print(ans)

Solution (Python):
import numpy as np
from numba import njit
def main():
    N = int(input())
    nlist = np.array(list(map(int, input().split())))

    def gdc(x, y):
        b = max(x, y)
        s = min(x, y)
        r = b % s
        if r == 0:
            return s
        else:
            return gdc(s, r)

    scp = False
    pcp = False

    sgdc = nlist[0]
    for n in nlist:
        sgdc = gdc(sgdc, n)
        if sgdc == 1:
            scp = True

    if not scp:
        print('not coprime')
        exit()

    pcheckl = [0] * (10**6+1)
    for n in nlist:
        pcheckl[n] = 1

    pcp = all([sum(pcheckl[i::i]) <= 1 for i in range(2, 10**6+1)])

    if pcp:
        print('pairwise coprime')
    elif scp:
        print('setwise coprime')

if __name__ == '__main__':
    main()

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

def prime(n):
    p = []
    min_p = [0 for i in range(n - 1)]
    flag = [True] * (n - 1)
    for i in range(n - 1):
        if flag[i] == True:
            p.append(i + 2)
            num = i
            while num <= n - 2:
                if flag[num] == True:
                    min_p[num] = i + 2
                flag[num] = False
                num += i + 2
    return p, min_p

gcd = 0
for i in range(n):
    gcd = math.gcd(gcd, a[i])
if gcd != 1:
    print("not coprime")
else:
    p = prime(max(a))
    p_list = {i:0 for i in p[0]}
    min_p = p[1]
    flag = True
    for i in a:
        temp = set()
        while i != 1:
            temp.add(min_p[i - 2])
            i //= min_p[i - 2]
        for j in temp:
            if p_list[j] == 1:
                flag = False
                break
            else:
                p_list[j] += 1
        if flag == False:
            print("setwise coprime")
            break
    else:
        print("pairwise coprime")

Solution (Python):
import math

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort(reverse=True)
primes = set()
flag = True
for i in range(n):
  num = lst[i]
  count = 0
  while num % 2 == 0:
    num //= 2
    count += 1
    if pow(2, count) in primes:
      flag = False
      break
    primes.add(pow(2, count))
  f = 3
  while f <= math.sqrt(lst[i]) and flag:
    count = 0
    while num % f == 0:
      num //= f
      count += 1
      if pow(f, count) in primes:
        flag = False
        break
      primes.add(pow(f, count))
    f += 2
  if num == 1:
    continue
  if num in primes or not flag:
    flag = False
    break
  primes.add(num)
if not flag:
  a = lst[0]
  for i in range(1, n):
    b = lst[i]
    c = math.gcd(a, b)
    a = c
  if a != 1:
    print('not coprime')
  else:
    print('setwise coprime')
else:
  print('pairwise coprime')

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

pairwise = True
setwise = False

M = 10**6+1

count = [0 for _ in range(M)]

for a in A:
    count[a] += 1

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

if max_count == N:
    print('not coprime')
elif max_count >= 2:
    print('setwise coprime')
else:
    print('pairwise coprime')

Solution (Python):
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k
    if n > 1:return {n} 
    return set(ret)
def main():
    n=int(input())
    a=list(map(int,input().split()))
    g=a[0]
    for i in a[1:]:g=gcd(g,i)
    if g!=1:
        print("not coprime")
        exit()
    ans=0
    s=set()
    for i in a:
        p=primeFactor(i)
        ans+=len(p)
        s|=p
    if ans!=len(s):print("setwise coprime")
    else:print("pairwise coprime")
if __name__ == "__main__":
    main()

Solution (Python):
from math import gcd

N = int(input())
A = list(map(int, input().split()))
sieve = [1] * (10**6+1)
for i in range(2, 10**6 + 1):
	if sieve[i] == 1:
		sieve[i] = i
		j = 2
		while(j * i <= 10**6):
			sieve[j * i] = i
			j += 1

g = A[0]
for i in range(1, N):
	g = gcd(g, A[i])
	
if g != 1:
	print("not coprime")
else:
	s = set()
	for i in range(N):
		st = set()
		while(A[i] > 1):
			d = sieve[A[i]]
			st.add(d)
			A[i] //= d
		for p in st:
			if p in s:
				print("setwise coprime")
				exit()
			s.add(p)
	print("pairwise coprime")

Solution (Python):
import sys
import math
import collections
import bisect
import itertools
import decimal




INF = 10 ** 20
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))




def main():
    n = ni()
    a = na()

    tmp = len(a)

    
    def Eratosthenes(n):  
        a = [[] for _ in range(n + 1)]
        if n >= 2:
            for i in range(2, n + 1):
                if len(a[i]) == 0:
                    for j in range(i, n + 1, i):
                        a[j].append(i)
        return a

    l = max(a)
    p = Eratosthenes(l)
    cnt = [0 for _ in range(l + 1)]

    pc = True
    tc = True

    for ai in a:
        for pi in p[ai]:
            cnt[pi] += 1
            if cnt[pi] >1:
                pc = False
            if cnt[pi] == n:
                tc = False
                break


    if pc:
        print("pairwise coprime")
    elif tc:
        print("setwise coprime")
    else:
        print("not coprime")

if __name__ == '__main__':
    main()

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


def sieve_table(n):
    table = [0] * (n+1)
    for i in range(2, n+1):
        if table[i] > 0:
            continue

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


def factorization_from_table(x, table):
    res = set()
    while x > 1:
        res.add(table[x])
        x //= table[x]
    
    return res

table = sieve_table(10 ** 6)
set_primes = set()

flg = True
for i in range(n):
    res = factorization_from_table(a[i], table)
    if len(set_primes & res) > 0:
        flg = False
        break
    
    for x in res:
        set_primes.add(x)
        
if flg:
    print('pairwise coprime')
else:
    from math import gcd
    tmp = a[0]
    for i in range(1, n):
        tmp = gcd(tmp, a[i])
    
    if tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Solution (Python):
import sys
import math
import collections
import bisect
import itertools
import decimal




INF = 10 ** 20
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))





class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

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

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    n = ni()
    a = na()

    tmp = len(a)

    
    def Eratosthenes(n):  
        a = [[] for _ in range(n + 1)]
        if n >= 2:
            for i in range(2, n + 1):
                if len(a[i]) == 0:
                    for j in range(i, n + 1, i):
                        a[j].append(i)
        return a

    l = max(a)
    p = Eratosthenes(l)
    cnt = [0 for _ in range(l + 1)]

    pc = True
    tc = True

    for ai in a:
        for pi in p[ai]:
            cnt[pi] += 1
            if cnt[pi] >1:
                pc = False
            if cnt[pi] == n:
                tc = False
                break


    if pc:
        print("pairwise coprime")
    elif tc:
        print("setwise coprime")
    else:
        print("not coprime")

if __name__ == '__main__':
    main()

Solution (Python):
class Sieve:
    """区間[2,n]の値を素因数分解する"""

    def __init__(self, n=1):
        primes = []
        f = [0] * (n + 1)
        f[0] = f[1] = -1
        for i in range(2, n + 1):  
            if f[i]:
                continue
            primes.append(i)
            f[i] = i  
            for j in range(i * i, n + 1, i):  
                if not f[j]:
                    f[j] = i  
        self.primes = primes
        self.f = f

    def is_prime(self, x) -> bool:  
        return self.f[x] == x

    def factor_list(self, x) -> list:  
        res = []
        while x != 1:
            res.append(self.f[x])
            x //= self.f[x]
        return res

    def factor(self, x) -> list:  
        fl = self.factor_list(x)
        if not fl:
            return []
        res = [[fl[0], 0]]
        for p in fl:
            if res[-1][0] == p:
                res[-1][1] += 1
            else:
                res.append([p, 1])
        return res


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

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

    setwise = False

    sv = Sieve(10 ** 6)
    for p in sv.primes:
        e = p
        cnt = 0
        while e <= 10 ** 6:
            if B[e]:
                cnt += B[e]
            e += p
        if cnt == N:
            print('not coprime')
            return
        elif cnt > 1:
            setwise = True

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


if __name__ == '__main__':
    main()

Solution (Python):
import base64
import subprocess


exe_bin = "e??420s

exe_bin = base64.b85decode(exe_bin)

with open("./kyomu", 'wb') as f:
    f.write(exe_bin)

subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

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


N = I()
A = LI()


from math import gcd

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

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


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

for d in range(2,5*10**5+1):
    a = sum(B[i] for i in range(d,10**6+1,d))
    if a >= 2:
        print('setwise coprime')
        break
else:
    print('pairwise coprime')

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

N = int(input())
A_lst = list(map(int, input().split()))
lst=[0]*(10**6+1)


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

ans = 'not coprime'
GCD = A_lst[0]
for i in range(N):
  GCD = math.gcd(GCD, A_lst[i])
  
if GCD != 1:
  print(ans)
else:
  ans = 'setwise coprime'
  post = 1
  visited = [0]*(10**6+1)
  for i in range(N):
    a = A_lst[i]
    while a > 1:
      dv = lst[a]
      if visited[dv]:
        post = 0
        break
      while a % dv == 0:
        a //= dv
      visited[dv] = 1
  
  if post:
    ans = 'pairwise coprime'
  print(ans)

Solution (Python):
n,a=int(input()),list(map(int,input().split()))
g=0
from math import gcd
for i in a:g=gcd(i,g)
if g!=1:print("not coprime")
else:
    from collections import defaultdict
    memo=defaultdict(int)
    for i in a:
        for p in range(2,int(i**.5)+1):
            if i%p==0:
                while i%p==0:i//=p
                if memo[p]:
                    print("setwise coprime");exit()
                memo[p]+=1
        if i!=1:
            if memo[i]:print("setwise coprime");exit()
            memo[i]+=1
    print("pairwise coprime")

Solution (Python):
import base64
import subprocess


exe_bin = "e??420s

exe_bin = base64.b85decode(exe_bin)

with open("./kyomu", 'wb') as f:
    f.write(exe_bin)

subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Solution (Python):
import math
from collections import deque

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

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    a,b = b,a
while a % b != 0:
    a, b = b, a % b
    if n == 2 and b == 1:
        ans = "pairwise coprime"
        failed = True

for i in range(2, n):
    a = als[i]
    if a < b:
        a,b = b,a 
    while a % b != 0:
        a, b = b, a % b
if b == 1:
    ans = "setwise coprime"
    

existeven = False

failed = False

for i in range(n):
    if als[i] >= 2 and als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

maxa = max(als)

afterchecklist = deque([])


if not failed:
    for i in range(3, int(math.sqrt(maxa))+2, 2):
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                afterchecklist.append(als[j]/i)
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        for i in list(afterchecklist):
            existfactrial = False
            failed = False
            for j in range(n):
                if i != 1 and als[j] >= i and als[j]%i == 0:
                    if existfactrial:
                        failed = True
                        break
                    else:
                        existfactrial = True
            if failed:
                break
        if not failed:
            ans = "pairwise coprime"

print(ans)

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

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

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

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

    print("pairwise coprime")
resolve()