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:
N = int(input())
A = list(map(int, input().split()))

h = 0

for i in range(len(A)):
  if A[i] % 2 != 0:
    h = 1
    
l = 0
for i in range(len(A)):
  if A[i] % 3 != 0:
    l = 1
    
p = 0
for i in range(len(A)):
  if A[i] % 5 != 0:
    p = 1

if h == 0 or l == 0 or p == 0:
  print("not coprime")
  
elif A[0] % 2 != 0:
  print("pairwise coprime")
  
else:
  print("setwise coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
A = tuple(map(int, input().split()))
fact_or = set()
fact_counts = [1] * (10**6+1)
def fact(n):
    exists = False
    if n%2 == 0 and 2 in fact_or:
        fact_counts[2] += 1
        exists = True
    while n%2 == 0:
        fact_or.add(2)
        n //=2

    for f in range(3, int(n**0.5)+ 1, 2):
        if n%f == 0 and f in fact_or:
            exists = True
        while n%f == 0:
            if f in fact_or:
                fact_counts[f] += 1
                exists = True
            fact_or.add(f)
            n //= f
    if n != 1:
        if n in fact_or:
            fact_counts[n] += 1
            exists = True
        fact_or.add(n)
    return exists

fact(A[0])
pairwise = True
for a in A[1:]:
    exists = fact(a)
    if exists:
        # 今まで出てきた素因数と共通するものが見つかったらpairwiseではない
        pairwise = False

if pairwise:
    print('pairwise coprime')
else:
    if max(fact_counts) == n:
        print('not coprime')
    else:
        # すべてに共通する素因数が見つからなかったら
        print('setwise coprime')

Submission status: Wrong Answer

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

counter = Counter(A)

is_pairwise = True
for key, count in counter.items():
    if key > 1 and count > 1:
        is_pairwise = False

def calc_primes(n):
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data

primes = calc_primes(int(math.sqrt(10**6)))
used = set()

def factorize(n):
    for prime in primes:
        if n == 1:
            break
        is_used = False
        while n % prime == 0:
            if prime in used:
                return False
            n //= prime
            is_used = True
        if is_used:
            used.add(prime)
    return True

all_gcd = A[0]
for a in A:
    all_gcd = math.gcd(all_gcd, a)
    if is_pairwise:
        if not factorize(a):
            is_pairwise = False

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

Submission status: Wrong Answer

Solution code:
import sys


def input():
    return sys.stdin.readline().rstrip()

def euc(a,b):

    while b!=0:
        a,b =b,a%b

    return a

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)

    if temp != 1:
        arr.append(temp)

    if arr == []:
        arr.append(n)
    return arr



def main():

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

    PS =set()

    current =A[0]
    for i in range(N-1):
        current =euc(current,A[i+1])
        if current ==1:
            break


    else:
        print("not coprime")
        exit()


    for i in range(N):
        for i in factorization((A[i])):
            if i in PS:
                print("setwise coprime")
                exit()
            else:
                PS.add(i)

    print("pairwise coprime")  
    exit()



if __name__ == "__main__":
    main()

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

N = int(input())
A = list(map(int, input().split()))
count = [0 for i in range(10**6+1)]
for ai in A:
    for y in yakusu(ai):
        count[y] += 1
max_c = max(count)
if max_c == 1:
    print('pairwise coprime')
elif max_c == N:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
def prime(n):
    nums = [True]*n
    primes = []
    for i in range(2,n):
        if nums[i]:
            primes.append(i)
            for j in range(2*i,n,i):
                nums[j] = False
    return primes

def main():
    n = int(input())
    A = set(map(int,input().split()))

    Amax = max(A)
    primes = set(prime(Amax+1))
    ct = 1
    if len(A) != n:
        ct = 2
    for p in primes:
        g = set(())
        temp = p
        while temp <= Amax:
            g.add(temp)
            temp+=p
        
        k = len(g & A)
        if k > ct:
            ct = k
    
    if len(A)==1 or ct == len(A):
        print("not coprime")
    elif ct == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
main()

Submission status: Wrong Answer

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

isSetWise = False
gcd = A[0]
if A[0] == 1:
    print("not coprime")
    exit()
for i in range(1, N):
    if A[i] == 1:
        print("not coprime")
        exit()
    gcd = math.gcd(gcd, A[i])
if gcd == 1:
    isSetWise = True

isPairWise = True
for i in range(N-1):
    if math.gcd(A[i], A[i+1]) != 1:
        isPairWise = False
        break

if isPairWise:
    print("pairwise coprime")
    exit()

if isSetWise:
    print("setwise coprime")
    exit()

print("not coprime")

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    S = 1
    d = dict()
    for x in A:
        S *= x
    flag = True
    for x in A:
        if gcd(S//x, x) == 1:
            continue
        else:
            flag = False
            break
    if flag:
        print("pairwise coprime")
    else:
        print("not coprime")


main()

Submission status: Wrong Answer

Solution code:
from math import sqrt
N = int(input())
A = list(map(int, input().split()))
M = 10 ** 6
num = [0 for i in range(M)]
num[0] = 1
for i in range(M):
  if num[i] == 0:
    if i + 1 > sqrt(M):
      break
    n = 2 * (i + 1)
    while n <= M:
      num[n-1] = 1
      n += (i + 1)
primes = [p+1 for p in range(M) if num[p] == 0]
l = len(primes)
B = [0 for i in range(l)]
x = 0
for i in range(N):
  j = 0
  while A[i] > 1:
    if A[i] % primes[j] == 0:
      B[j] += 1
      if B[j] > 1:
        x = 1
      if B[j] == N:
        x = 2
    while A[i] % primes[j] == 0:
      A[i] //= primes[j]
    j += 1
if x == 0:
  print("pairwise coprime")
elif x == 1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

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

if len(set(a))!=n:
  pflag=False
sosu=[1]*(10**6+1)
sosu[0]=0

k=2
while k<(10**5+1)**0.5+1:
  for i in range(2*k,10**5+1,k):
    sosu[i]=0
  if k==2:
    k+=1
  else:
    k+=2
gu=0
for i in range(n):
  if sosu[a[i]]!=1 and gu>1:
    pflag=False
  if a[i]%2==0:
    gu+=1
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    targets = LI()
    MAX_INT = max(targets) + 1
    targets = set(targets)
    is_pw = True

    if len(targets) != N:
        is_pw = False

    if len(targets) == 1:
        print("not coprime")
        return

    for i in range(2, MAX_INT):
        origin = i
        kosuu = 0
        while origin <= MAX_INT:
            if origin in targets:
                kosuu += 1
            origin += i

        if kosuu <= 1:
            continue
        elif kosuu < N:
            is_pw = False
        else:
            print("not coprime")
            return

    if is_pw:
        print("pairwise coprime")
        return
    print("setwise coprime")


main()

Submission status: Wrong Answer

Solution code:
import math

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

t = A[0]
check = A[0]
for i in range(n):
    s = math.gcd(check, A[i])
    t = math.gcd(t, A[i])
    check *= A[i] // t


if t == 1 and s == 1:
    print('pairwise coprime')
elif t == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
from math import gcd
n = int(input())
a = list(map(int, input().split()))
a.sort()
used = [False] * (10**6+1)

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

input_list = sieve_of_erastosthenes(int(-(-10**3//1))+1)
prime_list = [i for i, b in enumerate(input_list) if b == True]

def factorization(n):
    arr = []
    temp = n
    for i in prime_list:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

g = a[0]
arr = factorization(a[0])
for i in arr:
    used[i] = True

pair = True
for i in range(n-1):
    g = gcd(g, a[i+1])
    # 一度でも互いに素でない組合せが出たらpariwise coprimeではない
    if pair:
        arr = factorization(a[i+1])
        for i in arr:
            if i == 1: continue
            if used[i]: pair=False
            used[i] = True
    if g > 1:
        print('not coprime')
        exit(0)
if not pair:
    print('setwise coprime')
    exit(0)
else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
def make_divisors(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])

    a = set([item[0] for item in arr])
    if 1 in a:
        a.remove(1)

    return a


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

is_pairwise = True
is_setwise = False

f_set = set()
n_set = set()

for item in a:
    if item in n_set or item == 1:
        is_pairwise = False
        break
    else:
        n_set.add(item)
    for fc in make_divisors(item):
        if fc in f_set:
            is_pairwise = False
            break
        else:
            f_set.add(fc)
    if not is_pairwise:
        break

s_set = make_divisors(a[0])
for item in a[1:]:
    tmp_set = make_divisors(item)
    s_set = s_set & tmp_set
    if len(s_set) == 0:
        is_setwise = True

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

Submission status: Wrong Answer

Solution code:
import  math

n = int(input())
A = list(map(int, input().split()))
ans = A[0]
flag = 0

for i in range(1, n):
    ans = math.gcd(ans, A[i])
    if ans != 1:
        flag = 1

if ans == 1 and flag == 0:
    print('pairwise coprime')
elif ans == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

N = 1000
L = list(range(2,N+1))
p = list()
while L[0]**2<=N:
    tmp = L[0]
    p.append(tmp)
    L = [e for e in L if e%tmp!=0]
p = p + L

def function(n):
    memo = set()
    r = int((n+1)**0.5)
    for i in p:
        if n % i == 0:
            c = 0
            while n % i == 0:
                c += 1
                n //= i
            memo.add(i)
    if n > 1:
        memo.add(n)
    return memo

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

total_gcd = A[0]
for a in A:
    total_gcd = gcd(total_gcd, a)
    if total_gcd == 1:
        break

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

setA = set(A)
if len(setA) > len(p):
    print("setwise coprime")
    exit()

total = set()
cnt = 0
seki = set(p)
for a in A:
    s = function(a)
    total = total | s
    seki = seki & s
    cnt += len(s)
# print(total)

if seki == set():  # 全部に共通する素因数はない
    if len(total) != cnt:  # どこかに共通あり
        print("setwise coprime")
    else:
        print("pairwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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

def prime_decomposition(n):
    i = 2
    table = []
    while i**2 <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1: table.append(n)
    return set(table)

pri_0 = prime_decomposition(a[0])
pri_1 = prime_decomposition(a[1])
ans = pri_0 & pri_1

if len(ans):
    for i in range(2, n):
        res = prime_decomposition(a[i])
        ans &= res
        if not ans:
            print('setwise coprime')
            sys.exit()
    print('not coprime')
else:
    ans = pri_0 | pri_1
    for i in range(2, n):
        res = prime_decomposition(a[i])
        for i in res:
            if i in ans:
                print('setwise coprime')
                sys.exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
lis = [True for i in range(10**6+1)]
flag = False
for i in range(2, 10**3 + 1):
    if lis[i] == True:
        j = i
        while j <= 10**3+1:
            lis[j] = False
            j += i
        now = 0
        for a in A:
            if a % i == 0:
                now += 1
        if now == n:
            print("not coprime")
            exit()
        if now > 1:
            flag = True
if flag:
    print("setwise coprime")
else:
    print("pairwise 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()

pn = []
d = np.zeros(int(max_a**0.5)+10)
for i in range(2, int(max_a**0.5)+1):
    if d[i] == 0:
        pn.append(i)
        d[i::i] = 1

A = np.asarray(A)
for i in pn:
    if np.sum(A%i == 0) >= 2:
        print('setwise coprime')
        exit()
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
def main():

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

    A = [v for v in A if v != 1]
    if len(A) == 0: return "pairwise coprime"
    if len(set(A)) < len(A): return "not coprime"
    A = list(set(A))

    def searchPrimeNum(N):
        max = int(math.sqrt(N))
        seachList = [i for i in range(2,N+1)]
        primes = []
        while seachList[0] <= max:
            primes.append(seachList[0])
            tmp = seachList[0]
            seachList = [i for i in seachList if i % tmp != 0]
        primes.extend(seachList)
        return primes

    primes = searchPrimeNum(max(A))
    # print(primes)

    d = dict()
    ispair = True
    isset = True

    for v in A:
        for p in primes:
            if p <= v:
                if v % p == 0:
                    d[p] = d.get(p, 0) + 1
            else:
                break
    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"

    return "not coprime"

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

Submission status: Wrong Answer

Solution code:
import math
import copy

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


dp=[0 for _ in range(1000000+1)]

sosuu = [2]
A = 1000
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.append(L)

if n>=80000:
  g=a[0]
  for h in range(1,n):
    g=math.gcd(g,a[h])
  if g==1:
    print('setwise coprime')
    
  else:
      print('not coprime')
  
  
else:
  ch1=0
  ch3=0
  for w in sosuu:
    ch2=0
    for q in range(n):
      if B[q]%w==0:
        ch2+=1
        S=B[q]
        while S%w==0:
          S=S//w
        B[q]=S
    if ch2>1:
      ch3+=1
  d={}
  ch4=0
    
  for u in B:
      if u>1000:
        if u not in d:
          d[u]=0
        else:
          ch4+=1
  if ch3==0 and ch4==0:
    print('pairwise coprime')
      
  
  
    
  else:
    g=a[0]
    for h in range(1,n):
      g=math.gcd(g,a[h])
    
    if g==1:
      print('setwise coprime')
    
    else:
      print('not coprime')

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
from math import gcd
n=int(stdin.readline())
a=list(map(int,stdin.readline().split()))
s=set(a)
p=2;d={}
N=max(a)+2
primes=[1]*N;not_pairwise=0
while p*p<=N:
    if primes[p]:
        for mul in range(p,N,p):
            primes[mul]=0
            if mul in s:
                d[mul]=d.get(mul,0)+1
                if d[mul]>=2:not_pairwise=1;break;
        if not_pairwise:break
    p+=1
g=a[0]
for v in a:
    g=gcd(g,v)
if not_pairwise==0:print('pairwise coprime')
elif g==1:print('setwise coprime')
else:print('not 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(min(max(n//4,i+1),n-1),min(n//4+1000,n)):
            if math.gcd(a[i],a[j])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans
ruiseki=1

for i in range(n):
  ruiseki=ruiseki*a[i]%mod

for i in range(n):
    num=math.gcd(a[i],ruiseki//a[i])
    if num!=1:
      if setwise_coprime(a)==1:
        print("setwise coprime")
        sys.exit()
      else:
        print("not coprime")
        sys.exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
p=[1 for i in range(1001)]
p[0]=0
p[1]=0
for i in range(2,1001):
    if p[i]==1:
        for j in range(2,1001):
            if i*j<=1000:
                p[i*j]=0
#print(p[:25])
Prime=[]
for i in range(1001):
    if p[i]==1:
        Prime.append(i)
#print(Prime)
#print(len(Prime))
N=int(input())
L=list(map(int,input().split()))

def gcd(a,b):
    if b>a:
        a,b=b,a
    while a%b!=0:
        a,b=b,a%b
    return b
    
X=L[0]
for i in range(1,N):
    X=gcd(X,L[i])
    if X==1:
        break
if X>1:
    print("not coprime")
    exit()
        
D={}
for i in range(N):
    I=L[i]
    for j in Prime:
        if I%j==0:
            if j not in D:
                D[j]=1
            else:
                print("setwise coprime")
                exit()
            while I%j==0:
                I//=j
    if I!=1:
        if I not in D:
            D[I]=1
        else:
            print("setwise coprime")
            exit()
#print(D)

print("setwise coprime")

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[0]*(10**6+100)
for m in a:
  l[m]=1
x=0
j=2
#print(l)
while j <10**3+1:
  c=0
  k=1
  while j*k<=10**6+1 :
    if l[j*k]==1:
      c+=1
      l[j*k]=0
    k+=1
  if c==n:
    print("not coprime")
    exit()
  elif c>1:
    x=1
  j+=1 
  
if x==1:
  print("setwise coprime")
else:
  print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

N = 1000
L = list(range(2,N+1))
p = list()
while L[0]**2<=N:
    tmp = L[0]
    p.append(tmp)
    L = [e for e in L if e%tmp!=0]
p = p + L

def function(n):
    memo = set()
    for i in p:
        if n % i == 0:
            memo.add(i)
    return memo

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

total_gcd = A[0]
for a in A:
    total_gcd = gcd(total_gcd, a)
    if total_gcd == 1:
        break

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

setA = set(A)
if len(setA) > len(p):
    print("setwise coprime")
    exit()

total = set()
cnt = 0
seki = set(p)
for a in A:
    s = function(a)
    total = total | s
    seki = seki & s
    cnt += len(s)
# print(total)

if seki == set():  # 全部に共通する素因数はない
    if len(total) != cnt:  # どこかに共通あり
        print("setwise coprime")
    else:
        print("pairwise coprime")
else:
    print("not coprime")

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=1000002
    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(set)
    ok=True
    for i in ar:
        x=i
        while(x!=1):
            tp=prime[x]
            x=x//prime[x]
            d[tp].add(i)

    for i in d.keys():
        if(len(d[i])>1):
            ok=False
            break

    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:
N = int(input())
A = list(map(int, input().split()))

import itertools
import math
#
ans_list = 1
not_pair = False
not_set = False

for combi in itertools.combinations(A, 2):
    ans = math.gcd(combi[0], combi[1])
    if ans != 1:
        not_pair = True
        if ans_list == 1:
            ans_list = ans
        else:
            ans_list = math.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 math
n=int(input())
l=list(map(int,input().split()))
e=0
e1=0
e2=0
e3=0
c=l[0]
for i in range(1,n):
    c=math.gcd(l[i],c)
for i in range(n):
    if(l[i]%2==0):
        e+=1
    if(l[i]%3==0):
        e1+=1
    if(l[i]%5==0):
        e2+=1
    if(l[i]%7==0):
        e3+=1

if(e<=1 and e1<=1 and e2<=1 and e3<=1 and c==1):
    print("pairise coprime")
elif(c==1):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	nn=II()
	A=LI()
	ans="pairwise coprime"

	n = 1000000
	primes = set(range(2, n+1))
	for i in range(2, int(n**0.5+1)):
		primes.difference_update(range(i*2, n+1, i))
	primes=set(primes)

	#print(primes)


	B=set(range(1,10**6+1))
	C=set()
	for i in A:
		a=set()
		while i%2==0:
			a.add(2)
			i//=2
		f=3
		while f*f<=i:
			if i in primes:
				break
			elif n%f==0:
				a.add(f)
				i//=f
			else:
				f+=2
		if i!=1:
			a.add(i)
		B&=a
		if C&a:
			ans="setwise coprime"
		C|=a

	if B:
		ans="not coprime"

	print(ans)





















if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from math import gcd
import numpy as np

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

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


def sieve(x):
    """
    Sieve of Eratosthenes
    :param x: max value
    :return: list of bool
    """

    is_prime = [True] * (x + 1)
    is_prime[0] = is_prime[1] = False

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

    return is_prime


g = a[0]
for e in a:
    g = gcd(g, e)

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

primes = sieve(MAX)
p = [i for i, e in enumerate(primes) if e]

for i, e in enumerate(nums):
    if e:
        if e > 1:
            print("setwise coprime")
            exit()
        nums[i] = 0
        for ep in p:
            if ep > i:
                break

            if i % ep == 0:
                if nums[ep::ep].any():
                    print("setwise coprime")
                    exit()

print("pairwise coprime")

Submission status: Wrong Answer

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

h = 0

for i in range(len(A)):
  if A[i] % 2 != 0:
    h = 1
    
l = 0
for i in range(len(A)):
  if A[i] % 3 != 0:
    l = 1
    
p = 0
for i in range(len(A)):
  if A[i] % 5 != 0:
    p = 1
    
q = 0
for i in range(len(A)):
  if A[i] % 7 != 0:
    q = 1
    
r = 0
for i in range(len(A)):
  if A[i] % 11 != 0:
    r = 1
    
s = 0
for i in range(len(A)):
  if A[i] % 13 != 0:
    s = 1

if h == 0 or l == 0 or p == 0 or q == 0 or r == 0 or s == 0:
  print("not coprime")
  
elif A[0] % 2 == 0:
  print("setwise coprime")
  
else:
  print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import sys

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

a = 1
result = []
for i in range(len(arr) - 1):
    result.append(gcd(arr[i], arr[i + 1]))

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

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

if result2.count(1) == len(arr) - 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys


def input():
    return sys.stdin.readline().rstrip()

def euc(a,b):

    while b!=0:
        a,b =b,a%b

    return a

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)

    if temp != 1:
        arr.append(temp)

    if arr == []:
        arr.append(n)
    return arr



def main():

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

    PS =set()

    current =A[0]
    for i in range(N-1):
        current =euc(current,A[i+1])
        if current ==1:
            break


    else:
        print("not coprime")
        exit()


    if N>=100000:
        print("setwise coprime")
        exit()

    for i in range(N):
        for i in factorization((A[i])):
            if i in PS:
                print("setwise coprime")
                exit()
            else:
                PS.add(i)

    print("pairwise coprime")



if __name__ == "__main__":
    main()