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
from functools import reduce
k=10**6+1
def judge(n,a):
  c=[0]*k
  for x in a:
    c[x]+=1
  t=any(sum(c[i::i])>1 for i in range(2,k))
  t+=reduce(gcd,a)>1
  return ['pairwise','setwise','not'][t]+' coprime'
n=int(input())
a=list(map(int,input().split()))
print(judge(n,a))

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
NUM_MAX = 10**6 + 1
def solve(n, a):
    c = [0] * NUM_MAX
    for x in a:
        c[x] += 1
    t = any(sum(c[i::i]) > 1 for i in range(2, NUM_MAX))
    t += reduce(gcd, a) > 1
    return ["pairwise", "setwise", "not"][t] + " coprime"

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

Submission status: Accepted

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))

def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a
r = [0] * (n+1)
sosu = [False for i in range(10**6+1)]

for i in range(n):
  r[i+1] = math.gcd(r[i],a[i])
if r[-1] != 1:
  print ('not coprime')
  exit()

for i in range(n):
  ary = set(prime_factorize(a[i]))
  for j in ary:
    if sosu[j]:
      print ('setwise coprime')
      exit()
    sosu[j] = True
print ('pairwise coprime')

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)
    N = 1000001
    f = [1]*N
    lis = []
    p = 2
    while p < N:
        while p < N and not f[p]:
            p += 1
        j = p
        lis.append(p)
        while j < N:
            f[j] = 0
            j += p
    def func(n):
        i = 0
        p = lis[i]
        if n < 2:
            return 0
        while p*p <= n:
            if n%p == 0:
                if c[p]:
                    return 1
                c[p] = 1
                while n%p == 0:
                    n //= p
            i += 1
            p = lis[i]
        if c[n]:
            return 1
        if n > 1:
            c[n] = 1
        return 0
    n = I()
    a = LI()
    g = a[0]
    for i in a[1:]:
        g = gcd(g,i)
    if g != 1:
        print("not coprime")
        return
    c = [0]*N
    for i in a:
        if func(i):
            print("setwise coprime")
            return
    print("pairwise coprime")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineerin College

'''
import sys
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]



def solve():
    
    
    
    # for _ in range(ii()):
    
    
    n = ii()
    a = li()
    f = 1
    freq = [0]*1000005
        
    for i in a:
        x = i
        for j in range(2,int(sqrt(x))+1):
            c = 0
            while(x%j==0):
                x//=j
                c=1
            if(c > 0):
                if freq[j]>0:
                    f = 0
                    break
                freq[j] = 1
        if(x>1):
            freq[x]+=1
            if(freq[x]>1):
                f = 0
                break
        if(f==0):
            break
        
    if(f):
        print('pairwise coprime')
    else:
        x = a[0]
        for i in range(1,n):
            x = gcd(x,a[i])
        if(x==1):
            print('setwise coprime')
        else:
            print('not coprime')
    
    
    
    
    
    
    
if __name__ =="__main__":
    # read()
    solve()

Submission status: Accepted

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

cnt = [0] * (10**6 + 1)
for i in range(N):
    cnt[A[i]] += 1

flag = True
for i in range(2, 10**6 + 1):
    multiple = 0
    for j in range(i, 10**6 + 1, i):
        multiple += cnt[j]
    if multiple == N:
        print("not coprime")
        exit()
    if multiple >= 2:
        flag = False

print("pairwise coprime" if flag else "setwise coprime")

Submission status: Accepted

Solution code:
import math
N = int(input())
Alist = list(map(int,input().split()))
box = [0]*(10**6+1)
sign = math.gcd(Alist[0],Alist[1])
Amax = max(Alist[0],Alist[1])
for i in range(0,len(Alist)):
    A = Alist[i]
    sign = math.gcd(sign, A)
    Amax = max(Amax, A)
    box[A] += 1
setwise = (sign == 1)
pairwise = (sign == 1)
Amax = math.sqrt(Amax)+1
for i in range(2,10**6+1):
    if sum(box[i::i]) >1:
        pairwise = False
        break
if setwise:
    if pairwise:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
NUM_MAX = 10**6 + 1
def solve(n, a):
    c = [0] * NUM_MAX
    for x in a:
        c[x] += 1
    t = any(sum(c[i::i]) > 1 for i in range(2, NUM_MAX))
    t += reduce(gcd, a) > 1
    return ["pairwise", "setwise", "not"][t] + " coprime"

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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


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




n=int(input())
L=list(map(int,input().split()))
val = L[0]

for i in range(1,n):
    val = gcd(L[i],val)

if val!=1:
    print('not coprime')
    sys.exit()

d={}
for i in range(n):
    factor=prime_factor(L[i])
    for j in factor:
        if j not in d:
            d[j]=1
        else:
            print('setwise coprime')
            sys.exit()
print('pairwise coprime')

Submission status: Accepted

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

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

MAXA = 10**6
B = [0] * (MAXA+1)
for a in A:
    if a==1: continue
    if B[a]:
        print('setwise coprime')
        exit()
    B[a] = 1

for n in range(2,MAXA+1):
    c = 0
    for m in range(n,MAXA+1,n):
        c += B[m]
        if c > 1:
            print('setwise coprime')
            exit()

print('pairwise coprime')

Submission status: Accepted

Solution code:
_, *A = map(int, open(0).read().split())
lc = 10**6 + 1
C = [0] * lc
for a in A: C[a] += 1
import functools, math
t = any(sum(C[i::i]) > 1 for i in range(2, lc))
t += functools.reduce(math.gcd, A) > 1
print(['pairwise','setwise','not'][t], 'coprime')

Submission status: Accepted

Solution code:
_ = input()
A = [*map(int, input().split())]
C = [0] * (1000001)
for a in A: C[a] += 1
from functools import reduce
from math import gcd
t = any(sum(C[i::i]) > 1 for i in range(2, 1000001))
t += reduce(gcd, A) > 1
print(['pairwise','setwise','not'][t], 'coprime')

Submission status: Accepted

Solution code:
import sys, math

N = int(input())
A = list(map(int, input().split()))
G = 0
for a in A:
    G = math.gcd(G, a)

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

M = 10 ** 6 + 5
B = dict()
for a in A:
    if a in B:
        B[a] = B[a] + 1
    else:
        B[a] = 1

for i in range(2, M):
    cnt = 0
    for j in range(i, M, i):
        if j in B:
            cnt += B[j]
    if cnt > 1:
        print("setwise coprime")
        exit(0)

print("pairwise coprime")

Submission status: Accepted

Solution code:
from collections import defaultdict
MAX_A = 10**6

sieve = [[] for _ in range(MAX_A+1)]
# sieve[i] = True if i is prime
# sieve[i] = prime factors of i

for f in range(2, MAX_A + 1):
  if not sieve[f]:
    c = f
    while c <= MAX_A:
      sieve[c].append(f)
      c += f

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

cnt = defaultdict(int)
for a in A:
  for s in sieve[a]:
    cnt[s] += 1

def is_pairwise_coprime():
  return all(v == 1 for v in cnt.values())

def is_setwise_coprime():
  return all(v < N for v in cnt.values())

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

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

max_A = max(A)
sqrt_max_A = math.ceil(max_A ** 0.5)
sieve = list(range(2, max_A+1))
prime = list(range(max_A+1))
while len(sieve) > 0 and sieve[0] <= sqrt_max_A:
    p = sieve[0]
    prime[p]= p
    new_sieve = []
    for s in sieve:
        if s % p == 0:
            prime[s] = p
        else:
            new_sieve.append(s)
    sieve = new_sieve

factors = {}
pairwise = True
for a in A:
    while prime[a] != a:
        if prime[a] in factors:
            pairwise = False
            break
        factors[prime[a]] = True
        p = prime[a]
        while a % p == 0:
            a //= p
    if a != 1:
        if a in factors:
            pairwise = False
        else:
            factors[a] = True
    if not pairwise:
        break
if pairwise:
    print('pairwise coprime')
else:
    gcd = reduce(math.gcd, A)
    if gcd == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Accepted

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

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

# 1~aの最大値までの数の最小の素因数を前処理で求める(O(max_aloglog(max_a)))
def smallest_prime_factors(a):
    max_a = max(a)
    smallest_prime_factors = [int(x) for x in range(max_a + 1)]
    for i in range(2, max_a + 1):
        if smallest_prime_factors[i] == i:
            for j in range(i, max_a + 1, i):
                if smallest_prime_factors[j] == j:
                    smallest_prime_factors[j] = i
        else:
            continue
    return smallest_prime_factors

smallest_prime_factors = smallest_prime_factors(a)

# nを素因数分解(O(log(n)))
def prime_factorize(n):
    prime_factors = []
    if n == 1:
        return prime_factors
    while n != smallest_prime_factors[n]:
        prime_factors.append(smallest_prime_factors[n])
        n //= smallest_prime_factors[n]
    prime_factors.append(n)
    return prime_factors

prime_factors = set()

flag = 1

for i in a:
    prime_factorize_i = set(prime_factorize(i))
    for j in prime_factorize_i:
        if j in prime_factors:
            flag = 0
            break
        else:
            prime_factors.add(j)

if flag:
    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')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
#    bp.sort()
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1

#p=get_primenumber(amax)

#for pp in p:
for pp in range(2,amax+1):
    psum=sum(aa[pp: :pp])
#    print("pp:",pp,psum)
    if psum>=2:
            print("setwise coprime")
            sys.exit()
## max_13.txt ... max_16.txt : "setwise coprime"
print("pairwise coprime")

Submission status: Accepted

Solution code:

import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

from collections import deque    
#    q = deque(l)
#    q.append(4) # 後ろから4を挿入, l=deque([0,1,2,3,4])
#    q.appendleft(5)#前から5を挿入, l=deque([5,0,1,2,3,4])
#    x = q.pop() #後ろの要素を取り出す, x=4, l=deque([5,0,1,2,3])
#    y = q.popleft() # 前の要素を取り出す, y=5, l = deque([0,1,2,3])

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
#    search_list = deque(list(range(2,number+1)))
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
#    while search_list[0] <= math.sqrt(number):
    while search_list[0]**2 <= number:
      #search_listの先頭の値が√nの値を超えたら終了
      #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
#        head_num = search_list.popleft()
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
#        search_list =deque( [num for num in search_list if num % head_num != 0])
        search_list =[num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp.sort()
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1

#p=get_primenumber(amax)

#for pp in p:
for pp in range(2,amax+1):
    psum=sum(aa[pp: :pp])
#    print("pp:",pp,psum)
    if psum>=2:
            print("setwise coprime")
            sys.exit()
## max_13.txt ... max_16.txt : "setwise coprime"
print("pairwise coprime")

Submission status: Accepted

Solution code:
import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

from collections import deque    
#    q = deque(l)
#    q.append(4) # 後ろから4を挿入, l=deque([0,1,2,3,4])
#    q.appendleft(5)#前から5を挿入, l=deque([5,0,1,2,3,4])
#    x = q.pop() #後ろの要素を取り出す, x=4, l=deque([5,0,1,2,3])
#    y = q.popleft() # 前の要素を取り出す, y=5, l = deque([0,1,2,3])

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = deque(list(range(2,number+1)))
#    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
#    while search_list[0] <= math.sqrt(number):
    while search_list[0]**2 <= number:
      #search_listの先頭の値が√nの値を超えたら終了
      #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.popleft()
#        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        search_list =deque( [num for num in search_list if num % head_num != 0])
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp.sort()
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1

#p=get_primenumber(amax)

#for pp in p:
for pp in range(2,amax+1):
    psum=sum(aa[pp: :pp])
#    print("pp:",pp,psum)
    if psum>=2:
            print("setwise coprime")
            sys.exit()
## max_13.txt ... max_16.txt : "setwise coprime"
print("pairwise coprime")

Submission status: Accepted

Solution code:

import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

from collections import deque    
#    q = deque(l)
#    q.append(4) # 後ろから4を挿入, l=deque([0,1,2,3,4])
#    q.appendleft(5)#前から5を挿入, l=deque([5,0,1,2,3,4])
#    x = q.pop() #後ろの要素を取り出す, x=4, l=deque([5,0,1,2,3])
#    y = q.popleft() # 前の要素を取り出す, y=5, l = deque([0,1,2,3])

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = deque(list(range(2,number+1)))
#    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
#    while search_list[0] <= math.sqrt(number):
    while search_list[0]**2 <= number:
      #search_listの先頭の値が√nの値を超えたら終了
      #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.popleft()
#        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        search_list =deque( [num for num in search_list if num % head_num != 0])
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp.sort()
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1

p=get_primenumber(amax)

for pp in p:
#for pp in range(2,amax+1):
    psum=sum(aa[pp: :pp])
#    print("pp:",pp,psum)
    if psum>=2:
            print("setwise coprime")
            sys.exit()
## max_13.txt ... max_16.txt : "setwise coprime"
print("pairwise coprime")

Submission status: Accepted

Solution code:
from functools import reduce
from math import gcd

N, *A = map(int, open(0).read().split())

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

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

elif all(sum(C[i::i]) <= 1 for i in range(2, len(C))):
    print("pairwise coprime")

else:
    print("setwise coprime")

Submission status: Accepted

Solution code:
from functools import reduce
from math import gcd

N, *A = map(int, open(0).read().split())

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

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

elif all(sum(C[i::i]) <= 1 for i in range(2, len(C))):
    print("pairwise coprime")

else:
    print("setwise coprime")

Submission status: Accepted

Solution code:
from math import gcd

n = int(input())
A = list(map(int, input().split()))
maxA = 10**6+5

def furui(x):
    memo = [0]*(x+1)
    primes = []
    for i in range(2, x+1):
        if memo[i]: continue
        primes.append(i)
        memo[i] = i
        for j in range(i*i, x+1, i):
            if memo[j]: continue
            memo[j] = i
    return primes

primes = furui(maxA)

c = [0]*maxA
for a in A: c[a] += 1

for p in primes:
    cnt = 0
    for i in range(p, maxA, p):
        cnt += c[i]
    if cnt >= 2:
        break
else:
    print('pairwise coprime')
    exit()

g = 0
for a in A:
    g = gcd(g, a)
if g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd
n=int(input())
a=list(map(int,input().split()))
g=gcd(a[0],a[1])
for i in range(n-2):
    g=gcd(g,a[i+2])
if a==[1]*n:
    print("pairwise coprime")
    exit()
if g!=1:
    print("not coprime")
    exit()
temp=[i for i in range(10**6+5)]
p=2
while p*p<=10**6+5:
    if temp[p]==p:
        for q in range(2*p,10**6+5,p):
            if temp[q]==q:
                temp[q]=p
    p+=1
ans=[0]*(10**6+10)
for j in a:
    count=set()
    while j>1:
        count.add(temp[j])
        j//=temp[j]
    for k in count:
        ans[k]+=1
if max(ans)!=1:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Accepted

Solution code:
from functools import reduce
from math import gcd

n = int(input())
A = list(map(int, input().split()))
maxA = 10**6+5

def furui(x):
    memo = [0]*(x+1)
    for i in range(2, x+1):
        if memo[i]: continue
        memo[i] = i
        for j in range(i*i, x+1, i):
            if memo[j]: continue
            memo[j] = i
    return memo

memo = furui(maxA)
tf = [True]*(maxA)
for a in A:
    if a == 1: continue
    pfct = []
    while a > 1:
        pfct.append(memo[a])
        a //= memo[a]

    for b in set(pfct):
        if not tf[b]:
            break
        tf[b] = False
    else:
        continue
    break
else:
    print('pairwise coprime')
    exit()

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

Submission status: Accepted

Solution code:
from math import gcd 

n = int(input())
maxA = 10**6+5
A = list(map(int, input().split()))
c = [0]*maxA
for a in A:
    c[a] += 1

for i in range(2, maxA):
    cnt = 0
    for j in range(i, maxA, i):
        cnt += c[j]
    if cnt >= 2:
        break
else:
    print('pairwise coprime')
    exit()

g = 0
for a in A:
    g = gcd(g, a)
if g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
from functools import reduce
from math import gcd 

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

def furui(x):
    memo = [0]*(x+1)
    primes = []
    for i in range(2, x+1):
        if memo[i]: continue
        primes.append(i)
        memo[i] = i
        for j in range(i*i, x+1, i):
            if memo[j]: continue
            memo[j] = i
    return memo, primes

memo, primes = furui(10**6+5)

pr = [True]*(10**6+5)
for a in A:
    if a == 1: continue
    while a != 1:
        w = memo[a]
        if not pr[w]:
            break
        pr[w] = False
        while a%w == 0:
            a = a // w
    else:
        continue
    break
else:
    print('pairwise coprime')
    exit()

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

Submission status: Accepted

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

def is_pairwise(A):
    D = gen_d_prim(10**6)
    past = set()
    for a in A:
        now = set()
        while a != 1:
            if not D[a] in now and D[a] in past:
                return False
            now.add(D[a])
            past.add(D[a])
            a //= D[a]
    return True

def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def solve():
    if is_pairwise(A): return 0
    if gcd_all(A) ==1: return 1
    return 2
    
n = int(input())
A = [*map(int,input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Submission status: Accepted

Solution code:
import math 
N = int(input())
A = list(map(int, input().split()))
m = [0] * int(1e6+1)
for i in range(N):
    m[A[i]] += 1
pw = True
for p in range(2, len(m)):
    c = 0
    for i in range(p, len(m), p):
        c += m[i]
    if c > 1:
        pw = False
        break
if pw:
    print('pairwise coprime')
    exit()
d = A[0]
for i in range(N):
    d = math.gcd(d, A[i])
if d == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
def is_pairwise():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    if sum(C[2::2]) > 1: return False
    for i in range(3, MAX_A, 2):
        if sum(C[i::i]) > 1: return False
    return True

def solve():
    from functools import reduce
    from math import gcd
    if is_pairwise(): return 0
    if reduce(gcd, A) == 1: return 1
    return 2

n = int(input())
A = [*map(int, input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Submission status: Accepted

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

def is_pairwise(A):
    D = gen_d_prim(10**6)
    past = set()
    for a in A:
        now = set()
        while a != 1:
            # 素数 D[a]: 今回は未済 & 過去で済
            if not D[a] in now and D[a] in past: return False
            now.add(D[a])
            past.add(D[a])
            a //= D[a]
    return True

def solve():
    from functools import reduce
    from math import gcd
    if is_pairwise(A): return 0
    if reduce(gcd, A) == 1: return 1
    return 2

n = int(input())
A = [*map(int, input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Submission status: Accepted

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

def is_pairwise(A):
    D = gen_d_prim(10**6)
    past = set()
    for a in A:
        now = set()
        while a != 1:
            # 素数 D[a]: 今回は未済 & 過去で済
            if not D[a] in now and D[a] in past: return False
            now.add(D[a])
            past.add(D[a])
            a //= D[a]
    return True

def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def solve():
    if is_pairwise(A): return 0
    if gcd_all(A) == 1: return 1
    return 2

n = int(input())
A = [*map(int, input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Submission status: Accepted

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

def is_pairwise(A):
    D = gen_d_prim(10**6)
    past = set()
    for a in A:
        now = set()
        while a != 1:
            # 素数 D[a]: 今回は未済 & 過去で済
            if not D[a] in now and D[a] in past: return False
            now.add(D[a])
            past.add(D[a])
            a //= D[a]
    return True

def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def solve():
    if is_pairwise(A): return 0
    if gcd_all(A) == 1: return 1
    return 2

n = int(input())
A = [*map(int, input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Submission status: Accepted

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

def is_pairwise(A):
    D = gen_d_prim(10**6)
    past = set()
    for a in A:
        now = set()
        while a != 1:
            # 素数 D[a]: 今回は未済 & 過去で済
            if not D[a] in now and D[a] in past: return False
            now.add(D[a])
            past.add(D[a])
            a //= D[a]
    return True

def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def solve():
    if is_pairwise(A): return 0
    if gcd_all(A) == 1: return 1
    return 2

n = int(input())
A = [*map(int, input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
s.sort()

A = max(s)
dp = [0] * (A + 1)

for ss in s:
    dp[ss] += 1

pairwise = True
setwise = True

for i in range(2, A + 1):
    cnt = 0
    for j in range(i, A + 1, i):
        cnt += dp[j]
    if cnt > 1:
        pairwise = False
    if cnt == n:
        setwise = False
        break

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

Submission status: Accepted

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

def is_pairwise(A):
    D = gen_d_prim(10**6)
    past = set()
    for a in A:
        now = set()
        while a != 1:
            # 素数 D[a]: 今回は未済 & 過去で済
            if not D[a] in now and D[a] in past: return False
            now.add(D[a])
            past.add(D[a])
            a //= D[a]
    return True

def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def solve():
    if is_pairwise(A): return 0
    if gcd_all(A) == 1: return 1
    return 2

n = int(input())
A = [*map(int, input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
s.sort()

A = max(s)
dp = [0] * (A + 5)

for ss in s:
    dp[ss] += 1

pairwise = True
setwise = True

for i in range(2, A + 1):
    cnt = 0
    for j in range(i, A + 1, i):
        cnt += dp[j]
    if cnt > 1:
        pairwise = False
    if cnt >= n:
        setwise = False
        break

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