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 
from math import gcd
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int, readline().split()))
M = max(A) + 1

minfactor = [0] * M
minfactor[1] = 1
commondivisor = [0] * M

def seive():
    for i in range(2,M):
        if minfactor[i] == 0:
            for j in range(i*2,M,i):
                if minfactor[j] == 0:
                    minfactor[j] = i
    for i in range(2,M):
        if minfactor[i] == 0:
            minfactor[i] = i  

gc = A[0]
for i in range(1,N):
    gc = gcd(A[i],gc)
    
if gc != 1:
    print('not coprime')
else:
    seive()
    for i in range(N):
        a = A[i]
        while a > 1:
            div = minfactor[a]
            commondivisor[div] += 1
            while a % div == 0:
                a //= div
    if max(commondivisor) <= 1:
        print('pairwise coprime')
    else:
        print('setwise coprime')

Solution (Python):
import sys,random
from math import gcd
input=sys.stdin.readline
n=int(input())
*a,=map(int, input().split())
random.shuffle(a)
tmp=a[0]
for i in range(1,n):
    tmp=gcd(tmp,a[i])
if tmp>1:
    print('not coprime')
    exit()



def f(x):
    res=set()
    for i in range(2,int(x**(1/2))+3):
        if x%i==0:
            while x%i==0:
                x//=i
            res.add(i)
    return res,x
tmp=set()
tmp2=set()
for ai in a:
    for p in tmp:
        if ai%p==0:
            print('setwise coprime')
            exit()
    pp,x=f(ai)
    tmp|=pp 
    if x>1 and x in tmp2:
        print('setwise coprime')
        exit()
    tmp2.add(x)
    
        
print('pairwise coprime')

Solution (Python):
import sys,math
n=int(input())
a=list(map(int,input().split()))
numbers={}
flag=0
for i in range(n):
  if a[i] in numbers:
    numbers[a[i]]+=1
  else:
    numbers[a[i]]=1
for pointer in range(2,10**6+1):
  count=0
  pointer2=pointer
  while pointer2<10**6+1:
    if pointer2 in numbers:
      count+=numbers[pointer2]
    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 = int(input())
A = list(map(int, input().split()))
C = [0] * (10 ** 6 + 1)

for i in range(N):
    C[A[i]] += 1

is_pairwise = True
max_a = max(A) + 1
X = [0] * max_a
for i in range(2, max_a):
    count = 0
    for j in range(i, max_a, i):
        count += C[j]
    if count > 1:
        is_pairwise = False

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

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

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

Solution (Python):
import sys,math
n=int(input())
a=list(map(int,input().split()))
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:
  count=0
  pointer2=pointer
  while pointer2<10**6+1:
    if pointer2 in numbers:
      count+=numbers[pointer2]
    pointer2+=pointer
  if count>=2:
    flag=1
    break
  pointer+=1
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 sys,math,collections,itertools
import functools
input = sys.stdin.readline


N=int(input())
A=list(map(int,input().split()))
fact = set()
for a in A:
    if a==1:
        fact.add(1)
        continue
    if a%2 == 0 and 2 in fact:
        break
    while a%2==0:
        fact.add(2)
        a//=2
            
    i =3
    while i*i <= a:
        if a%i ==0 and i in fact:
            break
        while a%i==0:
            fact.add(i)
            a//=i
        else:
            i +=2
    else:
        if a != 1:
            if a in fact:
                break
            fact.add(a)
        continue
    break
else:
    print('pairwise coprime')
    exit()
if functools.reduce(math.gcd,A)!=1:
    print('not coprime')
else:
    print('setwise coprime')

Solution (Python):
from sys import stdin, stdout
from math import gcd
N=10**6+2
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
mp=[0]*N;not_pairwise=1
for v in a:
    mp[v]+=1
for i in range(2,N):
    if sum(mp[i::i])>1:
        not_pairwise=0
        break
g = a[0]
for v in a:
    g = gcd(g, v)
if not_pairwise:
    print('pairwise coprime')
elif g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
def factorize(n, d):
  
    
    arr = []
    tmp = n
    while True:
      i = d[tmp]
      if i == 1:
        break
      
      while tmp%i==0:
        
        tmp //= i
      arr.append(i)
    if tmp!=1:
      arr.append(tmp)
    if arr==[]:
      arr.append(n)
    return arr

def minimum_prime(n):
  
  
    d = list(range(n+1))
    d[0] = 1
    for i in range(2, int(n**0.5) + 1):
        if d[i] != i:
          continue
        for j in range(i * 2, n + 1, i):
          if d[j] == j:
            d[j] = i
    return d  

def main():
  n = int(input())
  arr = list(map(int, input().split()))
  max_arr = max(arr)
  d = minimum_prime(max_arr)
  dp = [0]*(max_arr+1)
  
  
  searched = []
  for a in arr:
    if a != 1:
      primes = factorize(a, d)
      for p in primes:
        dp[p] += 1
  
  max_dp = max(dp)
  if max_dp < 2:
    print('pairwise coprime')
  elif max_dp == n:
    print('not coprime')
  else:
    print('setwise coprime')
    

main()

Solution (Python):
import math
 
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
 
input()
d = None
u = set()
for x in map(int, input().split()):
  d = math.gcd(d or x, x);
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print('not' if d > 1 else r, 'coprime')

Solution (Python):
import math
from functools import reduce

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

def factorize(n, d):
  
    
    arr = []
    tmp = n
    while True:
      i = d[tmp]
      if i == 1:
        break
      
      while tmp%i==0:
        
        tmp //= i
      arr.append(i)
    if tmp!=1:
      arr.append(tmp)
    if arr==[]:
      arr.append(n)
    return arr

def minimum_prime(n):
  
  
    d = list(range(n+1))
    d[0] = 1
    for i in range(2, int(n**0.5) + 1):
        if d[i] != i:
          continue
        for j in range(i * 2, n + 1, i):
          if d[j] == j:
            d[j] = i
    return d  

def main():
  n = int(input())
  arr = list(map(int, input().split()))
  max_arr = max(arr)
  d = minimum_prime(max_arr)
  dp = [0]*(max_arr+1)
  
  if gcd(*arr) != 1:
    print('not coprime')
    exit()
  
  searched = []
  for a in arr:
    if a != 1:
      primes = factorize(a, d)
      for p in primes:
        dp[p] += 1

  if max(dp) < 2:
    print('pairwise coprime')
  else:
    print('setwise coprime')
    

main()

Solution (Python):
import math
 
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
 
input()
d = None
u = set()
for x in map(int, input().split()):
  d = math.gcd(d or x, x);
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print('not' if d > 1 else r, 'coprime')

Solution (Python):
import math
 
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
 
input()
d = None
u = set()
for x in map(int, input().split()):
  d = math.gcd(d or x, x);
  s = set()
  while x > 1:
    p = spf[x]
    s.add(p)
    x //= p
  if u & s:
    r = 'setwise'
  u |= s
print('not' if d > 1 else r, 'coprime')

Solution (Python):
import math

N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'

input()
d = None
u = set()
for x in map(int, input().split()):
  d = math.gcd(d or x, x);
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print('not' if d > 1 else r, 'coprime')

Solution (Python):
import math

N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'

input()
d = None
u = set()
for x in map(int, input().split()):
  d = math.gcd(d, x) if d else x;
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print('not' if d > 1 else r, 'coprime')

Solution (Python):
from math import gcd


def prime_fac(x):
    pfs = set()
    for i in range(2, x):
        if i * i > x:
            break
        while x % i == 0:
            pfs.add(i)
            x //= i
    if x > 1:
        pfs.add(x)
    return pfs


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

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

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

s = set()
for v in a:
    p = prime_fac(v)
    ls, lp = len(s), len(p)
    s.update(p)
    if len(s) < ls + lp:
        print("setwise coprime")
        exit()
print("pairwise coprime")

Solution (Python):
from math import gcd


def prime_fac(x):
    pfs = set()
    for i in range(2, x):
        if i * i > x:
            break
        while x % i == 0:
            pfs.add(i)
            x //= i
    if x > 1:
        pfs.add(x)
    return pfs


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

a.sort()
xs = [0] * (a[-1] + 1)
g = a[0]
for v in a:
    g = gcd(g, v)
    xs[v] += 1

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

s = set()
for v in a:
    p = prime_fac(v)
    ls, lp = len(s), len(p)
    s.update(p)
    if len(s) < ls + lp:
        print("setwise coprime")
        exit()
print("pairwise coprime")

Solution (Python):
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'

input()
a = input().split()
m = a.count('1')
if len(a) > m + 1:
  u = set()
  i = None
  for x in map(int, a):
    s = set()
    while x > 1:
      p = spf[x]
      if p in u:
        r = 'setwise'
      s.add(p)
      x //= p
    u |= s
    if m == 0:
      if i is None: i = s
      else: i &= s
  if i:
    r = 'not'
print(r, 'coprime')

Solution (Python):
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7
 
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 euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
 
def multiple(a, b):
    return a*b // euclid(a, b)
 
def gcd(nums):
    return functools.reduce(euclid, nums)
 
if gcd(A) != 1:
    print("not coprime")
 
else:
    """
    flag = 0
    M = [False]*(10**6+1)
    for i in range(N):
        n = A[i]
        if M[n]:
            flag = 1
            break
        if n != 1:
            k = 1
            while n*k <= 10**6:
                M[n*k] = True
                k += 1
    """
    flag = 0
    M = [False]*(10**6+1)
    for i in range(N):
        n = A[i]
        if n == 1:
            continue
        l = factorization(n)
        for j in range(len(l)):
            p = l[j][0]
            if M[p]:
                flag = 1
                break
            M[p] = True
        else:
            continue
        break
    if flag == 0:
        print("pairwise coprime")
    else:
        print("setwise coprime")

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

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

one = A.count(1)

def find_prime(n):
    prime_list = []
    find_list = list(range(2,n+1))
    while True:
        if find_list[0] > n**(1/2):
            prime_list.extend(find_list)
            break
        else:
            head = find_list[0]
            prime_list.append(head)
            find_list.pop(0)
            find_list = [num for num in find_list if num % head != 0]
    return prime_list

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 euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)

def multiple(a, b):
    return a*b // euclid(a, b)

def gcd(nums):
    return functools.reduce(euclid, nums)

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

else:
    """
    flag = 0
    M = [False]*(10**6+1)
    for i in range(N):
        n = A[i]
        if M[n]:
            flag = 1
            break
        if n != 1:
            k = 1
            while n*k <= 10**6:
                M[n*k] = True
                k += 1
    """
    flag = 0

    if N-one <= 78500:
        M = [False]*(10**6+1)
        for i in range(N):
            n = A[i]
            if n == 1:
                continue
            l = factorization(n)
            for j in range(len(l)):
                p = l[j][0]
                if M[p]:
                    flag = 1
                    break
                M[p] = True
    else:
        flag = 1
    
    if flag == 0:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Solution (Python):
import itertools
import collections

class PrimeFactorize:
    def __init__(self, n):
        self.prime_factor_table = self.create_prime_factor_table(n)

    
    def create_prime_factor_table(self, n):
        self.table = [0] * (n + 1)
        
        for i in range(2, n + 1):
            if self.table[i] == 0:
                for j in range(i + i, n + 1, i):
                    self.table[j] = i
        return self.table

    def prime_factor(self, n):
        prime_count = collections.Counter()
        
        while self.prime_factor_table[n] != 0:
            prime_count[self.prime_factor_table[n]] += 1
            n //= self.prime_factor_table[n]
        prime_count[n] += 1
        return prime_count

N = int(input())
A_s = list(map(int, input().split()))
pc = True
sc = True
M = {}
MAX = 0
pf = PrimeFactorize(10**6+1)

for i,A in enumerate(A_s):
    L = pf.prime_factor(A)
    for l in L.keys():
        if l == 1:
            continue
        if l in M:
            
            M[l] += 1
            pc = False
        else:
            M[l] = 1
        MAX = max(MAX, M[l])
    if not pc and MAX <= i:
        break
else:
    sc = False

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

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

x = max(A)
hurui = [x]*(x+1)
for i in range(2, x+1):
    for j in range(i, x+1, i):
        hurui[j] = min(i, hurui[j])

cnt = Counter([1])
for i in range(N):
    num = A[i]
    while num > 1:
        x = hurui[num]
        while num%x == 0:
            num //= x
        cnt[x] += 1

a = cnt.most_common(1)[0][1]
if a == 1:
    print("pairwise coprime")
elif a < N:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
import itertools
import collections
def prime_factor_table(n):
    table = [0] * (n + 1)
    
    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i
    
    return table

def prime_factor(n, prime_factor_table):
    prime_count = collections.Counter()
    
    while prime_factor_table[n] != 0:
        prime_count[prime_factor_table[n]] += 1
        n //= prime_factor_table[n]
    prime_count[n] += 1
    
    return prime_count

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

pc = True
sc = True
M = {}
MAX = 0
TABLE = prime_factor_table(10**6+1)

for i,A in enumerate(A_s):
    L = prime_factor(A, TABLE)
    for l in L.keys():
        if l == 1:
            continue
        if l in M:
            
            M[l] += 1
            pc = False
        else:
            M[l] = 1
        MAX = max(MAX, M[l])
    if not pc and MAX <= i:
        break
else:
    sc = False

if pc:
    print('pairwise coprime')
elif sc:
    print('setwise coprime')
else:
    print('not 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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

import itertools
import collections
def prime_factor_table(n):
    table = [0] * (n + 1)
    
    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i
    
    return table

def prime_factor(n, prime_factor_table):
    prime_count = collections.Counter()
    
    while prime_factor_table[n] != 0:
        prime_count[prime_factor_table[n]] += 1
        n //= prime_factor_table[n]
    prime_count[n] += 1
    
    return prime_count

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

pc = True
sc = True
M = {}
MAX = 0
TABLE = prime_factor_table(10**6+1)

for i,A in enumerate(A_s):
    L = prime_factor(A, TABLE)
    for l in L.keys():
        if l == 1:
            continue
        if l in M:
            
            M[l] += 1
            pc = False
        else:
            M[l] = 1
        MAX = max(MAX, M[l])
    if not pc and MAX <= i:
        break
else:
    sc = False

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

Solution (Python):
import sys
input = sys.stdin.readline
def main():
  n = int(input())
  A = tuple(map(int, input().split()))
  U = 10**6
  D = list(range(U+1))
  i = 2
  while i*i <= U:
    if D[i] != i:
      i += 1
      continue
    for j in range(i*i, U+1, i):
      D[j] = min(D[j], i)
    i += 1
  C = [0]*(U+1)
  is_pairwise = True
  for a in A:
    while a > 1:
      d = D[a]
      while a%d == 0:
        a //= d
      if C[d]:
        is_pairwise = False
      C[d] += 1
  if max(C) == n:
    print("not coprime")
  else:
    if is_pairwise:
      print("pairwise coprime")
    else:
      print("setwise coprime")
if __name__ == "__main__":
  main()

Solution (Python):
def main():
    n, *a, = map(int, open(0).read().split())
    m = max(a)

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

    def primes(x):
        ps = set()
        while x != 1:
            p = d[x]
            ps.add(p)
            x = x // d[x]
        return ps

    b = set()
    c = primes(a[0])
    f = 0
    for i in a:
        ps = primes(i)
        if f == 0:
            if b & ps:
                f = 1
            b |= ps
        c &= ps
    else:
        if f == 1 and len(c) > 0:
            f = 2
    
    ans = ["pairwise coprime", "setwise coprime", "not coprime"][f]
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
A = tuple(map(int, input().split()))
U = 10**6
D = list(range(U+1))
i = 2
while i*i <= U:
  if D[i] != i:
    i += 1
    continue
  for j in range(i*i, U+1, i):
    D[j] = min(D[j], i)
  i += 1
C = [0]*(U+1)
is_pairwise = True
for a in A:
  while a > 1:
    d = D[a]
    while a%d == 0:
      a //= d
    if C[d]:
      is_pairwise = False
    C[d] += 1
if max(C) == n:
  print("not coprime")
else:
  if is_pairwise:
    print("pairwise coprime")
  else:
    print("setwise coprime")

Solution (Python):
import sys
import math
input = sys.stdin.readline
def prime_factor(n):
    factors = []
    while n%2==0:
        factors.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            factors.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        factors.append(n)
    return set(factors)


n=int(input())
L=list(map(int,input().split()))
val = L[0]
for i in range(1,n):
    val=math.gcd(val,L[i])
if val!=1:
    print('not coprime')
    sys.exit()
d={}
for i in range(n):
    factors = prime_factor(L[i])
    for j in factors:
        if j not in d.keys():
            d[j]=1
        else:
            print('setwise coprime')
            sys.exit()
print('pairwise coprime')

Solution (Python):
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
n = int(input())
a = [int(x) for x in input().split() if x > '1']
if len(a) > 1:
  u = set()
  i = None
  for x in a:
    s = set()
    while x > 1:
      p = spf[x]
      if p in u:
        r = 'setwise'
      s.add(p)
      x //= p
    u |= s
    if len(a) == n:
      if i is None: i = s
      else: i &= s
  if i:
    r = 'not'
print(r, 'coprime')

Solution (Python):
import math
N=int(input())
m=10**6+1
M=[0]*m
g=0
for i in map(int,input().split()):M[i]+=1;g=math.gcd(g,i)
if g>1:print('not coprime')
elif all(sum(M[i::i])<=1 for i in range(2,m)):print('pairwise coprime')
else:print('setwise coprime')

Solution (Python):
import math
N=int(input())
m=10**6+1
M=[0]*m
g=0
for i in map(int,input().split()):M[i]+=1;g=math.gcd(g,i)
if g>1:print('not coprime')
elif all(sum(M[i::i])<=1 for i in range(2,m)):print('pairwise coprime')
else:print('setwise coprime')

Solution (Python):
def main():
    n, *a, = map(int, open(0).read().split())
    m = max(a)

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

    def primes(x):
        ps = set()
        while x != 1:
            p = d[x]
            ps.add(p)
            x = x // d[x]
        return ps

    b = set()
    c = primes(a[0])
    f = 1
    for i in a:
        ps = set()
        while i != 1:
            p = d[i]
            ps.add(p)
            i = i // d[i]
        if f:
            if b & ps:
                f = 0
            b |= ps
        c &= ps

    if f:
        ans = "pairwise coprime"
    elif len(c) == 0:
        ans = "setwise coprime"
    else:
        ans = "not coprime"

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

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

INF = 10**6

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

D = min_primes(INF)
Ps = defaultdict(int)

def fact(x):
  Ps[D[x]] += 1
  pre = x
  x //= D[x]
  while x > 1:
    if D[x] > D[pre]:
      Ps[D[x]] += 1
    pre = x
    x //= D[x]

for a in A:
  fact(a)

Ps[1] = 1
ans = max(Ps.values())

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

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**18
def solve(N,A):
    P = set()

    for i in range(N):
        n = A[i]
        if n % 2 == 0 and 2 in P: break
        while n % 2 == 0:
            P.add(2)
            n //= 2
            
        f = 3
        while f * f <= n:
            if n % f == 0:
                if f in P: break
                P.add(f)
                while n%f == 0:
                    n //= f
            else:
                f += 2
        else:
            if n != 1:
                if n in P: break
                P.add(n)
            
            continue
        break
    else:
        return 0
        
    return 1 



def main():
    N=ii()
    A=np.array(list(mi()))

    flag = solve(N,A)
    if flag == 0:
        print("pairwise coprime")
    else:
        gcd = np.gcd.reduce(A)
        if gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")
       

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    
    cc.export('solve', '(i8,i8[:])')(solve)
    cc.compile()

if __name__ == '__main__':
    
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**18
def solve(N,A):
    P = set()

    for i in range(N):
        n = A[i]
        if n % 2 == 0 and 2 in P: break
        while n % 2 == 0:
            P.add(2)
            n //= 2
            
        f = 3
        while f * f <= n:
            if n % f == 0:
                if f in P: break
                P.add(f)
                while n%f == 0:
                    n //= f
            else:
                f += 2
        else:
            if n != 1:
                if n in P: break
                P.add(n)
            
            continue
        break
    else:
        return 0
        
    return 1 



def main():
    N=ii()
    A=np.array(list(mi()))

    flag = solve(N,A)
    if flag == 0:
        print("pairwise coprime")
    else:
        gcd = np.gcd.reduce(A)
        if gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")
       

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    
    cc.export('solve', '(i8,i8[:])')(solve)
    cc.compile()

if __name__ == '__main__':
    
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**18
def solve(N,A):
    P = set()

    fl = True
    for i in range(N):
        n = A[i]
        if n % 2 == 0 and 2 in P: 
            fl = False
            break
        while n % 2 == 0:
            P.add(2)
            n //= 2
            
        f = 3
        while f * f <= n:
            if n % f == 0:
                if f in P: 
                    fl = False
                    break
                
                P.add(f)
                while n % f == 0:
                    n //= f
            else:
                f += 2

        if n != 1:
            if n in P:
                fl = False
                break
            P.add(n)
            
        if not fl:
            break

        
    return fl



def main():
    N=ii()
    A=np.array(list(mi()))

    flag = solve(N,A)
    if flag:
        print("pairwise coprime")
    else:
        gcd = np.gcd.reduce(A)
        if gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")
       

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    
    cc.export('solve', '(i8,i8[:])')(solve)
    cc.compile()

if __name__ == '__main__':
    
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()

Solution (Python):
import numpy as np

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

count=[0]*(1000001)
for a in A:count[a]+= 1


if np.gcd.reduce(A)!=1:
    print("not coprime")

elif np.all([sum(count[i::i])<=1 for i in range(2,10**6+1)]):
    print("pairwise coprime")
else:
    print("setwise coprime")

Solution (Python):
def main():
    from math import gcd
    _ = int(input())
    A = [int(i) for i in input().split()]

    def prime_factorize(n):
        for i in range(2, n+1):
            if i*i > n:
                break
            if n % i != 0:
                continue
            while n % i == 0:
                n //= i
            B[i] += 1
        if n != 1:
            B[n] += 1

    
    
    check = True if sum(a != 1 for a in A) <= 80000 else False
    maxA = max(A)
    B = [0] * (maxA + 1)
    if check:
        for a in A:
            prime_factorize(a)

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

    if g != 1:
        print("not coprime")
    elif check and max(B) <= 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    main()

Solution (Python):
from math import gcd

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


tmp = 0
for a in A:
    tmp = gcd(tmp, a)
isSetwise = (tmp == 1)


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

cnt = 0
isPairwise = True
for i in range(2, M + 1):
    isPairwise &= (sum(sieve[j] for j in range(i, M + 1, i)) <= 1)


if isPairwise:
    ans = 'pairwise coprime'
elif isSetwise:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)