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

Solution (Python):

import sys

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


import math

def get_primenumber(number):
    prime_list = []
    search_list = list(range(2,number+1))
    
    while search_list[0] <= math.sqrt(number):
      
      
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        
        search_list = [num for num in search_list if num % head_num != 0]
    
    prime_list.extend(search_list)
    return prime_list



n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

p=get_primenumber(amax)

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1
    

for pp in p:
    psum=0
    for pi in range(pp,amax+1,pp):
        psum+=aa[pi]


    if psum>=2:
            print("setwise coprime")
            sys.exit()

print("pairwise coprime")

Solution (Python):

import sys

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


import math

def get_primenumber(number):
    prime_list = []
    search_list = list(range(2,number+1))
    
    while search_list[0] <= math.sqrt(number):
      
      
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        
        search_list = [num for num in search_list if num % head_num != 0]
    
    prime_list.extend(search_list)
    return prime_list



n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

p=get_primenumber(amax)

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1
    
for pp in range(2,amax+1):

    psum=0
    for pi in range(pp,amax+1,pp):
        psum+=aa[pi]


    if psum>=2:
            print("setwise coprime")
            sys.exit()

print("pairwise coprime")

Solution (Python):

import sys

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


import math

def get_primenumber(number):
    prime_list = []
    search_list = list(range(2,number+1))
    
    while search_list[0] <= math.sqrt(number):
      
      
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        
        search_list = [num for num in search_list if num % head_num != 0]
    
    prime_list.extend(search_list)
    return prime_list

p=get_primenumber(79000)

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1
    
for pp in range(2,amax+1):

    psum=0
    for pi in range(pp,amax+1,pp):

        psum+=aa[pi]


    if psum>=2:
            print("setwise coprime")
            sys.exit()

print("pairwise coprime")

Solution (Python):

import sys

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


import math

def get_primenumber(number):
    prime_list = []
    search_list = list(range(2,number+1))
    
    while search_list[0] <= math.sqrt(number):
      
      
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        
        search_list = [num for num in search_list if num % head_num != 0]
    
    prime_list.extend(search_list)
    return prime_list

p=get_primenumber(79000)

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1
    
for pp in range(2,amax+1):

    psum=0



    psum=sum(aa[pp: :pp])

    if psum>=2:
            print("setwise coprime")
            sys.exit()

print("pairwise coprime")

Solution (Python):








import math,sys

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))


g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            
            for j in range(i+i,LIMIT+1,i):
                
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])
pc = True

for i in a:
    if not pc:
        break
    asf = set(factrial(i))

    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):








import math,sys

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))


g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            
            for j in range(i+i,LIMIT+1,i):
                
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])
pc = True

for i in a:
    if not pc:
        break
    asf = set(factrial(i))

    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):








import math

pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            
            for j in range(i+i,LIMIT+1,i):
                
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret










judge = set([])

for i in a:
    if not pc:
        break
    
    asf = set(factrial(i))

    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):








import math
from collections import defaultdict
pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            
            for j in range(i+i,LIMIT+1,i):
                
                if minPrime[j] == 0:
                    minPrime[j] = i
make()























def factrial(N):
    ret = set()
    while 1 != N:
        ret.add(minPrime[N])
        N = N//minPrime[N]
    if N != 1:
        ret.add(N)
    return ret


ddic = defaultdict()
judge = set([])

for i in a:
    if not pc:
        break
    
    asf = factrial(i)

    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):








import math
from collections import defaultdict
pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            
            for j in range(i+i,LIMIT+1,i):
                
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
class Sieve_of_Eratosthenes:
    def __init__(self, N):
        self.sieve = [-1] * (N+1)

        for i in range(2,N+1):
            if self.sieve[i] == -1:
                for j in range(1,1+N//i):
                    self.sieve[i*j] = i

    def isprime(self, num):
        if num <= 1:
            return False
        else:
            return self.sieve[num] == num

    def factorization(self, num):
        ret = set([])
        while num != 1:
            div = self.sieve[num]
            ret.add(div)
            num //= div
        return ret

def factrial(N):
    ret = set()
    while 1 != N:
        ret.add(minPrime[N])
        N = N//minPrime[N]
    if N != 1:
        ret.add(N)
    return ret


sofe = Sieve_of_Eratosthenes(M)
ddic = defaultdict()
judge = set([])

for i in a:
    if not pc:
        break
    
    asf = factrial(i)

    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):








import math
from collections import defaultdict
pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            
            for j in range(i+i,LIMIT+1,i):
                
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
class Sieve_of_Eratosthenes:
    def __init__(self, N):
        self.sieve = [-1] * (N+1)

        for i in range(2,N+1):
            if self.sieve[i] == -1:
                for j in range(1,1+N//i):
                    self.sieve[i*j] = i

    def isprime(self, num):
        if num <= 1:
            return False
        else:
            return self.sieve[num] == num

    def factorization(self, num):
        ret = set([])
        while num != 1:
            div = self.sieve[num]
            ret.add(div)
            num //= div
        return ret

    def factrial(self,N):
        ret = set()
        while 1 != N:
            ret.add(minPrime[N])
            N = N//minPrime[N]
        if N != 1:
            ret.add(N)
        return ret


sofe = Sieve_of_Eratosthenes(M)
ddic = defaultdict()
judge = set([])

for i in a:
    if not pc:
        break
    
    asf = sofe.factrial(i)

    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):








import math
from collections import defaultdict
pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            
            for j in range(i+i,LIMIT+1,i):
                
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
class Sieve_of_Eratosthenes:
    def __init__(self, N):
        self.sieve = [-1] * (N+1)

        for i in range(2,N+1):
            if self.sieve[i] == -1:
                for j in range(1,1+N//i):
                    self.sieve[i*j] = i

    def isprime(self, num):
        if num <= 1:
            return False
        else:
            return self.sieve[num] == num

    def factorization(self, num):
        ret = set([])
        while num != 1:
            div = self.sieve[num]
            ret.add(div)
            num //= div
        return ret

sofe = Sieve_of_Eratosthenes(M)
ddic = defaultdict()
judge = set([])

for i in a:
    if not pc:
        break
    asf = sofe.factorization(i)

    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
import math
from collections import defaultdict
pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
class Sieve_of_Eratosthenes:
    def __init__(self, N):
        self.sieve = [-1] * (N+1)
 
        for i in range(2,N+1):
            if self.sieve[i] == -1:
                for j in range(1,1+N//i):
                    self.sieve[i*j] = i
 
    def isprime(self, num):
        if num <= 1:
            return False
        else:
            return self.sieve[num] == num
 
    def factorization(self, num):
        ret = set([])
        while num != 1:
            div = self.sieve[num]
            ret.add(div)
            num //= div
        return ret
 
sofe = Sieve_of_Eratosthenes(M)
ddic = defaultdict()
judge = set([])
 
for i in a:
    if not pc:
        break
    asf = sofe.factorization(i)
    
    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):

import math

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

is_prime = [True for _ in range(1100000)]
is_prime[0] = is_prime[1] = False

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

g = 0 
for a in A:
    g = math.gcd(g, a)

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

used = [False for _ in range(1100000)]
primes = [a for a in A if is_prime[a]]
not_primes = [a for a in A if not is_prime[a]]

for p in primes:
    used[p] = True

small_prime = [p for p in range(1100) if is_prime[p]]
for a in not_primes:
    for p in small_prime:
        if a == 1: break
        if a%p != 0: continue
        if used[p]:
            print('setwise coprime')
            exit()
        used[p] = True
        while a%p == 0:
            a //= p
    if a > 1:
        if used[a]:
            print('setwise coprime')
            exit()
        used[a] = True

print('pairwise coprime')

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
temp=[0]*(10**6+1)
for i in a:
    temp[i]+=1
if temp[1]==n:
    print("pairwise coprime")
    exit()
ans=[]
for i in range(2,10**6+1):
    count=0
    j=1
    while True:
        count+=temp[i*j]
        j+=1
        if i*j>=10**6:
            break
    ans.append(count)
if max(ans)==1:
    print("pairwise coprime")
elif max(ans)==n:
    print("not coprime")
else:
    print("setwise coprime")

Solution (Python):
import math
import sys
input = sys.stdin.readline
pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
class Sieve_of_Eratosthenes:
    def __init__(self, N):
        self.sieve = [-1] * (N+1)

        for i in range(2,N+1):
            if self.sieve[i] == -1:
                for j in range(1,1+N//i):
                    self.sieve[i*j] = i

    def isprime(self, num):
        if num <= 1:
            return False
        else:
            return self.sieve[num] == num

    def factorization(self, num):
        ret = set([])
        while num != 1:
            div = self.sieve[num]
            ret.add(div)
            num //= div
        return ret

sofe = Sieve_of_Eratosthenes(M)

judge = set([])

for i in a:
    if not pc:
        break
    asf = sofe.factorization(i)
    
    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

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

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

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

pairwise = True
for i in range(2, 10**6+1):
    cnt = sum(num[i::i])
    if cnt == n:
        print('not coprime')
        exit()
    if cnt > 1:
        pairwise = False

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

Solution (Python):
import math
from collections import defaultdict
import sys
input = sys.stdin.readline
pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
class Sieve_of_Eratosthenes:
    def __init__(self, N):
        self.sieve = [-1] * (N+1)

        for i in range(2,N+1):
            if self.sieve[i] == -1:
                for j in range(1,1+N//i):
                    self.sieve[i*j] = i

    def isprime(self, num):
        if num <= 1:
            return False
        else:
            return self.sieve[num] == num

    def factorization(self, num):
        ret = set([])
        while num != 1:
            div = self.sieve[num]
            ret.add(div)
            num //= div
        return ret

sofe = Sieve_of_Eratosthenes(M)
ddic = defaultdict()
judge = set([])

for i in a:
    if not pc:
        break
    asf = sofe.factorization(i)
    
    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
from math import gcd
n = int(input())
s = list(map(int, input().split()))
s.sort()
dp = [0] * ((10 ** 6) + 100)

for ss in s:
    dp[ss] += 1

A = max(s)
pairwise = True

for i in range(2, A + 1):
    cnt = 0
    for j in range(i, A + 1, i):
        cnt += dp[j]
    if cnt > 1:
        pairwise = False

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

res = s[0]
for ss in s:
    res = gcd(res, ss)
print("setwise coprime" if res == 1 else "not coprime")

Solution (Python):
import math
from collections import defaultdict
pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
class Sieve_of_Eratosthenes:
    def __init__(self, N):
        self.sieve = [-1] * (N+1)

        for i in range(2,N+1):
            if self.sieve[i] == -1:
                for j in range(1,1+N//i):
                    self.sieve[i*j] = i

    def isprime(self, num):
        if num <= 1:
            return False
        else:
            return self.sieve[num] == num

    def factorization(self, num):
        ret = set([])
        while num != 1:
            div = self.sieve[num]
            ret.add(div)
            num //= div
        return ret

sofe = Sieve_of_Eratosthenes(M)
ddic = defaultdict()
judge = set([])

for i in a:
    if not pc:
        break
    asf = sofe.factorization(i)
    
    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

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

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

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

pairwise = True
for i in range(2, 10**6+1):
    cnt = sum(num[i::i])
    if cnt == n:
        print('not coprime')
        exit()
    if cnt > 1:
        pairwise = False

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

Solution (Python):
from functools import reduce
from math import gcd
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    M = max(A)

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

    
    sieve = list(range(M + 1))
    primes = []
    for i in range(2, M + 1):
        if sieve[i] == i:
            primes.append(i)
        for p in primes:
            if sieve[i] < p or i * p > M:
                break
            sieve[i * p] = 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()

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

ga = a[0]
for i in range(n):
  ga = math.gcd(ga, a[i])

if ga != 1:
  print("not coprime")
  sys.exit()

m = 1000000
b = [0]*(m+1)

for i in range(2, m):
  if b[i] != 0:
    continue
  j = 1
  while True:
    t = i * j
    if t > m:
      break
    if b[t] == 0:
      b[t] = i
    j += 1
d = {}
for i in a:
  p = i
  
  while p != 1:
    if p in d:
      print("setwise coprime")
      sys.exit()
    d[p] = 1
    p = int(p/b[p])

print("pairwise coprime")

Solution (Python):
import math

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

inf = int(1e6+5)
C = [0]*inf

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

pa = True
se = True
for i in range(2, inf):
    cnt = 0
    cnt += sum(C[i::i])
    if cnt > 1:
        pa = False
    if cnt == N:
        se = False
        
if pa:
    print("pairwise coprime")
elif se:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
import math

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

inf = int(1e6+5)
C = [0]*inf

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

pa = True
se = True
for i in range(2, inf):
    cnt = 0
    for j in range(i, inf, i):
        cnt += C[j]
    if cnt > 1:
        pa = False
    if cnt == N:
        se = False
        
if pa:
    print("pairwise coprime")
elif se:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
import math

N = int(input())
A = list(map(int,input().split()))
MAX_INT = 10**6
f1 = [0] * (MAX_INT+1)
for a in A:
  f1[a] += 1

flg = True
for i in range(2, MAX_INT+1):
  cnt = 0
  for j in range(i, MAX_INT+1, i):
    cnt += f1[j]
  if cnt > 1:
    flg = False
    break

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

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

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

Solution (Python):
import math
import functools
import sys

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

wise = functools.reduce(math.gcd, A)
if wise != 1:
    print('not coprime')
    sys.exit(0)

A = list(filter(lambda a: a != 1, A))

if len(A) == 0:
    print('pairwise coprime')
    sys.exit(0)

pcount = 78498
if len(A) > pcount:
    print('setwise coprime')
    sys.exit(0)

Amax = max(A) + 1

hurui = [1] * 1001
primes = []

for n in range(2, 1001):
    if hurui[n] != 1:
        continue

    primes.append(n)

    k = 2
    while n * k <= 1000:
        hurui[n * k] = n
        k += 1




count = [0] * (Amax+1)

pairwise = True
for i in range(len(A)):
    a = A[i]
    if a == 1:
        continue

    for p in primes:
        if a % p == 0:
            count[p] += 1
            while a % p == 0:
                a = a // p
    if a != 1:
        count[a] += 1

if max(count)==1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
c = [0]*(10**6 + 1)

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

cnt = 0

for i in range(2, 10**6 + 1):
    s = sum(c[i::i])
    if s == n:
        print("not coprime")
        exit()
    elif s > 1:
        cnt += 1

if cnt > 0:
    print("setwise coprime")
else:
    print("pairwise coprime")

Solution (Python):
from math import gcd

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

v = 0
for a in A: v = gcd(a, v)
if v > 1:
	print('not coprime')
	raise SystemExit


V = set()
for v in A:
	for i in range(2, v+1):
		if i * i > v: break
		if v % i == 0:
			if v in V:
				print('setwise coprime')
				raise SystemExit

			V.add(v)
			while v % i == 0: v //= i
	if v != 1:
		if v in V:
			print('setwise coprime')
			raise SystemExit

		V.add(v)

print('pairwise coprime')

Solution (Python):
import numpy as np
n = int(input())
a = list(map(int, input().split()))
g = np.gcd.reduce(a)

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

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

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

for i in range(2, 10**6 + 1):
    if sum(c[i::i]) > 1:
        print("setwise coprime")
        exit()

print("pairwise coprime")

Solution (Python):
from sys import exit
from math import gcd

def eratosthenes(n):
    '''
    n以下の整数の素数判定/列挙 (n > 1)
    O(NloglogN)
    '''
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    min_factor = [-1] * (n+1)
    min_factor[0] = 0
    min_factor[1] = 1
    
    for i in range(2, n+1):
        if is_prime[i]:
            min_factor[i] = i
            for j in range(i*2, n+1, i):
                is_prime[j] = False
                if min_factor[j] == -1:
                    min_factor[j] = i

    return min_factor


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

l = eratosthenes(10**6+1)

flag = True
used = [False] * (10**6+1)
for v in a:
    s = set()
    while v > 1:
        if l[v] not in s:
            if used[l[v]]:
                flag = False
                break
            else:
                s.add(l[v])
                used[l[v]] = True
        
        v //= l[v]

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

g = 0
for v in a:
    g = gcd(g, v)

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

Solution (Python):
import math

INF=float('inf')
ans1='pairwise coprime'
ans2='setwise coprime'
ans3='not coprime'

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

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

pairwise=True
for i in range(2,10**6+1):
  cnt=0
  for j in range(i,10**6+1,i):
    cnt+=P[j]
  if cnt>1:
    pairwise=False
    break

if pairwise:
  print(ans1)
  exit()
  
g=math.gcd(A[0],A[1])
for i in A:
  g=math.gcd(g,i)

if g==1:
  print(ans2)
else:
  print(ans3)

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

ga = a[0]
for i in range(n):
  ga = math.gcd(ga, a[i])

if ga != 1:
  print("not coprime")
  sys.exit()

m = 1000000
b = [0]*(m+1)

for i in range(2, m):
  if b[i] != 0:
    continue
  j = 1
  while True:
    t = i * j
    if t > m:
      break
    if b[t] == 0:
      b[t] = i
    j += 1

d = {}
for i in a:
  p = i
  while p != 1:
    if p in d:
      print("setwise coprime")
      sys.exit()
    d[p] = 1
    p = int(p/b[p])
print("pairwise coprime")

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5) + 1
        cnt_list = [0] * (n + 1)
        for i in range(2, limit + 1):
            if cnt_list[i] == 0:
                k = n // i
                for j in range(1, k + 1):
                    s = i * j
                    if cnt_list[s] == 0:
                        D[s] = i
                        cnt_list[s] = 1
        for l in range(limit, n + 1):
            if cnt_list[l] == 0:
                D[l] = l
                cnt_list[l] = 1
        return D



    N = I()
    A = LI()
    D = defaultdict()
    max_a = max(A)
    num_list = [0] * (max_a + 1)
    if max_a == 1:
        print("pairwise coprime")
        exit()

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print('not coprime')
        exit()

    A_ = set(A)
    A_.discard(1)
    if len(A_) >= 90000:
        print('setwise coprime')
        exit()

    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        P_list = defaultdict(int)
        while a != 1:
            x = D[a]
            P_list[x] += 1
            a //= x
        for key in P_list.keys():
            if num_list[key] != 0:
                print('setwise coprime')
                exit()
            num_list[key] = 1

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Solution (Python):
from sys import exit
from math import gcd

def eratosthenes(n):
    '''
    n以下の整数の素数判定/列挙 (n > 1)
    O(NloglogN)
    '''
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    judge = [i for i in range(n+1)]
    
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
                judge[j] = i

    return judge


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

l = eratosthenes(10**6+1)

flag = True
used = [False] * (10**6+1)
for v in a:
    while v > 1:
        d = l[v]

        if used[d]:
            flag = False
        else:
            used[d] = True
        
        while v % d == 0:
            v //= d

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

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

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