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.



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Accepted

Solution code:
from math import gcd

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


gcd_num = a[0]
for ai in a[1:]:
    gcd_num = gcd(gcd_num,ai)

if(gcd_num > 1):
    print('not coprime')
    exit()

def sieve(n):
    if( n <= 1):
        return []
    elif(n==2):
        return [2]

    primes = [2]
    len_list = (n+1)//2
    len_sqrt = int(len_list**0.5) + 1
    flags = [True] * len_list
    flags[0] = False
    for i in range(len_sqrt):
        if(flags[i]):
            start = ((i*2+1)**2)//2
            for j in range( start, len_list, i*2+1):
                flags[j] = False
    return [2] + [i*2+1 for i in range(len_list) if flags[i]]

p_6 = set(sieve(10**6))
p_3 = sieve(10**3)

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

for ai in a:
    if(ai==1):
        continue
    divs = []
    for p in p_3:
        if(ai%p==0):
            divs.append(p)
            while(ai%p==0):
                ai//=p
    if(ai != 1):
        divs.append(ai)

    for di in divs:
        if(use[di] != 0):
            print('setwise coprime')
            exit()
        use[di] = 1

print('pairwise coprime')

Submission status: Accepted

Solution code:
def examA():
    D,T,S = LI()
    if (D-1)//S<T:
        ans = "Yes"
    else:
        ans = "No"
    print(ans)
    return

def examB():
    S = SI()
    T = SI()
    s = len(S)
    t = len(T)
    ans = t
    for i in range(s-t+1):
        cnt = 0
        for j in range(t):
            if S[i+j]!=T[j]:
                cnt += 1
        ans = min(ans,cnt)

    print(ans)
    return

def examC():
    N = I()
    A = LI()
    S = sum(A)
    cnt = 0
    for a in A:
        cnt += (S-a)*a
        cnt %= mod
    ans = cnt * pow(2,mod-2,mod) % mod
    print(ans)
    return

def examD():
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            # 正==子: 根の頂点番号 / 負==根: 連結頂点数

        def reset(self):
            self.parent = [-1] * len(self.parent)

        def find(self, x):
            # 要素xが属するグループの根を返す
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            # 要素xが属するグループと要素yが属するグループとを併合する
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            # 要素x, yが同じグループに属するかどうかを返す
            return self.find(x) == self.find(y)

        def size(self, x):
            # 要素xが属するグループのサイズ（要素数）を返す
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            # 要素の根をリストで返す
            return self.parent[x] < 0

        def roots(self):
            # すべての根の要素をリストで返す
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            # 要素xが属するグループに属する要素をリストで返す
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            # グループの数を返す
            return len(self.roots())

        def all_group_members(self):
            # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
            return {r: self.members(r) for r in self.roots()}
    N, M = LI()
    uf = UnionFind(N)
    for _ in range(M):
        a, b = LI()
        a -= 1; b -= 1
        uf.unite(a,b)
    cnt = 0
    for i in range(N):
        cnt = max(cnt,uf.size(i))

    ans = cnt
    print(ans)
    return

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

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

    N = I()
    A = LI()
    cur = A[0]
    for i in range(1,N):
        cur = gcd(cur,A[i])
        if cur==1:
            break
    if cur!=1:
        print("not coprime")
        return

    n = max(A)

    P = primes(n)

    #print(P)

    D = [False]*(n+1)
    for a in A:
        if a==1:
            continue
        if D[a]:
            print("setwise coprime")
            return
        D[a] = True

    for p in P:
        flag = False
        cur = 1
        while (cur * p <= n):
            if D[cur*p]:
                if flag:
                    print("setwise coprime")
                    return
                flag = True

            cur += 1

    print("pairwise coprime")
    return

def examF():

    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
from collections import Counter


def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)


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

m = max(a)
is_prime = [True] * (m + 1)
cnt_a = [0] * (m + 1)
for i in range(n):
    cnt_a[a[i]] += 1

is_pairwise_coprime = True
for i in range(2, m // 2 + 1):
    if is_prime[i]:
        cnt = cnt_a[i]
        for j in range(2, m // i + 1):
            cnt += cnt_a[i * j]
            is_prime[i * j] = False
        if cnt > 1:
            is_pairwise_coprime = False
            break

gcd_all = a[0]
for i in range(1, n):
    gcd_all = GCD(gcd_all, a[i])
is_setwise_coprime = gcd_all == 1

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

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
def osa_k(n=10**6):
  p=list(range(n+1))
  for i in range(2,int(n**.5)):
    if p[i]<i:continue
    for j in range(i*i,n+1,i):
      if p[j]==j:p[j]=i
  return p
def fact_o(n):
  a=[]
  f=0
  while n>1:
    if f!=p[n]:ans[p[n]]+=1
    f=p[n]
    n//=p[n]
  return 0
p=osa_k()
n=int(input())
a=list(map(int,input().split()))
ans=[0]*(10**6+1)
for i in a:
  fact_o(i)
if max(ans)<=1:print('pairwise coprime')
elif reduce(gcd,a)==1:print('setwise coprime')
else:print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd


# def sieve(n):
#     is_prime = [1 for _ in range(n + 1)]
#     is_prime[0] = 0
#     is_prime[1] = 0

#     for i in range(2, n + 1):
#         if is_prime[i]:
#             j = i + i
#             while j <= n:
#                 is_prime[j] = 0
#                 j += i

#     return is_prime


def factorization(n):
    from collections import Counter
    arr = Counter()
    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[i] = cnt

    if temp != 1:
        arr[temp] = 1

    if len(arr.keys()) == 0 and n != 1:
        arr[n] = 1

    return arr


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

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


# pairwise
M = 10 ** 6
sieve = [0] * (M + 1)
for a in A:
    if sieve[a] == 1:
        isPairwise = False
        break
    else:
        arr = factorization(a)
        for p in arr.keys():
            np = p
            while np <= M:
                sieve[np] = 1
                np += p
else:
    isPairwise = True

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

Submission status: Accepted

Solution code:
import math


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


def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1:
            continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1:
                return 0
            t <<= 1
    return 1


def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        def f(x): return (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)


def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k:
            ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1:
        ret[n] = 1
    if rhoFlg:
        ret = {x: ret[x] for x in sorted(ret)}
    return ret


N = int(input())
A = [int(i) for i in input().split()]

a = A[0]
p = set(primeFactor(A[0]).keys())
flg = False

for i in range(1, N):
    a = math.gcd(a, A[i])
    for x in primeFactor(A[i]):
        if x in p:
            flg = True
        else:
            p.add(x)


if a >= 2:
    print('not coprime')
elif flg:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce

def factors(n):
    f=set()
    i=2
    while i*i<=n:
        if n%i==0:
            n//=i
            f.add(i)
        else:
            i+=1
    if n>1:
        f.add(n)
    return f

def list_gcd(A:list):
    return reduce(gcd,A)

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

A_gcd=list_gcd(A)

p=set()
coprime=False
for a in A:
    f=factors(a)
    if len(f&p)>0:
        coprime=True
        break
    else:
        p|=f

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

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.buffer.readline
from math import gcd

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

# Mまでの素数全列挙(エラトステネスの篩)
def primes(M):
    B = set(A)
    if (1 in B and len(A) != len(B) + A.count(1)-1) or (not 1 in B and len(A) != len(B)):
        return False
    ok = True
    is_prime = [-1 for _ in range(M+1)]
    for m in range(2, M+1):
        if is_prime[m] == -1:
            is_prime[m] = 1
            cnt = 0
            if m in B: cnt += 1
            l = 2
            while m*l <= M:
                if m*l in B:
                    cnt += 1
                is_prime[m*l] = 0
                l += 1
            if cnt > 1:
                ok = False
                break
    return ok

def check():
    k = A[0]
    for a in A:
        k = gcd(a, k)
    return k == 1

if primes(10**6):
    ans = "pairwise coprime"
elif check():
    ans = "setwise coprime"
else:
    ans = "not coprime"
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))

import math
#リスト l の最大公約数
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = math.gcd(a,l[i])
        if a == 1:
            return 1
    return a

res = gcdlist(lst1)
if res != 1:
    print("not coprime")
    exit()

#nまでの素数のリスト
def eratosthenes(n): #必要な分だけ用意
    if n < 2: #1は素数ではない
        return []
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p: #limit=root(n)
            return prime + data #root(n)まで判定すれば、残りは全て素数であると言える
        prime.append(p)
        data = [e for e in data if e % p != 0] #エラトステネスのふるい
"""素因数分解"""
def get_prime(n):
    b = 2
    fct = []
    while b*b <= n:
        while n % b == 0:
            n //= b
            if not b in fct:
                fct.append(b)
        b += 1
    if n > 1:
        fct.append(n)
    return fct
prime = eratosthenes(10**6)
prime_arr = [0]*10**6
for i in prime:
    prime_arr[i] = 1

for i in lst1:
    if prime_arr[i] == 1:
        prime_arr[i] = -1
    elif prime_arr[i] == -1:
        print("setwise coprime")
        exit()
    else:
        ret = get_prime(i)
        for i in ret:
            if prime_arr[i] == 1:
                prime_arr[i] = -1
            else:
                print("setwise coprime")
                exit()

print("pairwise coprime")

Submission status: Accepted

Solution code:
def main():

    from math import gcd
    import sys
    input = sys.stdin.buffer.readline
    n = int(input())
    alst = list(map(int, input().split()))
    aa = alst[0]
    for a in alst:
        aa = gcd(aa, a)
    if aa != 1:
        print("not coprime")
        exit()
    
    max_n = 10 ** 3 + 1
    div = [True for _ in range(max_n)]
    div[0] = div[1] = False
    prime_lst = []
    for i in range(2, int(max_n ** 0.5 + 1)):
        if not div[i]:
            continue
        prime_lst.append(i)
        for j in range(i * 2, max_n, i):
            div[j] = False
    tf = [False for _ in range(max_n)]
    for i in range(n):
        for pr in prime_lst:
            if alst[i] % pr == 0:
                if tf[pr]:
                    print("setwise coprime")
                    exit()
                while alst[i] % pr == 0:
                    alst[i] //= pr
                    tf[pr] = True
    alst.sort()
    bef = 1
    for a in alst:
        if a == 1:
            continue
        elif a == bef:
            print("setwise coprime")
            exit()
        bef = a
    print("pairwise coprime")
main()

Submission status: Accepted

Solution code:
from itertools import groupby

class Osa_k:
    def __init__(self, n_max):
        self.min_factor = min_factor = list(range(n_max+1))
        for i in range(2, int(n_max**0.5)+1):
            if min_factor[i] == i:
                for j in range(i*i, n_max+1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1  # 最悪ケースでは速くなる
        res = [2] * n_twoes
        n >>= n_twoes
        while n > 1:
            p = min_factor[n]
            res.append(p)
            n //= p
        return res

def main():
    N = int(input())
    A = list(map(int, input().split()))
    osa_k = Osa_k(1010101)
    Factors = [osa_k(a) for a in A]
    factors = Factors[0]
    st0 = set(factors)  # 0 になれば setwize
    st1 = set(factors)  # 重複しなければ pairwise
    pairwise = True
    for factors in Factors[1:]:
        st = []
        for f, _ in groupby(factors):
            if f in st1:
                pairwise = False
            else:
                st1.add(f)
            st.append(f)
        st0 &= set(st)
    if pairwise:
        print("pairwise coprime")
    elif not st0:
        print("setwise coprime")
    else:
        print("not coprime")

main()

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
from collections import Counter

class Factorize:
    def __init__(self):
        self.primes = Counter()

    def add_target(self, n):
        for i in range(2, int(n**0.5)+1):
            while n%i==0:
                self.primes[i] += 1
                n //= i
            if not n:
                break
        if n>1:
            self.primes[n] += 1
    
    def get_result(self):
        return dict(self.primes)

N = int(input())
*A, = map(int, input().split())
def f():
    cnt = Counter()
    for i in A:
        ins = Factorize()
        ins.add_target(i)
        res = ins.get_result()
        for j in res.keys():
            cnt[j] += 1
            if cnt[j] >= 2:
                return False
    return True

cond1 = f()
cond2 = (reduce(gcd, A)==1)

if cond1:
    print("pairwise coprime")
elif cond2:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from math import *

def gcd2(array):
    temp = array[0]
    for a in array[1:]:
        temp = gcd(temp, a)
    return temp

def prime_factors(n):       # 戻り値はiterable type
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i             # whileループを進めるごとにイテレータに値を貯め続ける
    if n > 1:
        yield n

N = int(input())
A = list(map(int, input().split()))
f1 = False
if gcd2(A) == 1:
    f1 = True
A.sort()
M = A[-1]
P = set()
f2 = True
for a in A:
    Q = set(prime_factors(a))
    if P & Q:
        f2 = False
        break
    P |= Q
if f2:
    print("pairwise coprime")
elif f1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

def prime_factor(x) :
  ret = dict()
  if x % 2 == 0 :
    ret[2] = 0
    while x % 2 == 0 :
      x //= 2
      ret[2] += 1
          
  i = 3
  while i * i <= x :
    if x % i == 0 :
      ret[i] = 0
      
      while x % i == 0 :
        x //= i
        ret[i] += 1
    i += 2
      
  if x != 1 :
    ret[x] = 1
  
  return ret

def pairwise() :
  done = set()
  for a in A :
    for k in prime_factor(a).keys() :
      if not k in done :
        done.add(k)
      else :
        return False
  return True
    
def setwise() :
  done = set(prime_factor(A[0]).keys())
  for a in A[1:] :
    done &= set(prime_factor(a).keys())
    if len(done) == 0 :
      return True
  return False
  
if pairwise() :
  print('pairwise coprime')
elif setwise() :
  print('setwise coprime')
else :
  print('not coprime')

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def enum_primes(n):
    flag_num = (n + 1) // 2
    prime_flag = [True] * flag_num

    for num in range(3, int(n ** 0.5) + 1, 2):
        idx = (num - 1) // 2 - 1
        if prime_flag[idx]:
            for j in range(idx + num, flag_num, num):
                prime_flag[j] = False

    primes = [2]
    temp = [(i + 1) * 2 + 1 for i in range(flag_num) if prime_flag[i]]
    primes.extend(temp)

    return primes


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    primes = enum_primes(10 ** 6 + 1)

    def judge():
        seq = [False] * (10 ** 6 + 1)
        A.sort()

        for x in A:
            if x == 1:
                continue
            if seq[x]:
                return False
            seq[x] = True

        for prime in primes:
            cnt = 0
            for i in range(prime, 10 ** 6 + 1, prime):
                if seq[i]:
                    cnt += 1
            if cnt > 1:
                return False
        return True

    if judge():
        print("pairwise coprime")
    else:
        from math import gcd
        cur = A[0]
        for x in A[1:]:
            cur = gcd(cur, x)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd, sqrt

def Divisor_Set(n):
    s = set()
    for i in range(1, int(sqrt(n))+2):
        if n%i == 0:
            s.add(i)
            s.add(n//i)
    return s

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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

def solve():
      input = sys.stdin.readline
      N = int(input())
      A = [int(a) for a in input().split()]
      L = max(A)
      count = [0] * (L + 1)
      isPrime = [False] * (L + 1)
      gcdA = A[0]
      for a in A[1:]:
            gcdA = gcd(gcdA, a)
            count[a] += 1
      if gcdA > 1:
            print("not coprime")
            return 0
      
      for i in range(2, L + 1):
            if not isPrime[i]:
                  c = 0
                  k = i
                  while k <= L:
                        isPrime[i] = True
                        c += count[k]
                        k += i
                  if c > 1:
                        print("setwise coprime")
                        return 0
      print("pairwise coprime")
      return 0

if __name__ == "__main__":
      solve()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


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


def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1


def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)


def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret


def solve():
    n = getN()
    nums = getList()
    d = defaultdict(int)
    for num in nums:
        res = primeFactor(num)
        for k in res.keys():
            d[k] += 1

    dup = 0
    over = 0
    for dv in d.values():
        if dv == n:
            over += 1
            break
        if dv > 1:
            dup += 1

    if over:
        print("not coprime")
        return
    if dup:
        print("setwise coprime")
        return

    print("pairwise coprime")
    return
    # print(primeFactor(100))
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
from collections import Counter
from itertools import chain


# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            while n % i == 0:
                n //= i
            yield i
    if n > 1:
        yield n


def solve(A):
    d = reduce(gcd, A)
    if d != 1:
        return 'not coprime'

    A.sort()

    s = set()
    for a in A:
        for p in prime_factors(a):
            if p in s:
                return 'setwise coprime'
            else:
                s.add(p)

    return 'pairwise coprime'


if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))

    print(solve(A))

Submission status: Accepted

Solution code:
# by the authority of GOD   author: manhar singh sachdev #

import os,sys
from io import BytesIO, IOBase
from collections import Counter

def main():
    n = int(input())
    arr = list(map(int,input().split()))
    x = max(arr)
    sieve = [[] for _ in range(x+1)]
    lst = [0]*(x+1)
    for i in range(2,x+1):
        if lst[i]:
            continue
        lst[i] = 1
        sieve[i].append(i)
        y = 2*i
        while y <= x:
            lst[y] = 1
            sieve[y].append(i)
            y += i
    pr = Counter()
    for i in arr:
        for x in sieve[i]:
            pr[x] += 1
    fl = 0
    fl1 = 0
    for p in pr:
        if pr[p] > 1:
            fl = 1
        if pr[p] == n:
            fl1 = 1
    if not fl:
        print('pairwise coprime')
    elif not fl1:
        print('setwise coprime')
    else:
        print('not coprime')



#Fast IO Region
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()