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: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
#input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

data = get_sieve_of_eratosthenes(1000001)
data2 = get_sieve_of_eratosthenes(2000)

# 1~1000000の素数リストを作成
check = [0] * (10 ** 6 + 1)
for d in data:
    check[d] = 1

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr

def is_pairwise(arr):

    cnt = [0] * 1000001
    
    # 非素数が168個以上あったらアウト
    non_prime = []
    for a in arr:
        if check[a] == 0:
            non_prime.append(a)
        else:
            cnt[a] += 1
    if len(non_prime) > 200:
        print("a")
        return 0
    
    # 非素数を素因数分解して、cntに足し合わせる
    for np in non_prime:
        for a, b in factorization(np):
            cnt[a] += 1
    if max(cnt[2:]) >= 2:
        return 0
    
    return 1
    
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def is_setwise(arr):
    
    tmp = arr[0]
    for a in arr:
        tmp = gcd(tmp, a)
    if tmp == 1:
        return 1
    else:
        return 0
        
ip = is_pairwise(A)
iss = is_setwise(A)

if ip:
    print("pairwise coprime")
else:
    if iss:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
check_list = [0]*1000010
conf = False

def make_divisors(n):
    global conf
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if check_list[i] >= 1:
                conf = True
                check_list[i] += 1
            elif check_list[i] == 0 and i != 1:
                check_list[i] = 1
            if i != n // i:
                if check_list[n//i] >= 1:
                    conf = True
                    check_list[i] += 1
                elif check_list[n//i] == 0 and n//i != 1:
                    check_list[n//i] = 1

def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(len(A)):
        make_divisors(A[i])
    if max(check_list) == len(A):
        return "not coprime"
    else:
        if conf:
            return "setwise coprime"
        else:
            return "pairwise coprime"

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

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = list(map(int, input().split()))
A_max = max(A)
if A_max == 1:
    print("pairwise coprime")
    sys.exit()
dp = [0]*(A_max+10)
p = 0
s = 0
for i in range(2, max(int((A_max+1)**0.5), 3)):
    c = 0
    if dp[i] == 0:
        dp[i] = 1
        for j in range(i, A_max+1, i):
            dp[j] = 1
        dp[A_max] = 0
        for j in range(N):
            if A[j] % i == 0:
                c += 1
        if c >= 2:
            p = 1
        if c == N:
            s = 1
if p == 0:
    print("pairwise coprime")
elif s == 0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

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

g = a[0]
for i in range(1, n):
    g = gcd(g, a[i])
    if g == 1:
        break
else:
    print('not coprime')
    exit()

ind = [-1] * (10**6)

prime = [2, 3, 5, 7]
for i in range(11, 10 ** 6, 2):
    j = 0
    flag = True
    while prime[j] * prime[j] <= i:
        if i % prime[j] == 0:
            flag = False
            break
        else:
            j += 1
    if flag:
        prime.append(i)

for i in range(len(prime)):
    ind[prime[i]] = i

# len(prime) = 78498

tf = [False] * len(prime)

for i in a:
    for j in range(len(prime)):
        if j > 3 and prime[j] * prime[j] > i:
            if tf[ind[i]]:
                print('setwise coprime')
                exit()
            tf[ind[i]] = True
            break

        if i % prime[j] == 0:
            if tf[j]:
                print('setwise coprime')
                exit()
            tf[j] = True
            while i % prime[j] == 0:
                i //= prime[j]

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
def a(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    for i in pr:
        if n % i == 0:
            lower_divisors.append(i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
def primes(n):
    candidate = list(range(2, n+1))
    prime = []
    limit = n**0.5 + 1
    while True:
        p = candidate[0] 
        if limit <= p:
            prime.extend(candidate)
            break
        prime.append(p)

        candidate = [i for i in candidate if i % p != 0]
    return prime
N=int(input())
pr=primes(1000)
L=list(map(int,input().split()))
gc=L[0]
for i in L:
  gc=math.gcd(i,gc)
  if gc==1:
    break
if gc!=1:
  print("not coprime")
  exit()
ans=set()
c=0
for i in L:
  c+=len(a(i))
  ans=set(a(i))|ans
if c==len(ans):
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Wrong Answer

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

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


primes=[];
isprime=[1 for i in range(0,1001)];
isprime[1]=0;isprime[0]=0
for i in range(2,1001):
  if isprime[i]:
    primes.append(i)
    j=2;
    while i*j<=1000:
      isprime[i*j]=0;
      j+=1
#s=set();


pc=(len(set(A))==N)   
#s=[0 for i in range(0,1001)];
s=[0 for i in range(0,1000001)]
#s2=set();
for i in range(N):
  a=A[i];
  
  for p in primes:
    #if a==1:
    #  break
    if(a%p==0):
      #while(a%p==0):
      #  a//=p;
      if s[p]:
        pc=0
      s[p]=1
    #if a>=1000:
    #if a!=1:
      #if a in s2:
      #if s[a]:
      #  pc=0
      #s2.add(a)
      #s[a]=1


g=A[0];
for i in range(1,N):
  g=gcd(g,A[i])
print("pairwise coprime"if pc else("setwise coprime"if g==1 else "not coprime"))

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

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

gcdAll = A[0]
isPairwise = True

for j in range(1, len(A)):
    gcdAll = math.gcd(gcdAll, A[j])
    if not isPairwise:
        continue
    for i in range(0, j):
        gcdNow = math.gcd(A[i], A[j])
        if gcdNow != 1:
            isPairwise = False
            break

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

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n=I()
    lis=LI()
    nums=[i for i in range(10**6+1)]
    spf=[-1 for i in range(10**6+1)]
    i=2
    while i<=10**1:
        if spf[i]>=0:
            i+=1
        for j in range(1,(10**6)//i+1):
            if spf[i*j]==-1:
                spf[i*j]=i
        i+=1
    #print(spf)
    dic=defaultdict(lambda :0)
    for i in range(n):
        x=lis[i]
        key=set()
        while x>1:
            u=spf[x]
            x//=u
            key.add(u)
        for z in key:
            dic[z]+=1
    #print(dic)
    flag=True
    for z in dic.keys():
        if dic[z]==n:
            print("not coprime")
            sys.exit()
        if dic[z]>1:
            flag=False
        
    if flag==True:
        print("pairwise coprime")
        sys.exit()
    print("setwise coprime")
                
        
            
        
            
            

            
            
            

    
            
            
            
            
        
        
        
    
        
            
        
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
tmp = [False if i == 0 or i == 1 else True for i in range(1000)]
p, s = True, True

for i in range(2, 1000):
    t = 0
    if not tmp[i]:
        continue

    for j in range(N):
        if A[j] % i == 0:
            t += 1
            A[j] //= i

    for j in range(i * 2, 1000, i):
        tmp[j] = False

    if t >= 2:
        p = False

    if t == N:
        s = False
        break
if p:
    print('pairwise coprime')
else:
    print('setwise coprime' if s else 'not coprime')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A_list = list(map(int, input().split()))

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

gcd_set = set()
for i in range(N - 1):
    gcd_set.add(gcd(A_list[i], A_list[i + 1]))

if gcd_set == set([1]):
    print("pairwise coprime")
elif len(gcd_set) == N - 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
def yakusu(n):
    results = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            results.append(i)
            if i != (n // i):
                results.append(n // i)
    results += [n]
    return results
def eratos(A):
    max_Ai = 10**6
    isprime = [0 for i in range(max_Ai+1)]
    ans = []
    for ai in set(A):
        if ai == 1:
            ans += [1]
        elif isprime[ai] == 0:
            y = yakusu(ai)
            ans += [y[0]]
            for i in y:
                if isprime[i] == 0:
                    j = i + i
                    while j <= max_Ai:
                        if isprime[j] == 0:
                            isprime[j] = i
                        j = j + i
        else:
            ans += [isprime[ai]]

    return isprime, ans
N = int(input())
A = list(map(int, input().split()))
isprime, ans = eratos(A)
set_ans = set(ans)
if len(set_ans) == N:
    print('pairwise coprime')
elif len(set_ans) == 1:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import math

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

gx=list()

jud=1

for i in range(n-1):
    g = math.gcd(a[i], a[i+1])
    if g!=1:
        gx.append(g)
        if gx[0]!=g:
            jud=0

if len(gx)==0:
    print("pairwise coprime")
elif len(gx)==n-1 and jud==0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
import math

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

set_A = set(A)
set_flag = len(set_A) != N

co_prime = True
max_a = max(A)

coprime = True
exists = set()
for i in range(2, max_a + 1):
    flag = False
    for j in range(i, max_a, i):
        if j in set_A:
            if not flag:
                flag = True
            elif flag:
                coprime = False
                break
    if not coprime:
        break
pairwise = (coprime and N == len(set_A))
if pairwise:
    print("pairwise coprime")
    sys.exit()

setwise = False
tmp = A[0]
for i in range(N):
    tmp = math.gcd(tmp, A[i])
if tmp == 1:
    setwise = True

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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


n = A[0]
for i in range(1, N):
    n = gcd(n, A[i])
if n != 1:
    print('not coprime')
    exit()

A = np.asarray(A)
for i in range(2, int(max_a**0.5)+1):
    if np.sum(A%i == 0) >= 2:
        print('setwise coprime')
        exit()
print('parwise coprime')

Submission status: Wrong Answer

Solution code:
import math

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

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

if ans!=1:
    print('not coprime')

else:
    for i in range(min(10000,n-1)):
        for k in range(min(i+1,n-1),min(n,1000)):
            if math.gcd(a[i],a[k])!=1:
                print('setwise coprime')
                exit()
        for j in range(n//2,min(n//2+1000,n)):
            if math.gcd(a[i],a[j])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_right

import math
from functools import reduce

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

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


P=[2,
 3,
 5,
 7,
 11,
 13,
 17,
 19,
 23,
 29,
 31,
 37,
 41,
 43,
 47,
 53,
 59,
 61,
 67,
 71,
 73,
 79,
 83,
 89,
 97,
 101,
 103,
 107,
 109,
 113,
 127,
 131,
 137,
 139,
 149,
 151,
 157,
 163,
 167,
 173,
 179,
 181,
 191,
 193,
 197,
 199,
 211,
 223,
 227,
 229,
 233,
 239,
 241,
 251,
 257,
 263,
 269,
 271,
 277,
 281,
 283,
 293,
 307,
 311,
 313,
 317,
 331,
 337,
 347,
 349,
 353,
 359,
 367,
 373,
 379,
 383,
 389,
 397,
 401,
 409,
 419,
 421,
 431,
 433,
 439,
 443,
 449,
 457,
 461,
 463,
 467,
 479,
 487,
 491,
 499,
 503,
 509,
 521,
 523,
 541,
 547,
 557,
 563,
 569,
 571,
 577,
 587,
 593,
 599,
 601,
 607,
 613,
 617,
 619,
 631,
 641,
 643,
 647,
 653,
 659,
 661,
 673,
 677,
 683,
 691,
 701,
 709,
 719,
 727,
 733,
 739,
 743,
 751,
 757,
 761,
 769,
 773,
 787,
 797,
 809,
 811,
 821,
 823,
 827,
 829,
 839,
 853,
 857,
 859,
 863,
 877,
 881,
 883,
 887,
 907,
 911,
 919,
 929,
 937,
 941,
 947,
 953,
 967,
 971,
 977,
 983,
 991,
 997]

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

check = [0]*1000
flag = 0
for a in A:
    for p in P:
        if a%p == 0:
            if check[p] == 1:
                flag = 1
            else:
                check[p] = 1
    if flag:
        break

if gcd_list(A) > 1:
    print("not coprime")
elif flag:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

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

import itertools
import fractions

ans_list = 1
not_pair = False
not_set = False

for combi in itertools.combinations(A, 2):
    ans = fractions.gcd(combi[0], combi[1])
    if ans != 1:
        not_pair = True
        if ans_list == 1:
            ans_list = ans
        else:
            ans_list = fractions.gcd(ans, ans_list)
            if ans_list != 1:
                not_set = True
                break

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

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 10 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N = int(input())
A = list(map(int, input().split()))
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

# calc prime
MAX = 10 ** 6 + 2
is_prime = [True] * (MAX + 1)
is_prime[0] = False
is_prime[1] = False
i = 2
primes = []
cnt_a = Counter(A)
cnt_facts = defaultdict(int)
while i < MAX:
    if is_prime[i]:
        if cnt_a[i]:
            cnt_facts[i] += cnt_a[i]
        for j in range(i+i, MAX, i):
            is_prime[j] = False
            if cnt_a[j]:
                cnt_facts[i] += cnt_a[j]
        primes.append(i)
    i += 1
if cnt_facts and max(cnt_facts.values()) <= 1:
    print('pairwise coprime')
    exit()
setwise = False
g = A[0]
for a in A:
    g = gcd(g, a)
if g == 1:
    setwise = True

if setwise:
    print('setwise coprime')
if not setwise:
    print('not coprime')

Submission status: Wrong Answer

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

def get_prime(p):
  result = []
  if p==1:
    return result
  else:
    integers = [1 for _ in range(p+1)]
    integers[0] = 0
    integers[1] = 0
    for i in range(p+1):
      if integers[i] == 1:
        result.append(i)
        for j in range(i,p+1,i):
          integers[j] = 0
    return result

P = get_prime(10**6+1)
list_count = [0 for _ in range(len(P))]

setA = set(A)
flg = len(setA)<N

j = 0
for a in set(A):
  for i in range(len(P)):
    p = P[i]
    if a%p == 0:
      list_count[i] += 1
    if a < p:
      break
  if max(list_count)>=2 or flg:
    if max(list_count)<j+1:
      break

v = max(list_count)
if v == len(setA):
  answer = 'not coprime'
elif v >= 2 or flg:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
import fractions
ans = a[0]
for i in range(1, N):
    ans = fractions.gcd(ans, a[i])
if ans == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log, gcd  # log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint


def ceil(a, b): return (a + b - 1) // b


inf = float('inf')
mod = 10 ** 9 + 7


def pprint(*A):
    for a in A:     print(*a, sep='\n')


def INT_(n): return int(n) - 1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [I() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N = I()
    A = LI()
    ans = "pairwise coprime"
    for i in range(2, 1001):
        t = 0
        for a in A:
            if a % i == 0:
                t += 1
        if t == N:
            ans = "not coprime"
        elif t > 1:
            ans = "setwise coprime"
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input()) 
c=list(map(int, input().split()))
ans = 1

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

for i in range(n-1):
    f=fractions.gcd(c[i],c[i+1])
    ans = max(ans,f)

Ans = gcd_list(c)

if ans == 1:
    print('pairwise coprime')
if ans > 1 and Ans == 1:
    print('setwise coprime')
if ans > 1 and Ans > 1:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from collections import Counter
import sys

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

a = 1
result = []
for x in arr:
    y = gcd(a, x)
    result.append(y)
    a = a * x // y

if result.count(1) == len(arr):
    print("pairwise coprime")
    sys.exit()

if len(Counter(result[1:])) == 1:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict
def main():
    n = int(input())
    a = list(map(int,input().split()))
    dic = defaultdict(bool)
    pairW = True
    setW = a[0]
    for i in a:
        t = 1
        while t**2 <= i:
            if i % t == 0:
                if (t != 1 and dic[t]) or dic[i//t]:
                    pairW = False
                    break
                else:
                    dic[t] = True
                    dic[i//t] = True
            t += 1
        setW = gcd(setW,i)
    

    if pairW:
        print("pairwise coprime")
        return
    elif setW == 1:
        print("setwise coprime")
        return
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import os
import heapq
import sys,threading
import math
import operator
from collections import defaultdict,deque
from io import BytesIO, IOBase
import math as mt
sys.setrecursionlimit(10 ** 5)
threading.stack_size(2**27)


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


"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""


def inpt():
    return [int(k) for k in input().split()]

def main():
    MAXN=100002
    prime=[0]*MAXN
    prime[1] = 1
    for i in range(2, MAXN):
        prime[i] = i

    for i in range(4, MAXN, 2):
        prime[i] = 2

    for i in range(3, mt.ceil(mt.sqrt(MAXN))):
        if (prime[i] == i):
            for j in range(i * i, MAXN, i):
                if (prime[j] == j):
                    prime[j] = i
    n=int(input())
    ar=inpt()
    d=defaultdict(int)
    ok=True
    for i in ar:
        x=i
        while(x!=1):
            tp=prime[x]
            x=x//prime[x]
            if(tp in d and d[tp]!=i):
                ok=False
            d[tp]=i

    if(ok):
        print('pairwise coprime')
        exit()
    gcd=ar[0]
    for i in range(1,n):
        gcd=mt.gcd(gcd,ar[i])

    if(gcd==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()
    threading.Thread(target=main).start()

Submission status: Wrong Answer

Solution code:
import bisect
import sys,io
import math
from collections import deque
from heapq import heappush, heappop
import functools
input = sys.stdin.buffer.readline

def sRaw():
    return input().decode("utf-8").rstrip("\n").rstrip("\r")


def iRaw():
    return int(input())

def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7
#DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost

def gcd_list(As):
    return functools.reduce(math.gcd, As)

def lcm_div(x, y):
    return ((x * y) // math.gcd(x, y))%DIV

def lcm_div_list(numbers):
    return functools.reduce(lcm_div, numbers, 1)%DIV


def main():
    N = iRaw()
    As = isRaw()
    gcds = gcd_list(As)
    if gcds!=1:
        print("not coprime")
        return
    lcms = lcm_div_list(As)
    mul_d = 1
    lcm_d = 1
    for a in As:
        mul_d = (mul_d*a)%DIV
        lcm_d = lcm_div(lcm_d,a)%DIV
        if mul_d!=lcm_d:
            print("setwise coprime")
            return
    print("pairwise coprime")
    return
    
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
#input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

data = get_sieve_of_eratosthenes(1000001)
data2 = get_sieve_of_eratosthenes(2000)

# 1~1000000の素数リストを作成
check = [0] * (10 ** 6 + 1)
for d in data:
    check[d] = 1

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr

def is_pairwise(arr):

    cnt = [0] * 1000001
    
    # 非素数が168個以上あったらアウト
    non_prime = []
    for a in arr:
        if check[a] == 0:
            non_prime.append(a)
        else:
            cnt[a] += 1
    if len(non_prime) > 200:
        return 0
    
    # 非素数を素因数分解して、cntに足し合わせる
    for np in non_prime:
        for a, b in factorization(np):
            cnt[a] += 1
    if max(cnt[1:]) >= 2:
        return 0
    
    return 1
    
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def is_setwise(arr):
    
    tmp = arr[0]
    for a in arr:
        tmp = gcd(tmp, a)
    if tmp == 1:
        return 1
    else:
        return 0
        
ip = is_pairwise(A)
iss = is_setwise(A)

if ip:
    print("pairwise coprime")
else:
    if iss:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    N = int(input())
    A = list(map(int, input().split()))
    A = sorted(A)
    m = A[0]
    table = [0] * (m+1)
    for i in range(2, m+1):
        for j in range(N):
            if A[j] % i == 0:
                table[i] += 1
        if table[i] == N:
            print('not coprime')
            return
        if table[i] > 1:
            print('setwise coprime')
            return
    print('pairwise coprime')


if __name__ == '__main__':
    main(sys.stdin.readline, print)