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
import math


N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


def eatosthenes(N):
    prime = []
    D = [1] * (N + 1)

    for i in range(2, N + 1):
        if D[i] != 1:
            continue
        for j in range(N // i + 1):
            if D[i * j] == 1:
                D[i * j] = i
        prime.append(i)

    return prime


def main():
    N = int(sys.stdin.readline().rstrip())
    A = [int(x) for x in sys.stdin.readline().rstrip().split()]

    maxA = max(A)
    primelist = eatosthenes(maxA)

    
    C = [0] * (maxA + 1)
    for a in A:
        C[a] += 1

    pc = True

    
    for p in primelist:
        cnt = 0
        for k in range(maxA // p + 1):
            cnt += C[k * p]

        
        if cnt > 1:
            pc = False

    if pc:
        print("pairwise coprime")
        return

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

    if GCD == 1:
        print("setwise coprime")
        return

    print("not coprime")


main()

Solution (Python):
def gcd(a, b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)


def divisor(n):
    l = []
    i = 1
    while True:
        if n % i == 0:
            l.append(i)
            if i * i != n:
                l.append(n / i)
        i += 1
        if i * i >= n:
            break
    return sorted(l)


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

gcd_of_all = gcd(a[0], a[1])
for i in range(2, n):
    gcd_of_all = gcd(gcd_of_all, a[i])

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

s = set()

for i in range(n):
    l = divisor(a[i])
    for j in range(len(l)):
        if l[j] == 1:
            continue
        if l[j] in s:
            print("setwise coprime")
            exit()
        else:
            s.add(l[j])

print("pairwise coprime")

Solution (Python):
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8,i8[:]), cache=True)
def main(N,A):
  Amax = A.max()
  lis = np.zeros(Amax+1, np.int64)
  table = np.full(Amax+1,Amax+1,np.int64)
  for i in range(2, Amax+1):
    table[i::i] = np.minimum(table[i::i],i)
  for i in range(N):
    p = A[i]
    while p>1:
      q = table[p]
      lis[q]+=1
      while p%q==0:
        p //= q
  setwise = False
  for i in range(Amax+1):
    if lis[i]==N:
      return 'not'
    if 2<=lis[i]<N:
      setwise=True
  if setwise==True:
    return 'setwise'
  return 'pairwise'

N = int(input())
A = np.array(list(map(int, input().split())))
print(main(N,A)+' coprime')

Solution (Python):
def main():
    from math import gcd
    from functools import reduce
    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()
    f = 0
    for i in a:
        ps = primes(i)
        if b & ps:
            f = 1
            break
        b |= ps
    if f > 0 and reduce(gcd, a) != 1:
        f = 2

    ans = ["pairwise coprime", "setwise coprime", "not coprime"][f]
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil, gcd
from bisect import bisect_left
import random
from itertools import combinations, accumulate
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

class PrimeTool(object):
    def __init__(self, n):
        self.n = n
        self.primes = []
        self.sieves = []

    def generate_primes(self):
        if len(self.primes) == 0 and len(self.sieves) == 0:
            is_prime = [True] * (self.n + 1)
            is_prime[0] = is_prime[1] = False
            self.sieves = [k for k in range(self.n + 1)]
            self.sieves[0] = 1
            for p in range(2, self.n + 1):
                if is_prime[p]:
                    self.primes.append(p)
                    for i in range(p, self.n + 1, p):
                        is_prime[i] = False
                        self.sieves[i] = p
            return self.primes

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

    def fast_factorization(self, num):
        
        self.generate_primes()

        
        arr = []
        temp = num
        while temp != 1:
            i = self.sieves[temp]
            c = 0
            while temp % i==0:
                c += 1
                temp //= i
            arr.append((i, c))
        if temp != 1:
            arr.append((temp, 1))
        return arr

def solve(N, A):
    tool = PrimeTool(max(A) + 1)
    primes = tool.generate_primes()
    ct = Counter()

    pair_wise = True
    for i, Ai in enumerate(A):
        arr = tool.fast_factorization(Ai)
        for p, _ in arr:
            ct[p] += 1
            if ct[p] > 1:
                pair_wise = False
                break
        if not pair_wise:
            break

    
    prod = A[0]
    for k in range(1, N):
        prod = gcd(prod, A[k])
    
    if pair_wise:
        print("pairwise coprime")
    elif prod == 1:
        print("setwise coprime")
    else:
        print("not coprime")

def main():
    from builtins import int, map
    N = int(input())
    A = list(map(int, input().split()))
    solve(N, A)

if __name__ == '__main__':
    main()

Solution (Python):
class Prime():
    def __init__(self, n):
        self.p = []
        self.d = [0] * n

        for i in range(2, n):
            if self.d[i] == 0:
                self.p.append(i)
                for j in range(i, n, i):
                    if self.d[j] == 0:
                        self.d[j] = i

        self.ind = [-1] * n
        for i in range(len(self.p)):
            self.ind[self.p[i]] = i

    def prime_factorization_index(self, x):
        l = []
        while x != 1:
            if l == [] or l[-1] != self.ind[self.d[x]]:
                l.append(self.ind[self.d[x]])
            x //= self.d[x]
        return l

    def num_prime(self):
        return len(self.p)

def main():

    from math import gcd
 
    n = int(input())
    a = list(map(int, input().split()))
 
    g = a[0]
    for i in range(1, n):
        g = gcd(g, a[i])
        if g == 1:
            break
    else:
        print('not coprime')
        exit()

    p = Prime(10**6 + 1)

    tf = [False] * p.num_prime()

    for i in range(1, n):
        l = p.prime_factorization_index(a[i])
        for i in l:
            if tf[i]:
                print('setwise coprime')
                exit()
            else:
                tf[i] = True

    print('pairwise coprime')

main()

Solution (Python):
class Prime():
    def __init__(self, n):
        self.p = []
        self.d = [0] * n

        for i in range(2, n):
            if self.d[i] == 0:
                self.p.append(i)
                for j in range(i, n, i):
                    if self.d[j] == 0:
                        self.d[j] = i

        self.ind = [-1] * n
        for i in range(len(self.p)):
            self.ind[self.p[i]] = i

    def prime_factorization_index(self, x):
        l = []
        while x != 1:
            if l == [] or l[-1] != self.ind[self.d[x]]:
                l.append(self.ind[self.d[x]])
            x //= self.d[x]
        return l

    def num_prime(self):
        return len(self.p)

def main():

    from math import gcd
 
    n = int(input())
    a = list(map(int, input().split()))
 
    g = a[0]
    for i in range(1, n):
        g = gcd(g, a[i])
        if g == 1:
            break
    else:
        print('not coprime')
        exit()

    p = Prime(10**6 + 1)

    tf = [False] * p.num_prime()

    for i in range(1, n):
        l = p.prime_factorization_index(a[i])
        for i in l:
            if tf[i]:
                print('setwise coprime')
                exit()
            else:
                tf[i] = True

    print('pairwise coprime')

main()

Solution (Python):
import sys
import math


N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


def main():
    N = int(sys.stdin.readline().rstrip())
    A = [int(x) for x in sys.stdin.readline().rstrip().split()]

    maxA = max(A)

    
    C = [0] * (maxA + 1)
    for a in A:
        C[a] += 1

    pc = True

    
    for p in range(2, maxA + 1):
        cnt = 0
        for k in range(maxA // p + 1):
            cnt += C[k * p]

        
        if cnt > 1:
            pc = False

    if pc:
        print("pairwise coprime")
        return

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

    if GCD == 1:
        print("setwise coprime")
        return

    print("not coprime")


main()

Solution (Python):
class Prime():
    def __init__(self, n):
        self.p = []
        self.d = [0] * n

        for i in range(2, n):
            if self.d[i] == 0:
                self.p.append(i)
                for j in range(i, n, i):
                    if self.d[j] == 0:
                        self.d[j] = i

        self.ind = [-1] * n
        for i in range(len(self.p)):
            self.ind[self.p[i]] = i

    def prime_factorization_index(self, x):
        l = []
        while x != 1:
            if l == [] or l[-1] != self.ind[self.d[x]]:
                l.append(self.ind[self.d[x]])
            x //= self.d[x]
        return l

    def num_prime(self):
        return len(self.p)

from math import gcd
 
n = int(input())
a = list(map(int, input().split()))
 
g = a[0]
for i in range(1, n):
    g = gcd(g, a[i])
    if g == 1:
        break
else:
    print('not coprime')
    exit()

p = Prime(10**6 + 1)

tf = [False] * p.num_prime()

for i in range(1, n):
    l = p.prime_factorization_index(a[i])
    for i in l:
        if tf[i]:
            print('setwise coprime')
            exit()
        else:
            tf[i] = True

print('pairwise coprime')

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def _make_prime_numbers(N: int):
    
    
    is_prime = [True] * (N + 1)
    is_prime[0] = False  
    is_prime[1] = False
    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

    primes = []
    for i, flg in enumerate(is_prime):
        if flg:
            primes.append(i)

    return primes


primes = _make_prime_numbers(10**6)


from bisect import bisect_left


def fast_factorization(N: int):
    
    
    if N == 1:
        return []  
    
    arr = []
    temp = N
    for p in primes[:bisect_left(primes, N**(1 / 2)) + 1]:
        if temp % p == 0:
            cnt = 0
            while temp % p == 0:
                cnt += 1
                temp //= p
            arr.append((p, cnt))
            if temp == 1:  
                break

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

    return arr


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from math import gcd


N = a_int()
A = ints()






g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  
for a in A:
    g_set = gcd(g_set, a)
    if flg:
        for p, n in fast_factorization(a):
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n








if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Solution (Python):
nn=int(input())
aa=list(map(int,input().split()))
a=[x for x in aa if x!=1]
n=len(a)
if n<=1:
  print('pairwise coprime')
  exit()


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
tmp=[i for i,j in factorization(min(a))]
not_flg=False
for t in tmp:
  flg=True
  for x in a:
    if x%t==0:
      pass
    else:
      flg=False
      break
  if flg:
    not_flg=flg
    break
if not_flg:
  if n==nn:
    print('not coprime')
  else:
    print('setwise coprime')
  exit()

if n>99999:
  print('setwise coprime')
  exit()
ary=set(())
for x in a:
  tmp={i for i,j in factorization(x)}
  for t in tmp:
    if t in ary:
      print('setwise coprime')
      exit()
    else:
      ary.add(t)
print('pairwise coprime')

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


def main():
    input()  
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 1
    histogram = [0] * MAX_A
    for x in array:
        histogram[int(x)] += 1

    for divider in range(2, MAX_A):
        count = sum(histogram[divider::divider])
        if count > 1:
            break
    else:
        return 'pairwise coprime'

    gcd_total = reduce(gcd, array)
    if gcd_total == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


if __name__ == '__main__':
    print(main())

Solution (Python):
def resolve():
    import sys
    from fractions import gcd
    input = sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    m=10**6+5
    chk=[0]*m
    for i in a:
      chk[i]+=1
    pw=1
    for i in range(2,m):
      cnt=0
      for j in range(i,m,i):
        cnt+=chk[j]
      if cnt>1:
        pw=0
        break
    g=a[0]
    for i in a[1:]:
      g=gcd(g,i)
    if pw==1:
      print('pairwise coprime')
    elif g==1:
      print('setwise coprime')
    else:
      print('not coprime')

if __name__ == '__main__':
    resolve()

Solution (Python):
from math import gcd


def main():
    input()  
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 1
    histogram = [0] * MAX_A
    for x in array:
        histogram[int(x)] += 1
    for divider in range(2, MAX_A):
        count = 0
        for counted in histogram[divider::divider]:
            count += counted
        if count > 1:
            break
    else:
        return 'pairwise coprime'
    gcd_now = 0
    for x in array:
        gcd_now = gcd(x, gcd_now)
    if gcd_now == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


if __name__ == '__main__':
    print(main())

Solution (Python):
from math import gcd


def main():
    input()  
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 2
    histgram = [0] * MAX_A
    for x in array:
        histgram[int(x)] += 1
    pairwise = True
    for divider in range(2, MAX_A):
        count = 0
        for counted in histgram[divider::divider]:
            count += counted
        if count > 1:
            pairwise = False
    if pairwise:
        return 'pairwise coprime'
    gcd_now = 0
    for x in array:
        gcd_now = gcd(x, gcd_now)
    if gcd_now == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


if __name__ == '__main__':
    print(main())

Solution (Python):
def sieve(n):
  is_prime = [True for _ in range(n+1)]
  is_prime[0] = False
  for i in range(2, n+1):
    if is_prime[i-1]:
      j = 2 * i
      while j <= n:
        is_prime[j-1] = False
        j += i
  table = [i for i in range(1, n+1) if is_prime[i-1]]
  return table

N = int(input())
A = list(map(int, input().split()))
Amax = max(A)
lis = [0]*(Amax+1)
for i in range(N):
  lis[A[i]] += 1
table = sieve(Amax)
setwise = False
for t in table:
  cnt = sum(lis[t::t])
  if cnt==N:
    print('not coprime')
    break
  if 2<=cnt<N:
    setwise=True
else:
  if setwise==True:
    print('setwise coprime')
  else:
    print('pairwise coprime')

Solution (Python):
def sieve(n):
  is_prime = [True for _ in range(n+1)]
  is_prime[0] = False
  for i in range(2, n+1):
    if is_prime[i-1]:
      j = 2 * i
      while j <= n:
        is_prime[j-1] = False
        j += i
  table = [i for i in range(1, n+1) if is_prime[i-1]]
  return table

N = int(input())
A = list(map(int, input().split()))
Amax = max(A)
lis = [0]*(Amax+1)
for i in range(N):
  lis[A[i]] += 1
table = sieve(Amax)
setwise = False
for t in table:
  cnt = sum(lis[t:Amax+1:t])
  if cnt==N:
    print('not coprime')
    break
  if 2<=cnt<N:
    setwise=True
else:
  if setwise==True:
    print('setwise coprime')
  else:
    print('pairwise coprime')

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

import math

primes = set()


def prime_factorization(n):
    global primes
    primess = set()
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            if i not in primess and i in primes:
                print("setwise coprime")
                exit()
            primes.add(i)
            primess.add(i)
    if n > 1:
        if n not in primess and n in primes:
            print("setwise coprime")
            exit()
        primess.add(n)
        primes.add(n)


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

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

    if a != 1:
        print("not coprime")
        return

    for i in range(N):
        prime_factorization(A[i])

    print("pairwise coprime")


if __name__ == '__main__':
    main()

Solution (Python):
import math
NOTCOM = "not coprime"
SETWISE = "setwise coprime"
PAIRWISE = "pairwise coprime"
MAX_A = 10 ** 6 + 5

def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = [0] * MAX_A
    for a in A:
        c[a] += 1
    pairwse = True
    for i in range(2, MAX_A):
        cnt = 0
        for j in range(i, MAX_A, i):
            cnt += c[j]
        if cnt > 1: pairwse = False
    if pairwse:
        return PAIRWISE
    
    allgcd = A[0]
    for a in A:
        allgcd = math.gcd(allgcd, a)
    if allgcd == 1: return SETWISE
    return NOTCOM

print(main())

Solution (Python):
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8, i8[:]), cache=True)
def main(N,A):
  Amax = np.max(A)
  lis = np.zeros(Amax+1, np.int64)
  for i in range(N):
    lis[A[i]] += 1
  setwise = False
  for t in range(2,Amax+1):
    cnt = np.sum(lis[t:Amax+1:t])
    if cnt==N:
      return 'not'
    if 2<=cnt<N:
      setwise=True
  if setwise==True:
    return 'setwise'
  return 'pairwise'

N = int(input())
A = np.array(list(map(int, input().split())))
print(main(N,A)+' coprime')

Solution (Python):
def resolve():
    import sys
    input = sys.stdin.readline
    n=int(input())
    a=sorted(list(map(int,input().split())))
    ma=a[-1]
    pn=[i for i in range(ma+1)]
    for i in range(2,ma//2+1):
      j=2
      while j*i<=ma:
        pn[j*i]=min(pn[j*i],i)
        j+=1
    chk=[0]*(ma+1)
    for i in a:
      if i==1:
        continue
      x=pn[i]
      chk[x]+=1
      while x!=i:
        while i%x==0:
          i//=x
        x=pn[i]
        chk[x]+=1
    ans=2
    for i in chk[2:]:
      if i==n:
        ans=0
        break
      if i>=2:
        ans=1
    if ans==2:
      print('pairwise coprime')
    elif ans==1:
      print('setwise coprime')
    else:
      print('not coprime')

if __name__ == '__main__':
    resolve()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N = getN()
A = getList()

pair = True
semi = True


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

now = A[0]
for i in A[1:]:
    now = math.gcd(now, i)
if now > 1:
    semi = False

for i in A:
    judge[i] += 1

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

if pair and semi:
    print('pairwise coprime')
elif semi:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
def prime(p):
    memo = set()
    for i in range(2,(int(p**0.5)+1)):
        while p%i==0:
            p //= i
            memo.add(i)
    if p != 1:
        memo.add(p)
    return memo

from math import gcd

N = int(input())

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

tmp_gcd = A[0]


for i in range(1,N):
    tmp_gcd = gcd(tmp_gcd, A[i])

if 1 < tmp_gcd:
    print('not coprime')
    exit()


servive_prime = set()
for a in A:
    now_prime = prime(a)
    ls,ln = len(servive_prime), len(now_prime)
    servive_prime.update(now_prime)
    if len(servive_prime) < ls + ln:
        print('setwise coprime')
        exit()

print('pairwise coprime')

Solution (Python):
def prime(p):
    memo = set()
    for i in range(2,(int(p**0.5)+1)):
        while p%i==0:
            p //= i
            memo.add(i)
    if p != 1:
        memo.add(p)
    return memo

from math import gcd

N = int(input())

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

tmp_gcd = A[0]

for i in range(1,N):
    tmp_gcd = gcd(tmp_gcd, A[i])

if 1 < tmp_gcd:
    print('not coprime')
    exit()

servive_prime = set()
for a in A:
    now_prime = prime(a)
    ls,ln = len(servive_prime), len(now_prime)
    servive_prime.update(now_prime)
    if len(servive_prime) < ls + ln:
        print('setwise coprime')
        exit()
print('pairwise coprime')

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

MAX = max(A)


AR = [0] * (MAX+1)
V = [False] * (MAX+1)
for i in range(N): AR[A[i]] += 1
pairwise, setwise = True, True


for i in range(2, MAX+1):
    if V[i]: continue
    cnt, j = 0, i
    while j < MAX+1:
        cnt += AR[j]
        V[j] = True
        j += i
    if cnt > 1: pairwise = False
    if cnt == len(A): setwise = False

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

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

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

from functools import reduce

import math

alls = reduce(math.gcd, A)

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

facts = [False] * (10 ** 6 + 1)

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

for a in A:
  cur = factorization(a)
  for f in cur:
    if f[0] != 1 and facts[f[0]]:
      print("setwise coprime")
      exit(0)
    else:
      facts[f[0]] = True
else:
  print("pairwise coprime")

Solution (Python):
M=10**6+1
f=lambda p: exit(print(['pairwise','setwise','not'][p]+' coprime'))
n,*l=map(int,open(0).read().split())
from math import *
g,C=0,[0]*M
for x in l:
  g=gcd(g,x)
  C[x]=1
if g>1: f(2)
if any(sum(C[i::i])>1 for i in range(2,M)): f(1)
f(0)

Solution (Python):
M=10**6+1
f=lambda p: exit(print(['pairwise','setwise','not'][p]+' coprime'))
n,*l=map(int,open(0).read().split())
from math import *
g,C=0,[0]*M
for x in l:
  g=gcd(g,x)
  C[x]=1
if g>1: f(2)
if any(sum(C[i::i])>1 for i in range(2,M)): f(1)
f(0)

Solution (Python):
import sys

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

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

count= [0] * (1000001)
setwise_gcd = A[0]
for i in range(0,N):
    count[A[i]]+= 1
    setwise_gcd = gcd(setwise_gcd, A[i])


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

for i in range(2,1000001):
    divided_count = count[i]
    now_number = 2 * i
    while(now_number<1000001):
        divided_count+= count[now_number]
        now_number+= i
    if(divided_count >= 2):
        print("setwise coprime")
        exit(0)
print("pairwise coprime")

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

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))

    pairwise = True
    used = [False] * (max(A) + 1)
    
    
    for a in A:
        for i in range(2, int(a ** 0.5) + 1):
            if a % i == 0:
                if used[i]:
                    pairwise = False
                else:
                    used[i] = True
                    while a % i == 0:
                        a //= i
        if a != 1:
            if used[a]:
                pairwise = False
                break
            else:
                used[a] = True

    
    g = reduce(gcd, A)

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


if __name__ == '__main__':
    main()

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

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    used = [False] * (max(A) + 1)
    pairwise = True
    for a in A:
        for i in range(2, int(a ** 0.5) + 1):
            if a % i == 0:
                if used[i]:
                    pairwise = False
                else:
                    used[i] = True
                    while a % i == 0:
                        a //= i
        if a != 1:
            if used[a]:
                pairwise = False
                break
            else:
                used[a] = True


    g = reduce(gcd, A)

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


if __name__ == '__main__':
    main()

Solution (Python):
from math import gcd

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

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1
from collections import Counter

def createPrimeList(N):
    isPrime = [True] * (N + 1)
    isPrime[0] = False
    isPrime[1] = False
    smallestPrime = [1] * (N + 1)
    for i in range(2, N + 1):
        if not isPrime[i]:
            continue
        for p in range(i * 2, N, i):
            if isPrime[p]:
                smallestPrime[p] = i
            isPrime[p] = False
    return smallestPrime

from collections import Counter
smallestPrime = createPrimeList(max(A) + 10)
def primeFactorization(N):
    ret = Counter()
    while N > 1:
        p = smallestPrime[N]
        if p == 1:
            ret[N] += 1
            break
        ret[p] += 1
        N //= p
    return ret

def isPairwise(A):
    P = Counter()
    for a in A:
        for p in primeFactorization(a):
            if P[p] >= 1:
                return False
            P[p] += 1
    return True

if not isSetwise(A):
    print('not coprime')
    exit()

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

Solution (Python):
import numpy as np
from numba import njit

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6

nums = np.zeros(MAX + 1, np.int64)
for e in a:
    nums[e] += 1


@njit
def solve(nums):
    mx = 0
    for i in range(2, MAX + 1):
        cnt = nums[i::i].sum()
        mx = max(mx, cnt)

    return mx


mx = solve(nums)

if nums[1] == n:
    ans = "pairwise"
elif mx == n:
    ans = "not"
elif mx == 1:
    ans = "pairwise"
else:
    ans = "setwise"

ans += " coprime"

print(ans)

Solution (Python):
import numpy as np
from numba import njit

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6

nums = np.zeros(MAX + 1, np.int64)
for e in a:
    nums[e] += 1


@njit
def solve(nums):
    mx = 0
    for i in range(2, MAX + 1):
        cnt = nums[i::i].sum()
        mx = max(mx, cnt)

    return mx


mx = solve(nums)

if nums[1] == n:
    ans = "pairwise coprime"
elif mx == n:
    ans = "not coprime"
elif mx == 1:
    ans = "pairwise coprime"
else:
    ans = "setwise coprime"

print(ans)

Solution (Python):

import math
from functools import reduce

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


n = 10**6
minfac = list(range(n+1))
for i in range(2, int(n**0.5) + 1):
    if minfac[i] < i:
        continue
    for j in range(i, n + 1, i):
        if minfac[j] > i:
            minfac[j] = i

"""nの素因数の種類を求める"""
def osa_k(n):
    temp = set()
    while n > 1:
        temp.add(minfac[n])
        n = n//minfac[n]
    return temp


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

check = [0]*(10**6)
flag = 0
for a in A:
    for i in osa_k(a):
        if check[i]:
            flag = 1
        else:
            check[i] = 1
    if flag:
        break
        
if gcd_list(A) > 1:
    print("not coprime")
elif flag:
    print("setwise coprime")
else:
    print("pairwise coprime")