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

Solution (Python):
def 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

from collections import defaultdict
def factorize(n,dd):
    
    for i in range(2,int(n**0.5)+1):
        flag=True
        while n%i==0 and n>0:
            if flag:
                if dd[i]>0:
                    return False
                else:
                    flag=False
            dd[i]+=1
            n//=i
    if n>1:
        if dd[n]>0:
            return False
        dd[n]+=1
    
    return True

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

import sys

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

def main():
    N = int(input())

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

    B = [a for a in A if a!=1]

    if len(B)<=1:
        print("pairwise coprime")
    else:
        N = len(B)
        if N>78498:
            if len(B)!=len(A):
                print("setwise coprime")
            else:
                print("not coprime")
        else:
            dd = defaultdict(int)
            flag=True
            for b in B:
                if factorize(b,dd)==False:
                    flag=False
                    break
            if flag:
                print("pairwise coprime")
            else:
                if len(B)!=len(A):
                    print("setwise coprime")
                elif gcdl(B)==1:
                    print("setwise coprime")
                else:
                    print("not coprime")        
        
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]

def make_sfp(N):
    F = [False] * (N + 1)
    P = [10 ** 7] * (N + 1)
    for i in range(2, N + 1):
        if F[i]:
            continue

        P[i] = i
        for j in range(i, N + 1, i):
            F[j] = True
            P[j] = min(P[j], i)
    return P


def dev_p(P, n):
    S = set()
    while n != 1:
        S.add(P[n])
        n //= P[n]
        
    return S


def main():
    N = int(input())
    A = read_list()
    D = dict()
    P = make_sfp(max(A))

    for a in A:
        S = dev_p(P, a)
        for s in S:
            D[s] = D.setdefault(s, 0) + 1
    
    is_pairwise = True
    for v in D.values():
        if v == N:
            print("not coprime")
            return
        elif v >= 2:
            is_pairwise = False
    
    print("pairwise coprime" if is_pairwise else "setwise coprime")
        

if __name__ == "__main__":
    main()

Solution (Python):
def pair (inp):
    from collections import Counter
    z=max(inp)
    arr=[1]*(z+1)
    c=Counter(inp)
    c[1]=0
    if max(c.values())>=2:
        return -1
    for i in range(2,z+1):
        if arr[i]==1:
            k=2
            if c[i]>=1:
                f=1
            else:
                f=0
            while k*i<len(arr):
                arr[k*i]=0
                if c[k*i]!=0:
                    f+=c[k*i]
                k+=1
            if f>=2:
                return -1
    return 1
def gcd (a,b):
    if a%b==0:
        return b
    if b%a==0:
        return a
    if a>b:
        return gcd(b,a%b)
    if b>a:
        return gcd(a,b%a)
n=int(input())
arr=list(map(int,input().split()))
if pair(arr)==1:
    print ('pairwise coprime')
else:
    k=arr[0]
    for i in range(1,len(arr)):
        k=gcd(k,arr[i])
        if k==1:
            break
    if k==1:
        print ('setwise coprime')
    else:
        print ('not coprime')

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")
def primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass


def solve():
    n = II()
    a = LI()
    x = 1
    if 1 in a:
        x = 0
    a = [i for i in a if i != 1]
    M = 10 ** 6 + 1
    p = [True] * M
    p[0] = False
    p[1] = False
    d = [-1] * M
    for xi in range(2, M):
        if p[xi]:
            d[xi] = xi
            for i in range(xi * 2, M, xi):
                p[i] = False
                if d[i] == -1:
                    d[i] = xi
    res = defaultdict(int)
    flg = 0
    for ai in a:
        tmp = []
        if d[ai] == -1:
            res[ai] = 1
            tmp = [ai]
        else:
            while d[ai] != -1:
                tmp.append(d[ai])
                ai = ai // d[ai]
        for t in set(tmp):
            if res[t]:
                flg = 1
            res[t] = 1
        if flg:
            break
    else:
        print("pairwise coprime")
        return
    g = a[0]
    for i in a:
        g = math.gcd(g, i)
    if g == 1 or x == 0:
        print("setwise coprime")
        return
    print("not coprime")
    
    return



if __name__ == '__main__':
    solve()

Solution (Python):
import math as mt
n=int(input())
l=list(map(int,input().split()))
gd=l[0]
sv=[0]*(10**6+1)
for i in range(2,len(sv)):
  if not sv[i]:
    sv[i]=i
    for j in range(2*i,len(sv),i):
      sv[j]=i
an="not coprime"
for i in range(n):
      gd=mt.gcd(gd,l[i])
if gd!=1:
	print(an)
else:
    an="setwise coprime"
    pos=1
    vis=[0]*(10**6+2)
    for i in range(n):
      cr=l[i]
      while cr>1:
          dv=sv[cr]
          if vis[dv]:
            pos=0;break
          while cr%dv==0:
            cr//=dv
          vis[dv]=1
    if pos:
      an="pairwise coprime"
    print(an)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
g = a[0]
for i in range(n):
    g = math.gcd(g, a[i])
if g != 1:
    print('not coprime')
    quit()
p = [0] * (10**6+1)
prime = []
cnt = 0
for i in range(2, 10**6 + 1):
    if p[i] == 0:
        prime.append(i)
        cnt += 1
        for j in range(i, 10**6 + 1, i):
            p[j] += 1

tmp = [0] * (10**6 + 1)
for i in range(n):
    tmp[a[i]] = 1
for i in prime:
    cnt = 0
    for j in range(i, 10**6+1, i):
        if tmp[j]:
            cnt += 1
    if cnt > 1:
        print('setwise coprime')
        quit()
print('pairwise coprime')

Solution (Python):
import math
n = int(input())
lis = list(map(int,input().split()))
lis.sort()
num = lis[0]
for nu in lis:
    num = math.gcd(num,nu)
exist = [0 for i in range(10**6+1)]
if num != 1:
    print("not coprime")
    exit()
for nu in lis:
    if nu != 1:
        for i in range(2,math.ceil(math.sqrt(nu))+1):
            if nu % i == 0:
                if exist[i] == 1:
                    print("setwise coprime")
                    exit()
                else:
                    exist[i] = 1
                    while nu % i == 0:
                        nu //= i
        if nu != 1:
            if exist[nu] == 1:
                print("setwise coprime")
                exit()
            exist[nu] = 1
print("pairwise coprime")

Solution (Python):

max_val = int(1e+6+1)
def make_kago(x):
    kago = [0 for _ in range(x+1)]
    sosuu = []
    for i in range(2,x+1):
        if kago[i] != 0:
            continue
        sosuu.append(i)
        for j in range(i, x+1, i):
            if kago[j] == 0:
                kago[j] = i
    return kago, sosuu

kago, sosuu = make_kago(max_val)

def prime_factorization(x):
    if x==0:
        return None
    soinsuu = []
    while x!=1:
        soinsuu.append(kago[int(x)])
        x = x/kago[int(x)]
    
    soinsuu_dict = dict()
    for i in range(len(soinsuu)):
        if soinsuu[i] not in soinsuu_dict:
            soinsuu_dict[soinsuu[i]] = 1
        else:
            soinsuu_dict[soinsuu[i]]+=1
    return soinsuu_dict

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

exists = [0 for _ in range(int(1e+6+1))]

complete_ok = True
exist_one = False

for i, A in enumerate(As):
    if A == 1:
        continue
    soinsuu_dict = prime_factorization(A)
    keys = list(soinsuu_dict.keys())
    for key in keys:
        if exists[key] != 0:
            complete_ok = False
        exists[key] += 1

part_ok = False
for i in range(len(exists)):
    if exists[i] == len(As):
        part_ok = True

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

Solution (Python):

def Prime_Factorization(N):
    if N<0:
        R=[[-1,1]]
    else:
        R=[]

    N=abs(N)
    k=2
    while k*k<=N:
        if N%k==0:
            C=0
            while N%k==0:
                C+=1
                N//=k
            R.append([k,C])
        k+=1

    if N!=1:
        R.append([N,1])
    if not R:
        R.append([N,1])

    return R

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


P=set()
F=True
for a in A:
    K=Prime_Factorization(a)
    for (p,_) in K:
        if p in P and p!=1:
            F=False
            break
        else:
            P.add(p)

    if not F:
        break

if F:
    print("pairwise coprime")
    exit()


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

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

Solution (Python):

import math

def cal_primes(N):
    candidate = [*range(2, N+1)]
    primes = []

    while candidate[0]**2 <= N:
        primes.append(candidate[0])
        candidate = [*filter(lambda x: x % candidate[0] != 0, candidate)]
    
    primes.extend(candidate)
    return primes

def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N == 2:
        if math.gcd(A[0],A[1]) == 1:
            ans = 0
        else:
            ans = 2
    else:
        A.sort()
        nums = [0] * (10**6+1)
        for a in A:
            nums[a] += 1
        
        plist = cal_primes(10**6//2)

        ans = 0
        for p in plist:
            now = p
            cnt = 0
            while now <= 10**6:
                cnt += nums[now]
                now += p
            if cnt == N:
                ans = 2
                break
            elif cnt > 1:
                ans = 1
    
    if ans == 0:
        print('pairwise coprime')
    elif ans == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == "__main__":
    main()

Solution (Python):
import math
import sys
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
ma = max(a)
pc = True

if ma == 1:
    print("pairwise coprime")
    sys.exit()
    
bb = Counter(a)
    
if len(bb) - 1 == n - bb[1]:
    pc = True
elif len(bb) != n :
    pc = False
    
cu = [0]*(ma+1)
for i in a:
    cu[i] = 1

for i in range(2,ma+1):
    aa = 0
    for j in range(i,ma+1,i):
        aa += cu[j]
    if aa > 1:
        pc = False
        break

gc = a[0]
for i in a[1:]:
    gc = math.gcd(i,gc)
    
if pc:
    print("pairwise coprime")
elif gc == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
from collections import Counter

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

def sieve(n):
    res=list(range(n))

    i=2
    while i*i<n:
        if res[i]<i:
            i+=1
            continue

        for j in range(i*i,n,i):
            if res[j]==j:
                res[j]=i
        i+=1
    
    return res
min_factor=sieve(10**6+1)
def factor(x):
    res=set()
    while x>1:
        res.add(min_factor[x])
        x//=min_factor[x]
    
    return list(res)

lst=[]

for aa in a:
    lst+=factor(aa)

cnt=list(Counter(lst).items())

if len(cnt)==len(lst):
    print('pairwise coprime')
else:
    for k,v in cnt:
        if v==n:
            print('not coprime')
            exit(0)
    
    print('setwise coprime')

Solution (Python):
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

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

    return arr


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

a.sort()

jd=[True]*(a[-1]+10)

pairwise=True

for i in a:
    if i==1:
        continue
    
    xxx=factorization(i)
    for j in xxx:
        if jd[j[0]]==True:
          jd[j[0]]=False
        else:
            pairwise=False
            break
    
    if pairwise==False:
        break

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

if 1 in a:
    print('setwise coprime')
    exit()


zzz=factorization(a[0])

for i in zzz:
    pin=i[0]
    flag=True
    cnt=0
    for j in a:
      if j%pin==0:
          cnt+=1
    
    if cnt==n:
        print('not coprime')
        exit()


print('setwise coprime')

Solution (Python):
def divisor(i):
    s = []
    for j in range(1, int(i ** (1 / 2)) + 1):
        if i % j == 0:
            s.append(i // j)
            s.append(j)
    return sorted(set(s))

import math

n = int(input())
a = list(map(int, input().split()))
ans = ["pairwise coprime", "setwise coprime", "not coprime"]
"""
if n >= 200000:
    g = a[0]
    for i in a:
        g = math.gcd(i, g)
        if g == 1:
            print(ans[1])
            exit()
    print(ans[2])
    exit()
"""
if n <= 1000000:
    x = [0] * 1000005
    for i in a:
        s = divisor(i)
        t = 1
        for j in s:
            if j == 1:
                continue
            if x[j] == 1:
                t = 0
                break
            x[j] = 1
        if t == 0:
            break
    if t == 1:
        print(ans[0])
        exit()
    g = a[0]
    for i in a:
        g = math.gcd(i, g)
        if g == 1:
            print(ans[1])
            exit()
    print(ans[2])
    exit()

Solution (Python):

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
A.sort()

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

def isPrime(n):
	if n <= 1:
		return False
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	i = 3
	while i * i <= n:
		if n % i == 0:
			return False
		i += 2
	return True

P = [n for n in range(10**3 + 1) if isPrime(n)]
used = [False for _ in range(10**6 + 1)]

isPC = True
s = A[0]

n = A[0]
for p in P:
	if p > n:
		break
	while n % p == 0:
		used[p] = True
		n = n // p
if n > 1:
	used[n] = True

for n in A[1:]:
	if isPC:
		a = n
		for p in P:
			if p > a:
				break
			if a % p == 0 and used[p]:
				isPC = False
				break
			while a % p == 0:
				a = a // p
		if a > 1 and used[a]:
			isPC = False
		else:
			used[a] = True

	if s > 1:
		s = gcd(s, n)

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip() 
from functools import reduce
from collections import defaultdict
from math import gcd

n = int(input())
A = list(int(x) for x in input().split())

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

def is_prime_miller_rabin(n):  
    if n < 2:
        return False
    elif n in {2, 3, 5, 7, 11}:
        return True
    elif n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 or n % 11 == 0:
        return False

    if n < 4_759_123_141:
        witnesses = [2, 7, 61]
    elif n < 341_550_071_728_321:
        witnesses = [2, 3, 5, 7, 11, 13, 17]
    else:
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]

    d = n - 1
    d = d // (d & -d)

    for a in witnesses:
        y = pow(a, d, n)
        if y == 1:
            continue
        t = d
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1:
                return False
            t <<= 1
    return True

def find_factor_rho(n):  
    if n < 2:
        return None
    m = 1<<n.bit_length() // 8 + 1
    for c in range(1, 99):
        def f(x):
            return (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 is_prime_miller_rabin(g):
                return g
            elif is_prime_miller_rabin(n // g):
                return n // g
    return None

def prime_factorize_dict(n):
    prime_dict = defaultdict(int)
    i = 2
    while i * i <= n:
        while n % i == 0:
            n //= i
            prime_dict[i] += 1
        i += 1 + i % 2
        if i != 101 or n < 1<<20:
            continue
        while n > 1:
            if is_prime_miller_rabin(n):
                prime_dict[n] = n = 1
                break
            j = find_factor_rho(n)
            while n % j == 0:
                n //= j
                prime_dict[j] += 1
    if n > 1:
        prime_dict[n] += 1
    return prime_dict



pset = set()
for a in A:
    for k in prime_factorize_dict(a).keys():
        if k in pset:
            print("setwise coprime")
            exit()
        pset.add(k)

print("pairwise coprime")

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
from functools import reduce
from math import gcd
g=reduce(lambda x,y:gcd(x,y),A,0)
if g>1:
    print('not coprime')
    exit()
def prime(N):
    p=set(range(2,N+1))
    for i in range(int(N**.5)+1):
        if i in p:
            p-=set(range(i*2,N+1,i))
    return p
p=prime(1000)
r=1
s=set()
for a in A:
    f=0
    for x in p:
        if a%x==0:
            if f==0:
                p2=p.copy()
                f=1
            p2.remove(x)
        while a%x==0:
            a//=x
        if a==1:
            break
    if a>1:
        if 1000<a and a not in s:
            s.add(a)
        else:
            r=0
            break
    if f:
        p=p2
print(['setwise coprime','pairwise coprime'][r])

Solution (Python):
import math

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


def primes(n):
    ans = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ans.append(i)
    return ans


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


c = 0
for a in A:
    if a == 1:
        c += 1
    else:
        break


P = primes(A[-1])
L = len(P)


if (N - c) <= L:
    USED = [False] * (10 ** 6 + 10)
    ok = True
    for a in A:
        if a == 1:
            continue

        f = fctr1(a)
        for x, c in f:
            if not USED[x]:
                USED[x] = True
            else:
                ok = False
                break

    if ok:
        print("pairwise coprime")
        exit()

t = A[0]
for a in A:
    t = math.gcd(a, t)
    if t == 1:
        break

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

Solution (Python):
import sys,math
n=int(input())
a=list(map(int,input().split()))
sieve=[0]*(10**6+1)
numbers={}
flag=0
for i in range(n):
  if a[i] in numbers:
    numbers[a[i]]+=1
  else:
    numbers[a[i]]=1
pointer=2
while pointer<10**6+1:
  if sieve[pointer]==1:
    pointer+=1
    continue
  count=0
  pointer2=pointer
  while pointer2<10**6+1:
    if pointer2 in numbers:
      count+=numbers[pointer2]
    sieve[pointer2]=1
    pointer2+=pointer
  if count>=2:
    flag=1
    break
if flag==0:
  print('pairwise coprime')
  sys.exit()
ans=a[0]
for i in range(1,n):
  ans=math.gcd(a[i],ans)
if ans==1:
  print('setwise coprime')
else:
  print('not coprime')

Solution (Python):
import math

n = input()
As = list(map(int, input().split()))
gcd = As[0]
for a in As[1:]:
    tmp = gcd
    gcd = math.gcd(tmp, a)

if gcd > 1:
    print("not coprime")
    exit()

era = [0] * (10**6 + 1)
for a in As:
    era[a] += 1
for d in range(2, 10**6+1):
    data = [i for i in range(d,10**6+1,d)]
    cnt = 0
    for i in data:
        cnt += era[i] 
    if cnt > 1:
        print("setwise coprime")
        exit()
print("pairwise coprime")

Solution (Python):
import math

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 main():
    N = int(input())
    A = list(map(int, input().split()))
    L = [False]*(max(A)+10)

    for i in range(N):
        divi =  make_divisors(A[i])
        for j in range(len(divi)):
            if L[divi[j]]==False:
                L[divi[j]] = True
            elif divi[j] != 1:
                gc = A[0]
                for k in range(1,N):
                    gc = math.gcd(gc,A[k])
                if gc == 1:
                    print('setwise coprime')
                    return
                else:
                    print('not coprime')
                    return


    print('pairwise coprime')
    return





if __name__ == '__main__':
    main()

Solution (Python):
from math import gcd

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

setgcd = A[0]
for i in range(N):
    setgcd = gcd(setgcd,A[i])
is_set = True
if setgcd != 1:
    is_set=False

M = max(A)
is_prime=[1]*(M+1)
is_inA=[0]*(M+1)
for i in range(N):
    is_inA[A[i]]=1

is_pair = True
is_prime[0]=0
is_prime[1]=0
for i in range(2,M+1):
    count = 0
    if is_inA[i]==1:
        count=1
    if is_prime[i]==1:
        for j in range(2*i,M+1,i):
            is_prime[j]=0
            if is_inA[j]==1:
                count+=1
    if count >= 2:
        is_pair = False

if is_set and is_pair:
    print("pairwise coprime")
elif is_set:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

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

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
used = [False] * len(primes)
big = [0] * (10 ** 6)

g = A[0]
for v in A:
    g = gcd(v,g)
if g == 1:  
    works = 1
    for v in A:
        if v > 1:
            for i in range(len(primes)):
                if v % primes[i] == 0:
                    if used[i]:
                        works = 0
                        break
                    used[i] = True
                    while v % primes[i] == 0:
                        v //= primes[i]
                    if v == 1:
                        break
                    
            works -= big[v]
            big[v] = 1
            big[1] = 0
            
            if works != 1:
                break
    if works:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
n = int(input())
*arr, = map(int, input().split())

def pairwise_coprime(arr):
    mx = max(arr)
    data = [0] * (mx + 1)
    for v in arr:
        data[v] += 1
        if v > 1 and data[v] > 1:
            return False
    primes = [1] * (mx + 1)
    for v in range(2, mx + 1):
        if primes[v]:
            cnt = 0
            if data[v]:
                cnt += 1
            for nonprime in range(2 * v, mx + 1, v):
                primes[nonprime] = 0
                if data[nonprime]:
                    cnt += 1
            if cnt > 1:
                return False
    return True

def gcd(a, b):
    if a > b:
        a, b = b, a

    while a:
        
        b, a = a, b % a
    return b


def setwise_coprime(arr):
    common_gcd = arr[0]
    for i in range(1, len(arr)):
        common_gcd = gcd(common_gcd, arr[i])
    return common_gcd == 1


if pairwise_coprime(arr):
    print("pairwise coprime")
elif setwise_coprime(arr):
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
import math


def simple_sol(N, A):
    is_pairwise_coprime = True
    for i in range(N - 1):
        for j in range(i + 1, N):
            g = math.gcd(A[i], A[j])
            if g == 1:
                continue
            is_pairwise_coprime = False
            break
        if not is_pairwise_coprime:
            break
    if is_pairwise_coprime:
        return 'pairwise coprime'
    g = A[0]
    for i in range(1, N):
        g = math.gcd(g, A[i])
        if g == 1:
            return 'setwise coprime'
    return 'not coprime'



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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    exponents = [0] *  (10 ** 6 + 1)
    is_pairwise_coprime = True
    for a in A:
        for x, e in factorial(a):
            if exponents[x] > 0:
                is_pairwise_coprime = False
                break
            exponents[x] = e
        if not is_pairwise_coprime:
            break
    if is_pairwise_coprime:
        print('pairwise coprime')
        return
    g = A[0]
    for i in range(1, N):
        g = math.gcd(g, A[i])
        if g == 1:
            print('setwise coprime')
            return
    print('not coprime')


if __name__ == '__main__':
    main()

Solution (Python):
P = [1 for _ in range(10**6)]
P[0]=0
P[1]=0
for i in range(2,10**3+1):
    for j in range(i*i,10**6,i):
        P[j]=0
Q = []
for i in range(2,10**6):
    if P[i]==1:
        Q.append(i)
def gcd(x,y):
    while y>0:
        x,y = y,x%y
    return x
N = int(input())
A = list(map(int,input().split()))
a = A[0]
for i in range(1,N):
    a = gcd(a,A[i])
if a>1:
    print("not coprime")
else:
    hist = [0 for _ in range(10**6)]
    flag = 0
    for i in range(N):
        a = A[i]
        if P[a]==1:
            if hist[a]==0:
                hist[a]=1
            else:
                flag=1
                break
        else:
            for q in Q:
                if a%q==0:
                    if hist[q]==0:
                        hist[q]=1
                    else:
                        flag = 1
                        break
                    while a%q==0:
                        a = a//q
                if a==1:break
            if flag==1:break
    if flag==0:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Solution (Python):
from collections import defaultdict
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())
min_cnt = min(primes.values())

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