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:
import math
n = int(input())
a = [int(i) for i in input().split()]

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

for i in range(n):
    #if chk[a[i]] == 1 and a[i] >= 2:
    #    print("not coprime")
    #    exit()
    chk[a[i]] += 1

flag = True

for i in range(2,10**6+1):
    #tmp = i
    kake = 1
    num = 0
    #print(i)
    while i * kake <= 10**6:
        if chk[i*kake] >= 2:
            flag = False
            break
        #print(i)
        if chk[i*kake] == 1:
            if num == 1:
                flag = False
                break
            num = 1
            #break
        kake += 1
gcd_num = math.gcd(a[0],a[1])
        
for i in range(n-2):
    gcd_num = math.gcd(gcd_num,a[i+2])
    
if flag == True:
    print("pairwise coprime")
elif gcd_num == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd
import sys
sys.setrecursionlimit(1000000)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    tmp = gcd(A[0],A[1])
    set_A = set(A)
    for i in range(2,N):
        tmp = gcd(tmp, A[i])

    if tmp != 1:
        print('not coprime')
        exit()
    max_A = max(A)
    ans = [False] * (max_A + 1)
    flag = True
    def divisor(n):
        ass = []
        for i in range(1,int(n**0.5)+1):
            if n%i == 0:
                ass.append(i)
                if ans[i]:
                    return False
                if i != 1:
                    ans[i] = True
                if i**2 == n:
                    continue
                if ans[n//i]:
                    return False
                ans[n//i] = True
                ass.append(n//i)
        if n != 1:
            ans[n] = True
        return True #sortされていない
    for a in A:
        if not divisor(a):
            flag = False
            break

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






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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
#pairwise coprime どの2つをとっても共通素因数がない
#setwise coprime すべてに共通する素因数が存在しない
#左から見ていって、素因数の個数をカウントしていく…？
#setwise はエラトステネスの篩を再帰的に行う
#pairwise はそもそも、maxまでの素数の個数までしか存在し得ない
N = int(input())
A_old = [int(hoge) for hoge in input().split()]
A = [a for a in A_old if a != 1]
Pairwise = False
Setwise = False
SOSUU = [0 for _ in range(10**6+10)]
A.sort()
Fail = False
G = A_old[0]
for a in A_old:
    G = math.gcd(G,a)
if G != 1:
    print("not coprime")
    exit()

if len(A) <= 80000:
    for a in A:
        Fact = factorization(a)
        for f in Fact:
            if f[0]==1:continue
            if SOSUU[f[0]] > 0:
                Fail = True
                break
            else:
                SOSUU[f[0]] += 1
        if Fail:
            break
    if not Fail:
        Pairwise = True

if Pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Accepted

Solution code:
import math
def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def soinnsuu(x):
    s = set()
    for i in primes:
        if i > int(math.sqrt(x)):
            break
        elif x % i == 0:
            while x % i == 0:
                x //= i
            s.add(i)
    if not x == 1:
        s.add(x)
    return s
from math import gcd
n = int(input())
a = list(map(int, input().split()))
g = 0
for i in range(n):
    g = gcd(g, a[i])
primes = prime_numbers(2000000)
cur = soinnsuu(a[0])
f = False
for i in range(1, n):
    s2 = soinnsuu(a[i])
    if len(cur & s2) >= 1:
        f = True
        break
    cur |= s2
if not f:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

def max_gcd_pair(S):
    # Assumption 1: S is the list of numbers
    # Assumption 2: There are no duplicates in S

    s = set(S)
    m = max(S)

    res = 0
    i = m

    while(i > 0):
        a = i
        cnt = 0
        while (a<=m): # a maxed at max of the list
            if a in s:   
               cnt += 1
            a += i

        if cnt >= 2:  # we have found the result
            res = i
            break

        i = i -1 

    return res

n = int(input())
a = [int(x) for x in input().split()]

from collections import Counter

c = Counter(a)
flag = 1
for i in a:
    if c[i] > 1 and i != 1:
        flag = 0
if flag:
    if max_gcd_pair(a) <= 1:
        print('pairwise coprime')
        sys.exit()

import math
from functools import reduce

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

if gcd(*a) == 1:
    print('setwise coprime')
    sys.exit()

else:
    print('not coprime')

Submission status: Accepted

Solution code:
import math
def makePrimes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

primes = makePrimes(10**6)
prime_set = set()
def prime_factorization(n):
    tmp = n
    ret = True
    m = int(-(-n**0.5//1))+1
    for p in primes:
        if m < p:
            break
        if tmp%p==0:
            if p in prime_set:
                ret = False
            while tmp%p==0:
                tmp//=p
            prime_set.add(p)
    if tmp!=1:
        if tmp in prime_set:
                ret = False
        prime_set.add(tmp)
    return ret

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

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

if pairwize:
    print("pairwise coprime")
elif gcd == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
# coding: utf-8
#import numpy as np
import re
import math
from collections import defaultdict,deque,Counter
from fractions import Fraction
import bisect
import itertools
from itertools import accumulate
from copy import deepcopy

import heapq
import random
import time
import os
import sys
from functools import lru_cache,reduce
readline=sys.stdin.readline
sys.setrecursionlimit(100000)
alp="abcdefghijklmnopqrstuvwxyz"
numbers="0123456789"
mod=int(10**9+7)
inf=int(10**19)
class Set():
    def __init__(self,A=[]):
        self.heap=[]
        self.dic=defaultdict(bool)
        self.size=0
        for a in A:self.add(a)
    
    def __str__(self):
        return str(self.heap)
    
    def add(self,x):
        if not self.find(x):
            heapq.heappush(self.heap,x)
            self.dic[x]=True
            self.size+=1

    def remove(self,x):
        if self.find(x):
            self.dic[x]=False
            self.size-=1

    def find(self,x):
        return self.dic[x]
    
    def top(self):
        while self.heap and self.dic[self.heap[0]]==False:
            heapq.heappop(self.heap)
        if self.heap:return self.heap[0]
        else:return None

    def pop(self):
        ret=None
        if self.heap:
            ret=self.top()
            self.remove(ret)
        return ret
class multiset():
    def __init__(self,A=[]):
        self.heap=[]
        self.dic=defaultdict(int)
        self.size=0
        for a in A:self.add(a)
    
    def __str__(self):
        return str(self.heap)
    
    def add(self,x):
        heapq.heappush(self.heap,x)
        self.dic[x]+=1
        self.size+=1

    def remove(self,x):
        if self.dic[x]>0:
            self.dic[x]-=1
            self.size-=1
    
    def count(self,x):
        return self.dic[x]

    def find(self,x):
        return self.dic[x]>0
    
    def top(self):
        while self.heap and self.dic[self.heap[0]]==0:
            heapq.heappop(self.heap)
        if self.heap:return self.heap[0]
        else:return None

    def pop(self):
        ret=None
        if self.heap:
            ret=self.top()
            self.remove(ret)
        return ret
class Edge():
    def __init__(self,x,y,val=1):
        self.x=x
        self.y=y
        self.val=val
class Point():
    def __init__(self,y,x):
        self.x=x
        self.y=y
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def yn(b):print("yes" if b else "no")
def Yn(b):print("Yes" if b else "No")
def YN(b):print("YES" if b else "NO")
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n):
    if n==0:return []
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    ret=[]
    for a in range(n+1):
        if(A[a]):ret.append(a)
    return ret
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(b,t,f):return t if b else f
def factorize(n):
    b = 2
    ret=defaultdict(int)
    while b * b <= n:
        while n % b == 0:
            n //= b
            ret[b]+=1
        b+=1
    if n > 1:ret[n]+=1
    return ret
def inputintlist(row=1): 
    if row==1:
        ret=list(map(int,input().split()))
    else:
        ret=[None]*row
        for a in range(row):
            ret[a]=int(input())
    return ret
def inputfloatlist(row=1): 
    if row==1:
        ret=list(map(float,input().split()))
    else:
        ret=[None]*row
        for a in range(row):
            ret[a]=float(input())
    return ret
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.val))
    return ret
def dijkstra(edges,V,start):
    from queue import PriorityQueue
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.val,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])#[cost,x]
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.val)#x→yが複数ある場合のためにmin()する
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
    return mincost
def bellemanford(edges,V,start):
    mincost=[inf]*V
    mincost[start]=0
    for _ in range(V):
        for edge in edges:
            if mincost[edge.x]==inf:continue
            mincost[edge.y]=min(mincost[edge.y],mincost[edge.x]+edge.val)
    return mincost
def getmd(x1,y1,x2,y2):return abs(x1-x2)+abs(y1-y2)
def geted(x1,y1,x2,y2):return math.sqrt((x1-x2)**2+(y1-y2)**2)
class fordfulkerson():
    def __init__(self,edges,V,s,t):
        self.V=V
        self.used=[False]*V
        self.G=[[] for a in range(V)]
        self.s=s
        self.t=t
        for edge in edges:
            self.G[edge.x].append({"x":edge.x,"y":edge.y,"cap":edge.val,"rev":len(self.G[edge.y])})
            self.G[edge.y].append({"x":edge.y,"y":edge.x,"cap":0,"rev":len(self.G[edge.x])-1})
    def dfs(self,v,t,f=inf):
        if v==t:return f
        self.used[v]=True
        for a in range(len(self.G[v])):
            x=self.G[v][a]["x"]
            y=self.G[v][a]["y"]
            cap=self.G[v][a]["cap"]
            rev=self.G[y][self.G[x][a]["rev"]]
            if self.used[y] or cap==0:continue
            f2=self.dfs(y,t,min(f,cap))
            if f2>0:
                self.G[v][a]["cap"]-=f2
                rev["cap"]+=f2
                return f2
        return 0
    def maxflow(self):
        flow=0
        while True:
            self.used=[False]*V
            zouka=self.dfs(self.s,self.t)
            if zouka==0:break
            flow+=zouka
        return flow
def zipsort(*args):
    ziplist=sorted(zip(*args))
    for a in range(len(args)):
        for b in range(len(ziplist)):
            args[a][b]=ziplist[b][a]
def zipreverse(*args):
    ziplist=list(zip(*args))
    rev=[]
    for a in range(len(ziplist)-1,-1,-1):
        rev.append(ziplist[a])
    for a in range(len(args)):
        for b in range(len(rev)):
            args[a][b]=rev[b][a]

def to10(A):
    ret=0
    for a in range(len(A)-1,-1,-1):
        ret+=X[a]*2**(N-1-a)
    return ret
######################################################################################################
N=int(input())
A=inputintlist()
s=defaultdict(bool)
f=True

for a in A:
    for b in factorize(a):
        if s[b]:
            f=False
        else:
            s[b]=True
    if not f:break
if f:
    print("pairwise coprime")
else:
    G=A[0]
    for a in A:
        G=math.gcd(a,G)
    if G==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

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

from math import gcd
import sys

divisors = [False]*10**6
def make_divisors(n):
    i = 1
    while i*i <= n:
        if n % i == 0:
            if not divisors[i-1]:
                divisors[i-1] = True
            elif i != 1:
                return -1
            if i != n // i:
                if not divisors[n//i-1]:
                    divisors[n//i-1] = True
                else:
                    return -1
        i += 1
    return 1

GCD = A[0]
for i in range(1,N):
    GCD = gcd(A[i], GCD)
if GCD != 1:
    print("not coprime")
else:
    for a in A:
        if make_divisors(a) < 0:
            print("setwise coprime")
            sys.exit()
    print("pairwise coprime")

Submission status: Accepted

Solution code:

from math import gcd
from functools import reduce


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

lim = 10 ** 6 + 10
is_prime = [True] * (lim + 1)
is_prime[0] = False
is_prime[1] = False
min_factor = list(range(lim + 1))

for i in range(2, lim + 1):
    if is_prime[i]:
        for j in range(2 * i, lim + 1, i):
            is_prime[j] = False
            min_factor[j] = i

pairwise = True
appeared = set()
for v in X:
    while v > 1:
        div = min_factor[v]
        if div in appeared:
            pairwise = False
            break

        appeared.add(div)
        while v % div == 0:
            v //= div

if pairwise:
    print("pairwise coprime")
elif reduce(gcd, X) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
from functools import reduce
N = int(input())
A = list(map(int,input().split()))

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

def sieve_Eratosthenes(n):
    f = [True]*(n+1)
    f[0] = False
    f[1] = False
    m = int(n**0.5+1)
    for i in range(2,m):
        if f[i]:
            for j in range(i*i,n+1, i):
                f[j] = False
    return f

def getPrimeLists(n):
    table = sieve_Eratosthenes(n)
    return [x for x in range(2,n+1) if table[x]]

def primeFactorization(n):
    res = defaultdict(int)
    m = int(n**0.5)
    for i in range(2,m+1):
        while n % i == 0:
            n = n//i
            res[i] += 1
    if n > 1:
        res[n] = 1
    return res

table = [0] * (10**6+10)
f = False
for a in A:
    pf = primeFactorization(a).keys()
    for p in pf:
        if table[p] > 0:
            f = True
        table[p] += 1
    if f:
        break
else:
    print('pairwise coprime')
    exit()

allgcd = reduce(gcd, A)
if allgcd == 1:
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Accepted

Solution code:
from collections import defaultdict


def get_prime_factors(x):
    out = set()
    if x < 1:
        return out
    while not x%2:
        out.add(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.add(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.add(x)
    return out


def main():
    n = int(input())
    a = list(map(int, input().split()))
    df = defaultdict(lambda : 0)
    for ai in a:
        primes = get_prime_factors(ai)
        for prime in primes:
            df[prime] += 1
    if df.values():
        val = max(df.values())
        if val == 1:
            print("pairwise coprime")
        elif val == n:
            print("not coprime")
        else:
            print("setwise coprime")
    else:
        print("pairwise coprime")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd

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

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

# すべてのi,jについてgcd(ai, aj) = 1 の判定 
# anygcd1
# 素因数分解してsetで管理、最後まで存在しなければTrue

# gcd(a1,,,an) = 1 の判定
# allgcd1
# やるだけ？

anygcd1 = True

pset = set()
for a in A:
  pf = prime_factorize(a)
  if any(p in pset for p in pf):
    anygcd1 = False
    break
  pset |= pf

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

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

Submission status: Accepted

Solution code:
# E - Coprime
from math import gcd

N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
MAX = 10**6
L = [0]*(MAX+1)

def prime(x):
    global L
    p = 2
    while x>1:
        if L[x]==1:
            return False
        if x%p==0:
            while x%p==0:
                x //= p
            tmp = p
            while tmp<=MAX:
                L[tmp] = 1
                tmp += p
        p = p+1 if p*p<x else x   
    return True
        
G = A[0]
pairwise = True
_ = prime(A[0])

for i in range(1,N):
    a = A[i]
    if pairwise:
        pairwise = prime(a)
    G = gcd(G,a)

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

Submission status: Accepted

Solution code:
import os
import heapq
import sys,threading
import math as mt
import bisect
import operator
from collections import defaultdict
sys.setrecursionlimit(10**5)
from io import BytesIO, IOBase
def gcd(a,b):
    if b==0:

        return a
    else:
        return gcd(b,a%b)
def power(x, p,m):
    res = 1
    while p:
        if p & 1:
            res = (res * x) % m
        x = (x * x) % m
        p >>= 1
    return res
def inar():
    return [int(k) for k in input().split()]
dic={}
def lcm(num1,num2):
    return (num1*num2)//gcd(num1,num2)

# Python3 program to find prime factorization
# of a number n in O(Log n) time with
# precomputation allowed.


MAXN = 10**6+1

# stores smallest prime factor for
# every number
spf = [0 for i in range(MAXN)]


# Calculating SPF (Smallest Prime Factor)
# for every number till MAXN.
# Time Complexity : O(nloglogn)
def sieve():
    spf[1] = 1
    for i in range(2, MAXN):
        spf[i] = i

    # separately marking spf for
    # every even number as 2
    for i in range(4, MAXN, 2):
        spf[i] = 2

    for i in range(3, mt.ceil(mt.sqrt(MAXN))):

        # checking if i is prime
        if (spf[i] == i):

            # marking SPF for all numbers
            # divisible by i
            for j in range(i * i, MAXN, i):
                if (spf[j] == j):
                    spf[j] = i

                # A O(log n) function returning prime


# factorization by dividing by smallest
# prime factor at every step
def getFactorization(x):
    ret = defaultdict(int)
    while x != 1:
        ret[spf[x]]+=1
        x = x // spf[x]

    return ret

#
# # Driver code
#
# # precalculating Smallest Prime Factor
#
# x = 12246
# print("prime factorization for", x, ": ",
#       end="")
#
# # calling getFactorization function
# p = getFactorization(x)
#
# for i in range(len(p)):
#     print(p[i], end=" ")


# This code is contributed
# by Mohit kumar 29


def main():
    #t=int(input())
    global dic
    t=1
    for _ in range(t):
        n=int(input())
        arr=inar()
        sieve()
        coprime=True
        dic=defaultdict(int)
        for i in range(n):
            take=getFactorization(arr[i])
            #print(take)
            for key in take.keys():
                dic[key]+=1
                if dic[key]>1:
                    coprime=False
                    break
            if coprime==False:
                break
        if coprime:
            print("pairwise coprime")
        else:
            gc=arr[0]
            for i in range(n):
                gc=gcd(arr[i],gc)
            if gc==1:
                print("setwise coprime")
            else:
                print("not coprime")





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()
    #threadin.Thread(target=main).start()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

class factorials:
    '''
    args:
      n : max val when exploring factorials
    '''
    def __init__(self, n):
        self.n = 1# factorials to be searched
        self.factorials = set()
        self.update_factorials(n)

    def update_factorials(self, n):
        if self.n >= n:
            return None
        for i in range(self.n+1, n+1):
            done = False
            limit = int(i ** 0.5)
            for j in self.factorials:
                if j > limit: break
                if not i % j:
                    done = True
                    break
            if not done:
                self.factorials.add(i)
        self.n = n
        return None

    def factorials_set(self):
        return self.factorials

    def check_fact(self, x):
        if x > self.n**2:
            self.update_factorials(int(x ** 0.5)+1)
        MAX = int(math.sqrt(x))
        for f in self.factorials:
            if f > MAX:break
            if not x % f:
                return False
        return True

    def prime_factorization(self, val, divisors=None):
        # divisors : default-dict of divisors. Should be specified only if appended vals are required
        max_n = int(math.sqrt(val))
        if self.n < max_n:
            self.update_factorials(max_n)
        if divisors == None:
            divisors = defaultdict(lambda: 0)
        for f in self.factorials:
            if f > val: break
            while True:
                if not val % f:
                    divisors[f] += 1
                    val //= f
                else:
                    break
        if val > 1:
            divisors[val] += 1
        return divisors

def run():
    N, *A = map(int, read().split())
    MAX = max(A)
    nn = int(MAX ** 0.5)
    FACT = factorials(nn)
    FACT_SET = FACT.factorials_set()
    #print(FACT_SET)
    fact_get = set()
    done = False
    for a in A:
        #print(a, fact_get)
        if done: break
        for f in FACT_SET:
            if not a % f:
                if f in fact_get:
                    done = True
                    break
                fact_get.add(f)
                while not a % f:
                    a //= f
        if a > 1:
            if a in fact_get:
                done = True
                break
            fact_get.add(a)
    if not done:
        print('pairwise coprime')
        return

    SETWISE = False
    setwise_fact = set()
    mina = min(A)
    for f in FACT_SET:
        if not mina % f:
            setwise_fact.add(f)
            while not mina % f:
                mina //= f
    if mina > 1:
        setwise_fact.add(mina)

    for a in A:
        remlist = []
        if len(setwise_fact) == 0:
            print('setwise coprime')
            return
        for f in setwise_fact:
            if not a % f:
                continue
            else:
                remlist.append(f)
        for f in remlist:
            setwise_fact.remove(f)
        #print(a, setwise_fact)
    if len(setwise_fact) == 0:
        print('setwise coprime')
        return


    print('not coprime')



if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:

from math import gcd
N=int(input())
A=list(map(int, input().split()))


A=sorted(A)
gcda=A[0]
gcdais=True
gcdb=A[0]
MAX=max(A)
counts=[0]*MAX
counts[A[0]-1]+=1
for i in range(1,N):
    
    a=A[i]
    gcdb=gcd(gcdb, a)
    counts[a-1]+=1

for i in range(1,MAX):
    count=0
    now=i+1
    while now<=MAX:
        if counts[now-1]!=0:
            count+=counts[now-1]
        now+=(i+1)
    if count>=2:
        gcdais=False
    #print(count)
    
#print(counts)
if gcdais:
    print("pairwise coprime")
elif gcdb==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import sys
from math import gcd

input = sys.stdin.buffer.readline


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 = int(input())
A = tuple(map(int, input().split()))
MAX = 10 ** 6


def pairwise(A):
    table = [0] * (10 ** 6 + 1)
    for a in A:
        table[a] += 1
    for p in primes(MAX):
        ct = 0
        for i in range(p, MAX + 1, p):
            ct += table[i]
        if ct > 1:
            return False
    return True


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


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