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

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

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

sys.setrecursionlimit(1000000)

class Eratosthenes:
    
    def __init__(self, n):
        primes, lp = [], [0] * (n + 1)
        for i in range(2, n + 1):
            if lp[i] == 0:
                primes.append(i)
                lp[i] = i

            for pj in primes:
                if pj > lp[i] or i * pj > n: break
                lp[i * pj] = pj
        self.primes, self.lp = primes, lp

    def is_prime(self, x): return self.lp[x] == x

    def factors(self, x):
        ret = []
        while x > 1:
            ret.append(self.lp[x])
            x //= self.lp[x]
        return ret


def main():
    N = I()
    A = LI()

    era = Eratosthenes(1 + 10 ** 6)
    cumgcd = reduce(lambda x,y: math.gcd(x, y), A)
    s = set()
    for ai in A:
        for i in set(era.factors(ai)):
            if i in s:
                break
            s.add(i)
        else:
            continue
        break
    else:
        print("pairwise coprime")
        return

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


if __name__ == '__main__':
    main()

Solution (Python):
from math import gcd

"""
pairwise coprimeであるための条件は、全てのAに関して素因数に重複がないことである。
したがって、各Aに関して素因数分解を行う⇒各数の素因数の種類数をカウントし総和する。⇒全体の素因数の種類数をカウントし、先ほどの総和と比較する。
"""
N = int(input())
A = list(map(int,input().split()))
primes = []
def primeFinder(n):
    memo = [1]*(n+1)
    memo[0] = 0
    memo[1] = 0
    for i in range(2,n+1):
        if memo[i] == 1:
            primes.append(i)
            for j in range(i*2,n+1,i):
                memo[j] = 0
primeFinder(1000000)

primeMemo = set()
cnt = 0
for i in range(N):
    a = A[i]
    for p in primes:
        if p*p > a:
            break
        if a%p == 0:
            cnt += 1
            primeMemo.add(p)
        while a%p==0:
            a //= p
    if a != 1:
        cnt += 1
        primeMemo.add(a)

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

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

N, *A = map(int, open(0).read().split())

def f():
    t = [0] * (10 ** 6 + 1)
    for a in A:
        t[a] += 1

    c = 0
    for j in range(2, 10 ** 6 + 1, 2):
        c += t[j]
    if c > 1:
        return False

    for i in range(3, 10 ** 6 + 1, 2):
        c = 0
        for j in range(i, 10 ** 6 + 1, i):
            c += t[j]
        if c > 1:
            return False

    return True

if f():
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

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

N, *A = map(int, open(0).read().split())

t = [0] * (10 ** 6 + 1)
for a in A:
    t[a] += 1

for i in range(2, 10 ** 6 + 1):
    c = 0
    for j in range(i, 10 ** 6 + 1, i):
        c += t[j]
    if c > 1:
        break
else:
    print('pairwise coprime')
    exit()

if reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):



def soinsu_bunkai(m):
    pf=set()
    mm =m
    pri_num =[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, 1009]
    for i in pri_num:
        if i > mm:
            break
        while mm %i==0:
            pf.add(i)
            mm //=i
    if mm !=1:
        pf.add(mm)
    return pf


import math
import sys
from functools import reduce
input = sys.stdin.readline  
N = int(input())
A = list(map(int, input().split()))
used =set()
pair_w =set()


pri =10**6 +10


gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"


else:
    ans ="pairwise coprime"
    for a in A:
        aa =soinsu_bunkai(a)
        if used & aa:
            print("setwise coprime")
            sys.exit() 
        used |=aa

        
print(ans)

Solution (Python):

def osa_k(a):
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
    return tmp

    
import math
import sys
from bisect import bisect_left
from functools import reduce
input = sys.stdin.readline  
N = int(input())
A = list(map(int, input().split()))
used =set()


gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"


else:
    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
    
    ans ="pairwise coprime"
    for a in A:
        aa =osa_k(a)
        if used & aa:
            ans ="setwise coprime"
            break 
        used |=aa
    
print(ans)

Solution (Python):

def osa_k(a):
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
    return tmp

    
import math
import sys
from bisect import bisect_left
from functools import reduce
input = sys.stdin.readline  
N = int(input())
A = list(map(int, input().split()))
used =set()


gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"


else:
    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
    
    ans ="pairwise coprime"
    for a in A:
        aa =osa_k(a)
        if used & aa:
            ans ="setwise coprime"
            break 
        used |=aa
    
print(ans)

Solution (Python):
import math

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


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


def is_pairwise():
    cs = [0] * 1000010
    for i in a:
        for p, _ in factorization(i):
            if p != 1 and cs[p] == 1:
                return False
            cs[p] = 1
    return True


def is_setwise():
    c = a[0]
    for i in a:
        c = math.gcd(c, i)
    return c == 1


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

Solution (Python):

import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache
import copy

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7




def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])




class osa_k():
    def __init__(self, n):
        """高速素因数分解

        Args:
            n (int): n以下全ての値について素因数分解できるようにする
        """
        self.n = n
        self.minFactor = list(range(0, n + 1))
        self.prime = []

    def factorize(self, i):
        if not self.prime:
            self.get_sieve_of_eratosthenes()
        factor = []
        while i != 1:
            p = self.minFactor[i]
            factor.append(p)
            i //= p
        return factor

    def get_sieve_of_eratosthenes(self):
        """エラトステネスの篩
        """
        limit = math.sqrt(self.n)
        for prime in range(2, self.n + 1):
            if prime >= limit:
                break
            if self.minFactor[prime] == prime:
                self.prime.append(prime)
                for composite in range(2 * prime, self.n + 1, prime):
                    if self.minFactor[composite] == composite:
                        self.minFactor[composite] = prime


n = inp()
a = inpl()
factorizer = osa_k(10**6)
tmp = collections.defaultdict(int)
for i in a:
    p = set(factorizer.factorize(i))
    for j in p:
        tmp[j] += 1
if not tmp.values():
    print("pairwise coprime")
    exit()
max_val = max(tmp.values())
if max_val == 1:
    print("pairwise coprime")
elif max_val == n:
    print("not coprime")
else:
    print("setwise coprime")

Solution (Python):
from math import gcd
from functools import reduce
 
 
def facs(n):
    yield 2
    for x in range(3, n, 2):
        yield x
 
 
def main():
    input()  
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 1
    histogram = [0] * MAX_A
    for x in array:
        histogram[int(x)] += 1
 
    for divider in facs(MAX_A):
        count = sum(histogram[divider::divider])
        if count > 1:
            break
    else:
        return 'pairwise coprime'
 
    gcd_total = reduce(gcd, array)
    if gcd_total == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'
 
 
if __name__ == '__main__':
    print(main())

Solution (Python):
import math
from functools import reduce


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


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


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

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

primes = set()
for a in A:
    len_primes = len(primes)
    divs = set(prime_factorize(a))
    primes |= divs

    if len(primes) != len_primes + len(divs):
        print('setwise coprime')
        exit()

print('pairwise coprime')

Solution (Python):

import math
import functools


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

    

Fnum_list2 = []

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



A.sort()
Amax = A[-1]
Fnum_list2 = primes(Amax)
j = A[0]
ans = 1

Ai_primes     = set()
Ai_primes_add = []
gcd_num = 0
for i in range(len(A) ):
    p = A[i]
    while p != 1:
        j = p
        p = int (p / Fnum_list2[j])
        if Fnum_list2[j] in Ai_primes:
            ans = 0
        else:
            Ai_primes_add.append(Fnum_list2[j])
    if Fnum_list2[j] in Ai_primes:
        break
    else:
        Ai_primes |= set(Ai_primes_add)
        Ai_primes_add.clear()

gcd_num = functools.reduce(math.gcd,A)

if ans == 0:
    if gcd_num == 1:
        ans = 2


if ans == 1:
    print("pairwise coprime")
else:
    if ans == 2:
        print("setwise coprime")
    else:
        print("not coprime")

Solution (Python):
import sys
from collections import defaultdict as dd
from collections import deque
from functools import *
from fractions import Fraction as f
from copy import *
from bisect import *	
from heapq import *
from math import *
from itertools import permutations ,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 

if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def inc(d,c):
	d[c]=d[c]+1 if c in d else 1
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<n	
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)


t=1
N=10**6+5
spf=[i for i in range(N+1)]
for i in range(2,int(ceil(sqrt(N)))+2):
	if spf[i]==i:
		for j in range(i*i,N,i):
			if spf[j]==j:
				spf[j]=i
			
def fact(i):
	s=set()
	while i!=1:
		s.add(spf[i])	
		i//=spf[i]
	return s	

while t>0:
	t-=1
	n=fi()
	a=li()
	s=set()
	g=a[0]
	flag=0
	for i in range(n):
		g=gcd(g,a[i])
		k=fact(a[i])
		if len(s&k)!=0:
			flag|=1
		s|=k
	if flag==0:
		print("pairwise coprime")
	elif g==1:
		print("setwise coprime")	
	else:
		print("not coprime")

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
maxA=max(A)
count=[0]*(maxA+1)
for x in A:
    count[x]+=1
maxc=0
for i in range(2,maxA+1):
    maxc = max(maxc,sum(count[i::i]))

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

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

def generate_D(maxA):
  seq = [i for i in range(maxA+1)]
  p = 2
  while p*p <= maxA:
    if seq[p]==p:
      for q in range(p*2,maxA+1,p):
        if seq[q]==q:
          seq[q] = p
    p += 1
  return seq

cur = a[0]
for v in a[1:]:
  cur = math.gcd(cur,v)
if cur > 1:
  print('not coprime')
else:  
  d = generate_D(max(a))
  primes = set([])
  tf = 1
  for v in a:
    tmp = set([])
    while v > 1:
      tmp.add(d[v])
      v //= d[v]
    for k in tmp:
      if k in primes:
        tf = 0
      else:
        primes.add(k)
  if tf:
    print('pairwise coprime')
  else:
    print('setwise coprime')

Solution (Python):
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop



n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N = n1()
A = nn()


MAX = max(A)
dp = defaultdict(list)

p = 2
while p <= MAX:
    i = p
    while i <= MAX:
        dp[i].append(p)
        i += p

    p += 1
    while len(dp[p]) >= 1:
        p += 1

if max(A) == 1:
    print("pairwise coprime")
    exit(0)

dic = defaultdict(list)

for ai in A:
    fact = dp[ai]
    for x in fact:
        dic[x].append(ai)

maxlen = 0
for k, v in dic.items():
    maxlen = max(len(v), maxlen)

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

Solution (Python):
def eratosthenes(N):
    is_prime = {i: True for i in range(2, N+1)}
    primes = []
    for i in range(2, N+1):
        if is_prime[i]:
            primes.append(i)
            if i**2 <= N:
                for j in range(i**2, N+1, i):
                    is_prime[j] = False
    return primes


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    allgcd = A[0]
    primes = eratosthenes(1000)
    divs = set()
    pairwise_coprime = True
    for a in A:
        if allgcd > 1:
            allgcd = gcd(allgcd, a)
        if not pairwise_coprime:
            continue
        for p in primes:
            if a % p == 0:
                if p in divs:
                    pairwise_coprime = False
                while a % p == 0:
                    a //= p
                divs.add(p)
            if a == 1:
                break
        if a != 1:
            if a in divs:
                pairwise_coprime = False
            divs.add(a)
    if pairwise_coprime:
        print("pairwise coprime")
    else:
        if allgcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")


if __name__ == "__main__":
    main()

Solution (Python):
from math import gcd
class Factor:
    def __init__(self, max_element):
        self.minFactor = [-1]*(max_element+1)
        for i in range(2, max_element+1):
            if self.minFactor[i] == -1:
                for j in range(i, max_element+1, i):
                    self.minFactor[j] = i
    def getFactorSet(self, element):
        retSet = set(1)
        while element > 1:
            retSet.add(element)
            retSet.add(self.minFactor[element])
            element //= self.minFactor[element]
        return retSet
    def getPrimeFactorSet(self, element):
        retSet = set()
        while element > 1:
            retSet.add(self.minFactor[element])
            element //= self.minFactor[element]
        return retSet
    def getPrimeFactorDic(self, element):
        retDic = {}
        while element > 1:
            val = self.minFactor[element]
            if val in retDic:
                retDic[val] += 1
            else:
                retDic[val] = 1
            element //= val
        return retDic

def main():
    n = int(input())
    a = list(map(int, input().split()))
    f = True
    fact = Factor(max(a))
    st = set()
    for v in a:
        fac_set = fact.getPrimeFactorSet(v)
        for u in fac_set:
            if u in st:
                f = False
                break
            st.add(u)
        if not f:
            break
    if f:
        print("pairwise coprime")
    else:
        all_gcd = a[0]
        for i in range(1, n):
            all_gcd = gcd(all_gcd, a[i])
        if all_gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")

if __name__ == "__main__":
    main()

Solution (Python):
from math import gcd
class Factor:
    def __init__(self, max_element):
        self.minFactor = [-1]*(max_element+1)
        for i in range(2, max_element+1):
            if self.minFactor[i] == -1:
                for j in range(i, max_element+1, i):
                    self.minFactor[j] = i
    def getFactorSet(self, element):
        retSet = set(1)
        while element > 1:
            retSet.add(element)
            retSet.add(self.minFactor[element])
            element //= self.minFactor[element]
        return retSet
    def getPrimeFactorSet(self, element):
        retSet = set()
        while element > 1:
            retSet.add(self.minFactor[element])
            element //= self.minFactor[element]
        return retSet
    def getPrimeFactorDic(self, element):
        retDic = {}
        while element > 1:
            val = self.minFactor[element]
            if val in retDic:
                retDic[val] += 1
            else:
                retDic[val] = 1
            element //= val
        return retDic

def main():
    n = int(input())
    a = list(map(int, input().split()))
    f = True
    fact = Factor(max(a))
    st = set()
    for v in a:
        fac_set = fact.getPrimeFactorSet(v)
        for u in fac_set:
            if u in st:
                f = False
                break
            st.add(u)
        if not f:
            break
    if f:
        print("pairwise coprime")
    else:
        all_gcd = a[0]
        for i in range(1, n):
            all_gcd = gcd(all_gcd, a[i])
        if all_gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")

if __name__ == "__main__":
    main()

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = LIST()

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

k = max(sum(c[i::i]) for i in range(2, 10**6+1))

if k <= 1:
    print("pairwise coprime")
elif k < n:
    print("setwise coprime")
else:
    print("not coprime")

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

def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor: GCD)を求める
    計算量: O(log(min(a, b)))
    """
    while b:
        a, b = b, a % b
    return a


def multi_gcd(array: list) -> int:
    """arrayのGCDを求める"""
    n = len(array)
    ans = array[0]
    for i in range(1, n):
        ans = gcd(ans, array[i])
    return ans


def make_mindiv_table(n):
    mindiv = [i for i in range(n + 1)]
    for i in range(2, int(n ** 0.5) + 1):
        if mindiv[i] != i:
            continue
        for j in range(2 * i, n + 1, i):
            mindiv[j] = min(mindiv[j], i)
    return mindiv


def get_prime_factors(num):
    res = []
    while mindiv[num] != 1:
        res.append(mindiv[num])
        num //= mindiv[num]
    return res


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


mindiv = make_mindiv_table(10 ** 6)

set_primes = set()
flag = True
for val in a:
    set_ = set(get_prime_factors(val))
    for v in set_:
        if v in set_primes:
            flag = False
        set_primes.add(v)
    if not flag:
        break
else:
    print("pairwise coprime")
    exit()

gcd_ = multi_gcd(a)
if gcd_ == 1:
    print("setwise coprime")
    exit()

print("not coprime")

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = LIST()
m = max(a)

primes = [0]*(m+1)
primes[1] = 1
for i in range(2, m+1):
    if primes[i] == 0:
        for j in range(1, m//i+1):
            primes[i*j] = i

count = [0]*(m+1)
for x in a:
    y = x
    while primes[y] != y:
        count[primes[y]] += 1
        p = primes[y]
        while y % p == 0:
            y //= p
    if primes[y] >= 2:
        count[primes[y]] += 1

if max(count) <= 1:
    print("pairwise coprime")
else:
    g = 0
    for x in a:
        g = gcd(g, x)
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Solution (Python):
from math import gcd
flag=0
N=int(input())
A=list(map(int,input().split()))
Max=max(A)
a=[0]*(Max+1)
for i in A:
    a[i]+=1
for i in range(2,Max+1):
    if sum(a[i::i])>=2:
        flag=1
        break
if flag==0:
    print('pairwise coprime')
else:
    r=A[0]
    for i in A:
        r=gcd(r,i)
    if r==1:
        print('setwise coprime')
    else:
        print("not coprime")

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [0] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i] == 0:
            p.append(i)
            t[i] = i
            for j in range(2*i, n, i):
                if t[j] == 0:
                    t[j] = i

    for j in range(i+1, n):
        if t[j] == j or t[j] == 0:
            p.append(j)
            t[j] = j

    return p, t


@mt
def slv(N, A):
    _, T = eratosthenes(10**6+1)

    used = set()
    for a in A:
        while a != 1:
            p = T[a]
            if p in used:
                break
            while a % p == 0:
                a //= p
            used.add(p)
        if a != 1:
            break

    else:
        return 'pairwise coprime'

    return 'setwise coprime' if reduce(math.gcd, A) == 1 else 'not coprime'


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [0] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i] == 0:
            p.append(i)
            t[i] = i
            for j in range(2*i, n, i):
                if t[j] == 0:
                    t[j] = i

    for j in range(i+1, n):
        if t[j] == j or t[j] == 0:
            p.append(j)
            t[j] = j

    return p, t


@mt
def slv(N, A):
    _, T = eratosthenes(10**6+1)

    used = set()
    for a in A:
        while a != 1:
            p = T[a]
            if p in used:
                break
            while a % p == 0:
                a //= p
            used.add(p)
        if a != 1:
            break

    else:
        return 'pairwise coprime'

    g = 0
    for a in A:
        g = math.gcd(a, g)
    return 'setwise coprime' if g == 1 else 'not coprime'


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()