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 sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
import random
J=int(1e9)+7


X=[False]*(10**6+1)
P=[]
for i in range(2,len(X)):
    if X[i] is False:
        for j in range(2*i,len(X),i):
            X[j]=True
for i in range(2,len(X)):
    if X[i] is False:
        P.append(i)


n=int(input())
A=INPUT()
ans=0
V=[0]*(10**6+1)
for i in range(n):
    ans=math.gcd(ans,A[i])
    V[A[i]]+=1
if ans==1:
    bool=True
    for i in range(2,10**6+1):
        if V[i]>=2:
            bool=False
            break
    if bool:
        for ele in P:
            c=0
            for i in range(ele,10**6+1,ele):
                if V[i]>0 and i%ele==0:
                    c+=1
            if c>1:
                bool=False
                break
        if bool:
            print("pairwise coprime")
        else:
            print("setwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
from math import gcd

N,*A = map(int, open(0).read().split())
m = max(A)
if m == 1:
    print('pairwise coprime')
else:
    minfactor = [-1] * (m+1)
    for i in range(2,m+1):
        if minfactor[i] == -1:
            for j in range(1,m//i+1):
                minfactor[i*j] = i
    temp = gcd(A[0],A[1])
    for i in range(2,N):
        temp = gcd(temp,A[i])
        if temp == 1:
            break
    if temp > 1:
        print('not coprime')
    else:
        s = set()
        for x in A:
            if x > 1:
                p = x
                while p > 1:
                    mf = minfactor[p]
                    if mf not in s:
                        s.add(mf)
                        while p % mf == 0:
                            p = p // mf
                    else:
                        break
                else:
                    continue
                print('setwise coprime')
                break
        else:
            print('pairwise coprime')

Solution (Python):
import sys


def LI():
    return list(map(int, input().split()))


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


input()
A = LI()

g = 0
for a in A:
    g = gcd(g, a)
if g != 1:
    print("not coprime")
    sys.exit()

sosudayo = [True] * 1100000
sosudayo[0] = False
sosudayo[1] = False
for i in range(2, 1100000):
    if not sosudayo[i]:
        continue
    for j in range(i*i, 1100000, i):
        sosudayo[j] = False

used = [False] * 1100000
sosu = [a for a in A if sosudayo[a]]
for i in sosu:
    used[i] = True
ruto_sosu = [a for a in range(1100) if sosudayo[a]]
not_sosu = [a for a in A if not sosudayo[a]]

for i in not_sosu:
    for j in ruto_sosu:
        if i == 1:
            break
        if i % j != 0:
            continue
        if used[j]:
            print("setwise coprime")
            sys.exit()
        used[j] = True
        while i % j == 0:
            i //= j
    if i > 1:
        if used[i]:
            print("setwise coprime")
            sys.exit()
        used[i] = True

print("pairwise coprime")

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    maxA = max(A)
    if maxA == 1:
        print('pairwise coprime')
        return
    prime = [i if i % 2 != 0 else 2 for i in range(maxA+1)]
    f = [False] * (maxA+1)
    for i in range(3, int(maxA**.5)+1):
        if prime[i] != i:
            continue
        p = i * 2
        while p <= maxA:
            if prime[p] == p:
                prime[p] = i
            p += i

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

    setwise_coprime = A[0]
    for An in A[1:]:
        setwise_coprime = gcd(setwise_coprime, An)
        if setwise_coprime == 1:
            break
    
    for An in A:
        if An == 1:
            continue
        
        not_pairwise_coprime = False
        while prime[An] != An:
            
            if f[prime[An]]:
                not_pairwise_coprime = True
                break
            f[prime[An]] = True
            prime_An = prime[An]
            while An % prime_An == 0:
                An //= prime_An
        else:
            if An != 1:
                if f[An]:
                    not_pairwise_coprime = True
                else:
                    f[An] = True
        if not_pairwise_coprime:
            break
        
    else:
        print('pairwise coprime')
        return
    if setwise_coprime == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    maxA = max(A)
    if maxA == 1:
        print('pairwise coprime')
        return
    prime = [i if i % 2 != 0 else 2 for i in range(maxA+1)]
    f = [False] * (maxA+1)
    for i in range(3, int(maxA**.5)+1):
        if prime[i] != i:
            continue
        p = i * 2
        while p <= maxA:
            if prime[p] == p:
                prime[p] = i
            p += i

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

    setwise_coprime = A[0]
    for An in A[1:]:
        setwise_coprime = gcd(setwise_coprime, An)
        if setwise_coprime == 1:
            break
    
    for An in A:
        if An == 1:
            continue
        
        not_pairwise_coprime = False
        while prime[An] != An:
            
            if f[prime[An]]:
                not_pairwise_coprime = True
                break
            f[prime[An]] = True
            prime_An = prime[An]
            while An % prime_An == 0:
                An //= prime_An
        else:
            if An != 1:
                if f[An]:
                    not_pairwise_coprime = True
                else:
                    f[An] = True
        if not_pairwise_coprime:
            break
        
    else:
        print('pairwise coprime')
        return
    if setwise_coprime == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Solution (Python):

import math
from functools import reduce


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


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


def eratosthenes(n):
    D = [0]*(n+1)
    for i in range(2, n+1):
        if D[i] > 0:
            continue
        for j in range(i, n+1, i):
            D[j] = i
    return D


N = int(input())
A = list(map(int, input().split()))
D = eratosthenes(10**6+1)

dic = {}
for i in A:
    while i != 1:
        if i in dic:
            dic[i] += 1
        else:
            dic[i] = 1
        i //= D[i]
isPairwise = True
for i in dic.items():
    if i[1] > 1:
        isPairwise = False
        break


def is_pairwise():
    used_primes = [False] * (10**6 + 1)
    for a in A:
        while a > 1:
            prime = D[a]
            while a % prime == 0:
                a //= prime
            if used_primes[prime]:
                return False
            used_primes[prime] = 1
    return True



if is_pairwise():
    print("pairwise coprime")
elif gcd_list(A) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
import math
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
a = set()

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

def prime_factorize(n):
  global a
  tmp = []
  while n % 2 == 0:
    if 2 not in a:
      tmp.append(2)
      n //= 2
    else:
      return False
  f = 3
  while f * f <= n:
    if n % f == 0:
      if f not in a:
        tmp.append(f)
        n //= f
      else:
        return False
    else:
      f += 2
  if n != 1:
    if n not in a:
      tmp.append(n)
    else:
      return False
  a |= set(tmp)
  return True

flag = True
for i in range(N):
  ans = prime_factorize(A[i])
  if not ans:
    flag = False
    break
if flag:
  print('pairwise coprime')
elif gcd_list(A) == 1:
  print('setwise coprime')
else:
  print('not coprime')

Solution (Python):
import collections
import heapq
import math
import random
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500005)
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
rs = lambda: input().rstrip()

Nmax = 10**6 + 1

n = ri()
A = rl()

f = [0] * Nmax
for v in A:
    f[v] += 1
for i in range(2, Nmax//2+1):
    for j in range(i*2, Nmax, i):
        f[i] += f[j]

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

if max(f[2:]) <= 1:
    print("pairwise coprime")
else:
    x = 0
    for v in A:
        x = gcd(x, v)
    if x == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Solution (Python):
"""E."""

import sys


def input() -> str:  
    """Input."""
    return sys.stdin.readline()[:-1]


RESULT_TEXT = {
    1: 'pairwise coprime',
    2: 'setwise coprime',
    3: 'not coprime',
}

n = int(input())

a_list = list(map(int, input().split(' ')))

ans = 0

MAX = 1000000 + 1
counts = [0] * MAX
for a in a_list:
    counts[a] += 1

max_count = 0

for i in range(2, MAX):
    max_count = max(max_count, sum(counts[i::i]))

if max_count == n:
    ans = 3
elif max_count >= 2:
    ans = 2
else:
    ans = 1

print(RESULT_TEXT[ans])

Solution (Python):
N=int(input())
from math import gcd
from functools import reduce
l=list(map(int,input().split()))
sw=0
c=[0]*1000001
for i in l:
   c[i]+=1
if all(sum(c[i::i])<=1 for i in range(2,1000001)):
   print("pairwise coprime")
elif reduce(gcd,l)==1:
   print("setwise coprime")
else:
   print("not coprime")

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
def prime_factorize(n):
    prime_fact = []
    while n%2 == 0:
        prime_fact.append(2)
        n//=2
    f = 3
    while f * f <= n:
        if n % f == 0:
            prime_fact.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        prime_fact.append(n)
    return prime_fact

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    prefix_gcd = a[0]
    dp = [0]*(max(a)+1)
    for i in range(n):
        prefix_gcd = math.gcd(prefix_gcd,a[i])

    for i in range(n):
        d = prime_factorize(a[i])
        d = set(d)
        for j in d:
            dp[j]+=1
    pair = True
    for i in range(len(dp)):
        if dp[i] > 1:
            pair = False
    if pair == True and prefix_gcd == 1:
        print("pairwise coprime")
    elif pair == False and prefix_gcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Solution (Python):
import math
import collections
import copy
import sys

n = int(input())

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

limit = 10 ** 6

sCheck = math.gcd(a[0],a[1])
if n == 2:
    if sCheck == 1:
        print("pairwise coprime")
    else:
        print("not coprime")
    sys.exit()
else:
    for i in range(2,n):
        sCheck = math.gcd(sCheck,a[i])


beforeQ = collections.deque([int(i) for i in range(3,(limit + 1))])
D = dict()
p = 2
D[2] = 2
D[1] = 1

while p < math.sqrt(limit):
    afterQ = collections.deque()
    while len(beforeQ) > 0:        
        k = beforeQ.popleft()
        if k % p != 0:
            afterQ.append(k)
        else:
            D[k] = p
    beforeQ = copy.copy(afterQ)
    p = beforeQ.popleft()
    D[p] = p
while len(beforeQ) > 0:
    k = beforeQ.popleft()
    D[k] = k
    
ansSet = set()
count = 0

for i in a:
    k = i
    kSet = set()
    while k != 1:
        if D[k] in ansSet:
            if not(D[k] in kSet):
                count = 1
                break
        else:
            ansSet.add(D[k])
            kSet.add(D[k])
        k = int(k // D[k])
    if count == 1:
        break

if count == 0:
    print("pairwise coprime")
elif sCheck == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):


class SpeedPrime:
    
    def __init__(self, a):
        self.d = [i for i in range(a+1)]

        i=2
        while i*i<=a:
            if self.d[i]==i:
                j=i*i
                while j<=a:
                    if self.d[j]==j:
                        self.d[j]=i
                    j+=i
            i+=1

    
    def fac(self, n):
        ret = dict()
        while n!=1:
            prime=self.d[n]
            if prime in ret:
                ret[prime]+=1
            else:
                ret[prime]=1
            n=n//prime
        return ret

import math
from functools import reduce
def gcd(numbers):
    return reduce(math.gcd, numbers)

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

sp=SpeedPrime(max(a))

d=set()
pc=True
for i in a:
    prime=sp.fac(i)
    for k in prime.keys():
        if k in d:
            pc=False
            break
        else:
            d.add(k)

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

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

Solution (Python):
from math import sqrt, gcd
import sys


def osk_a(M):
    p = [i for i in range(M+1)]
    for x in range(2, int(sqrt(M))+1):
        if p[x] == x:
            for y in range(2*x, M+1, x):
                if p[y] == y:
                    p[y] = x
    return p


def g(a):
    g = 0
    for x in a:
        g = gcd(g, x)
    return g


def main():
    n = int(sys.stdin.buffer.readline())
    a = list(map(int, sys.stdin.buffer.readline().split()))
    if g(a) > 1:
        print("not coprime")
        exit()
    p = osk_a(10**6)
    chk = set()
    while a[0] > 1:
        chk.add(p[a[0]])
        a[0] //= p[a[0]]
    for x in a[1:]:
        tmp = set()
        while x > 1:
            tmp.add(p[x])
            x //= p[x]
        if not chk.isdisjoint(tmp):
            print("setwise coprime")
            exit()
        chk |= tmp
    print("pairwise coprime")


if __name__ == "__main__":
    main()

Solution (Python):
from math import sqrt, gcd
import sys


def osk_a(M):
    p = [i for i in range(M+1)]
    for x in range(2, int(sqrt(M))+1):
        if p[x] == x:
            for y in range(2*x, M+1, x):
                if p[y] == y:
                    p[y] = x
    return p


def g(a):
    g = 0
    for x in a:
        g = gcd(g, x)
    return g


def main():
    n = int(sys.stdin.buffer.readline())
    a = list(map(int, sys.stdin.buffer.readline().split()))
    if g(a) > 1:
        print("not coprime")
        exit()
    p = osk_a(10**6)
    chk = set()
    t = a[0]
    while t > 1:
        chk.add(p[t])
        t //= p[t]

    for x in a[1:]:
        tmp = set()
        while x > 1:
            tmp.add(p[x])
            x //= p[x]
        if chk.isdisjoint(tmp):
            chk |= tmp
        else:
            print("setwise coprime")
            exit()
    print("pairwise coprime")


if __name__ == "__main__":
    main()

Solution (Python):
from math import sqrt, gcd
import sys


def osk_a(M):
    p = [i for i in range(M+1)]
    for x in range(2, int(sqrt(M))+1):
        if p[x] == x:
            for y in range(2*x, M+1, x):
                if p[y] == y:
                    p[y] = x
    return p


def g(a):
    g = 0
    for x in a:
        g = gcd(g, x)
    return g


def main():
    n = int(sys.stdin.buffer.readline())
    a = list(map(int, sys.stdin.buffer.readline().split()))
    if g(a) > 1:
        print("not coprime")
        exit()
    p = osk_a(10**6)
    chk = set()
    t = a[0]
    while t > 1:
        chk.add(p[t])
        t //= p[t]

    for x in a[1:]:
        tmp = set()
        while x > 1:
            tmp.add(p[x])
            x //= p[x]
        if len(chk & tmp):
            print("setwise coprime")
            exit()
        else:
            chk |= tmp
    print("pairwise coprime")


if __name__ == "__main__":
    main()

Solution (Python):
from math import gcd
n = int(input())
a = list(map(int, input().split()))
max_a = max(a)
cnt_a = [0] * (max_a + 1)
for ai in a:
  cnt_a[ai] += 1
ans = 'pairwise'
for i in range(2, max_a + 1):
  cnt = 0
  for j in range(i, max_a + 1, i):
    cnt += cnt_a[j]
  if cnt > 1:
    ans = 'setwise'
g = 0
for ai in a:
  g = gcd(g, ai)

if ans == 'pairwise':
  print(ans, 'coprime')
elif ans == 'setwise' and g == 1:
  print(ans, 'coprime')
else:
  print('not coprime')

Solution (Python):
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))

flag = True

d_set = set()
for a in A:
    while a != 1:
        d = D[a]
        if d in d_set:
            flag = False
            break
        else:
            d_set.add(d)
        while a > 1 and a % d == 0:
            a = a // d
    if not(flag):
        break



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

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

Solution (Python):
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))

flag = True

d_set = set()
for a in A:
    while a != 1:
        d = D[a]
        if d in d_set:
            flag = False
            break
        else:
            d_set.add(d)
        while a > 1 and a % d == 0:
            a = a // d



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

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

Solution (Python):
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))

flag = True

d_set = set()
for a in A:
    while a != 1:
        d = D[a]
        if d in d_set:
            flag = False
            break
        else:
            d_set.add(d)
        
        while a % d == 0 and a > 1:
            a = a // d

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

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

Solution (Python):
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))

flag = True

d_set = set()
for k in A:
    while k != 1:
        div = D[k]
        if div in d_set:
            flag = False
            break
        else:
            d_set.add(div)
        
        while k % div == 0 and k > 1:
            k = k // div

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

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

Solution (Python):
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))
pairwise_coprime = True
use_divnum = set()
for k in A:
    while k != 1:
        div = D[k]
        if div in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(div)
        
        while k % div == 0 and k > 1:
            k = k // div

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

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

Solution (Python):
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))
pairwise_coprime = True
use_divnum = set()
for k in A:
    while k != 1:
        if D[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(D[k])
        div = D[k]
        while k % div == 0 and k > 1:
            k = k // div

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

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

Solution (Python):
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))
pairwise_coprime = True
use_divnum = set()
for i in range(N):
    k = A[i]
    while k != 1:
        if D[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(D[k])
        div = D[k]
        while k % div == 0 and k > 1:
            k = k // div

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

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

Solution (Python):
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))
pairwise_coprime = True
use_divnum = set()
for i in range(N):
    k = A[i]
    while k != 1:
        if D[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(D[k])
        div = D[k]
        while k % div == 0 and k > 1:
            k = k // div
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = A[0]
for i in range(N):
    gcd_of_a = gcd(gcd_of_a, A[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
import sys
from math import gcd


def osa_k(sieve, MAXN):
    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


input = lambda: sys.stdin.readline().rstrip()
n = int(input())
A = list(map(int, input().split()))
nowgcd = A[0]

for i in A:
    nowgcd = gcd(nowgcd, i)
if nowgcd != 1:
    print('not coprime')
    exit()

MAXN = 10**6 + 5
sieve = [i for i in range(MAXN + 1)]
p = 2
osa_k(sieve, MAXN)

check = set()
for a in A:
    tmp = set()
    while (a > 1):
        tmp.add(sieve[a])
        a //= sieve[a]
    for p in tmp:
        if p in check:
            print('setwise coprime')
            exit()
        check.add(p)
print('pairwise coprime')

Solution (Python):
import sys
from math import gcd
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
A = list(map(int, input().split()))
nowgcd = A[0]

for i in A:
    nowgcd = gcd(nowgcd, i)
if nowgcd != 1:
    print('not coprime')
    exit()


MAXN = 10**6 + 5
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

check = set()
for a in A:
    tmp = set()
    while (a > 1):
        tmp.add(sieve[a])
        a //= sieve[a]
    for p in tmp:
        if p in check:
            print('setwise coprime')
            exit()
        check.add(p)
print('pairwise coprime')

Solution (Python):
def GCD(m, n):
    while n != 0:
        m, n = n, m % n
    return m

def gcd_all(a):
    n = len(a)
    gcd = a[0]
    for i in range(1, n):
        gcd = GCD(gcd, a[i])
    return gcd

def f(a):
    mx = 10**6
    p = set([])
    sieve = [i for i in range(mx + 1)]
    for i in range(2, int(mx**0.5 + 1)):
        for j in range(2 * i, mx + 1, i):
            if sieve[j] > i:
                sieve[j] = i
    pairwise_coprime = True
    for i in a:
        p2 = set([])
        while i > 1:
            p2.add(sieve[i])
            i //= sieve[i]
        for j in p2:
            if j in p:
                pairwise_coprime = False
                break
            p.add(j)
        if pairwise_coprime == False:
            break
    gcd = gcd_all(a)
    if pairwise_coprime == False and gcd == 1:
        return 'setwise coprime'
    elif pairwise_coprime:
        return 'pairwise coprime'
    else:
        return 'not coprime'

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

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



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


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

def is_pairwise():
    used_primes = [False] * (10**6 + 1)
    pairwise_flag = 1
    for a in A:
        curr_primes = set()
        while a > 1:
            prime = number_to_prime[a]
            while a % prime == 0:
                a //= prime
            if used_primes[prime]:
                return False
            used_primes[prime] = 1
    return True

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pairwise():
    print("pairwise coprime")
elif is_setwise(*A):
    print("setwise coprime")
else:
    print("not coprime")

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



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


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

def is_pair_copr(A):
    import numpy as np
    U = 1 << 20
    div_p = np.arange(U)
    for p in range(2, U):
        if div_p[p] != p:
            continue
        div_p[p::p] = p
    used = np.zeros(U, np.bool_)
 
    for x in A:
        while x > 1:
            p = div_p[x]
            while x % p == 0:
                x //= p
            if used[p]:
                return False
            used[p] = True
    return True

def is_pairwise():
    used_primes = set()
    pairwise_flag = 1
    for a in A:
        curr_primes = set()
        while a > 1:
            prime = number_to_prime[a]
            curr_primes.add(prime)
            a //= prime
        if used_primes & curr_primes:
            pairwise_flag = 0
            break
        else:
            used_primes = used_primes | curr_primes
    return pairwise_flag

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pair_copr(A):
    print("pairwise coprime")
elif is_setwise(*A):
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
from collections import defaultdict
import sys
input = sys.stdin.readline

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



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


primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i])
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1



if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

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