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):
    # 同じ数があったらアウト
    len_A = len(arr)
    A = list(set(arr))
    if len_A != len(arr):
        return 0

    cnt = [0] * 1000001
    
    # 非素数が168個以上あったらアウト
    non_prime = []
    for a in arr:
        if check[a] == 0:
            non_prime.append(a)
        else:
            cnt[a] += 1
    #print(non_prime)
    
    if len(non_prime) > 200:
        return 0
    
    for np in non_prime:
        for a, b in factorization(np):
            cnt[a] += 1
    if max(cnt) >= 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:
def computeGCD(x, y): 
  
   while(y): 
        x, y = y, x % y 
  
   return x 

n=int(input())
a=list(map(int,input("\nEnter the numbers : ").strip().split()))
lc=1
mu=1
gc=computeGCD(a[0],a[1])
for i in range(n):
    mu*=a[i]
    lc=(lc*a[i])/(computeGCD(lc,a[i]))
    gc=computeGCD(gc,a[i])
if(mu==lc):
    print("pairwise coprime")    
elif(gc==1):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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

def fact(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

from collections import defaultdict
cntd=defaultdict(int)
for i in range(len(a)):
    lis = fact(a[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
m=list(map(int,input().split()))
import math
mod=10**12+7
s=m[n-1]
d=m[n-1]

r=0
for i in range(n-2,-1,-1):
    d=math.gcd(m[i],d)
    
    
    if math.gcd(s,m[i])>1:
        r=1
    s*=m[i]
    
    

    s%=mod

    
if d>1:
    print('not coprime')
elif r==1:
    print('setwise coprime')
else:
    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()))
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:
                D[j]+=1
                if D[j]<(i+1):
                    Prime.remove(j)
            while I%j==0:
                I//=j
    if I!=1:
        if I not in D:
            D[I]=1
        else:
            D[I]+=1
#print(D)

ans=0
for k,v in D.items():
    if ans<v:
        ans=v
if ans==1:
    print("pairwise coprime")
elif ans==N:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            arr.append(i)

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

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

    return arr

N = i()
A = l()
li = []
num = [0]*(10**6+1)
for i in range(N):
    for j in factorization(A[i]):
        if j not in li:
            li.append(j)
        else:
            num[j] += 1
if max(num) == 0:
    print('pairwise coprime')
elif max(num) == N-1:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:

from math import gcd
from functools import reduce


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

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

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

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

if pairwise:
    print("pairwise coprime")
elif reduce(gcd, 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()))
#

sosu = [1 for _ in range(10**6+1)]
sosu[0] = 0
sosu[1] = 1
i = 2
while i < len(sosu):
    j = i*2
    if sosu[i] == 0:
        i += 1
        continue
    while j < len(sosu):
        sosu[j] = 0
        j += i
    i += 1
sosus = []
for i in range(2, len(sosu)):
    if sosu[i]:
        sosus.append(i)

sosuset = set()
flag = 0
GCD = a[0]
for i in range(n-1, -1, -1):
    J = 0
    j = sosus[J]
    while j*j <= a[i]:
        if a[i]%j == 0 and j in sosuset:
            flag = 1
            break
        while a[i]%j == 0:
            a[i]//=j
            sosuset.add(j)
        J += 1
        j = sosus[J]
    if a[i] != 1:
        sosuset.add(a[i])
    GCD = math.gcd(GCD, a[i])

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

Submission status: Wrong Answer

Solution code:
from math import gcd
from itertools import zip_longest

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

npcf = False
while True:
    B = []
    for x, y in zip_longest(A[:len(A)//2], A[len(A)//2:], fillvalue=1):
        if gcd(x, y) != 1:
            npcf = True
            break
        B.append(x*y)
    if npcf:
        break
    if len(B) == 1:
        break
    A = B

if not npcf:
    print('pairwise coprime')
    exit()

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

Submission status: Wrong Answer

Solution code:

from math import gcd
from functools import reduce


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

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

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

pairwise = True
appeared = set()
for v in X:
    while v > 1:
        if v in appeared:
            pairwise = False
            break
        div = min_factor[v]
        while v % div == 0:
            print(v, div)
            if v in appeared:
                pairwise = False
                break
            appeared.add(v)
            v //= div

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

Submission status: Wrong Answer

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

N=10**6
spf = [i for i in range(N+1)]

for i in range(2,N):
    if i**2>N:
        break
    if spf[i] == i:
        for j in range(i**2,N+1,i):
            if spf[j] == j:
                spf[j] = i

def get(n):
    ps = set()
    while n != 1:
        ps.add(spf[n])
        n //= spf[n]
    return ps

f1=True
f2=True

n0 = list(get(A[0]))
K=set(n0)

for a in A[1:]:
    res = get(a)
    #print(K,res)
    if len(K & res) != 0:
        f1 = False
        
    K &= res
    
if len(K) == 0:
    f2 = True
else:
    f2 = False
    
if f2:
    if f1:
        print("pairwise coprime")
    else:
        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 + 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:
from collections import Counter
import sys
import numpy as np
n = int(input())
ls = list(map(int,input().split()))
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
            for _ in range(cnt):
                arr.append(i)

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

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

    return arr
if len(list(set(ls))) != len(ls):
    print("not coprime")
    sys.exit()
c = Counter(ls)
s = list(set(ls))
if np.gcd.reduce(ls) == 1:
    fi = [True]*(10**6+1)
    for y in s:
        l = list(set(factorization(n)))
        for q in l:
            u = q * 2
            while u <= 10**6:
                fi[u] = False
                u += y
    cnt = 0
    for z in ls:
        if fi[z] == True:
            cnt += 1
    if cnt == len(ls):
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

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

if len(A) <= 80000:
    for a in A:
        Fact = factorization(a)
        for f in Fact:
            if f[0]==1:continue
            if SOSUU[f[0]]:
                Fail = True
                break
            else:
                SOSUU[f[0]] = True
        if Fail:
            break
if not Fail:
    print("pairwise coprime")
else:
    print("setwise 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 i in range(bisect_right(P, int(a**0.5)+10)):
        if a%P[i] == 0:
            if check[P[i]] == 1:
                flag = 1
            else:
                check[P[i]] = 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:
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()))
L=list(set(L))
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:
import math
import functools

N = int(input())
A = [int(_) for _ in input().split()]
p = set([])

A.sort()

pairwise = True
for a in A:
    if a == 1:
        continue
    if pairwise is False:
        break
    for k in range(2, int(math.sqrt(a) + 1)):
        if a % k == 0:
            if k in p:
                pairwise = False
                break
            p.add(k)
            while a % k == 0:
                a //= k
    if pairwise and a > 1:
        p.add(a)

y = functools.reduce(math.gcd, A)

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

Submission status: Wrong Answer

Solution code:
import math
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr


N=int(input())
A=list(map(int,input().split()))
a=A[0]
for i in range(1,N):
    a=math.gcd(a,A[i])
if N>=78500 and a==1:
    print("setwise coprime")
elif N>=78500 and a>1:
    print("not coprime")
else:
    flag=True
    num_list=[0 for i in range(10000000)]
    for i in range(N):
        list_=factorization(A[i])
        for b,d in list_:
            if num_list[b]!=0:
                flag=False
            else:
                num_list[b]+=1
    if flag==True and a==1:
        print("pairwise coprime")
    elif flag==False and a==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

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

def fact(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

from collections import defaultdict
cntd=defaultdict(int)
for i in range(len(a)):
    lis = fact(a[i])
    for num,cnt in lis:
        if num==1:
            continue
        cntd[num]+=1

Submission status: Wrong Answer

Solution code:
from math import gcd 
n = int(input())
A = list(map(int,input().split()))
g = A[0]
pflag = True
for i in range(n-1):
  if gcd(A[i],A[i+1]) != 1:
    pflag = False
  g = gcd(g,A[i+1])
if g != 1:
  print("not coprime")
else:
  if pflag:
    print("pairwise coprime")
  else:
    print("setwise 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

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

A.reverse()
val = A[0]
flg = True
for i in range(1,N):
    if gcd(val,A[i]) != 1:
        flg = False
if flg == True:
    print('pairwise coprime')
    exit()





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

Submission status: Wrong Answer

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

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

pl = primes(1000)

def fact(n):
    arr = []
    temp = n
    for i in pl:
        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

import math

temp = []
dp = [0]*(10**6)
#pairwise
for i in range(n):
    for j in fact(al[i]):
        dp[j[0]] +=1

if max(dp)==1:
    print("pairwise coprime")

elif max(dp) ==n:
    print("not coprime")
    
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math


def gcd_muti(A):
    ans = A[0]
    for i in range(1, len(A)):
        ans = math.gcd(ans, A[i])
    return ans


def gcd_every(A):
    s = set()
    fucs = list(map(factorization, A))
    for fuc in fucs:
        for radix, _ in fuc:
            if radix in s:
                return False
            s.add(radix)
    return True


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

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

all_gcd = gcd_muti(A) == 1
every_gcd = gcd_every(A)

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

Submission status: Wrong Answer

Solution code:
import numpy as np
 
def prime(n):
    primes = np.zeros(n + 1, dtype=np.bool)
    primes[2] = 1
    primes[3::2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            primes[p * p::2 * p] = 0
    return primes
pp=prime(10**3)
p=[]
for i in range(2,1001):
  if pp[i]:
    p.append(i)
n=int(input())
a=list(map(int,input().split()))
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

g=a[0]
for i in a[1:]:
  g=gcd(g,i)
if g==1:
  m=[0 for i in range(1001)]
  mm=[0 for i in range(10**6+1)]
  f=True
  for i in a:
    if mm[i]:
      f=False
      break
    mm[i]=1
    for j in range(168):
      if i%p[j]:
        if m[j]:
          f=False
          break
        m[j]=1
    if not f:
      break
  if f:
    print("pairwise coprime")
  else:
    print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
def all_same(a):
    return all([x==a[0] for x in a])

def gcd(a,b):
	if b==0:
		return a
	else:
		return gcd(b,a%b)
		
N=int(input())
array=[int(x) for x in input().split()]
checklist=[]
totality=0
for i in array:
	totality=gcd(totality,i)

for i in range(N-1):
	checklist.append(gcd(array[i],array[i+1]))
if 1 in checklist and all_same(checklist):
	print("pairwise coprime")
elif totality==1:
	print("setwise coprime")
else:
	print("not coprime")

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, A_max+1):
    c = 0
    if dp[i] == 0:
        dp[i] = 1
        for j in range(i, A_max+1, 2):
            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:
import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
input=sys.stdin.readline
from random import randint
##import numpy as np
##sys.setrecursionlimit(10**7)
mo=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
##def gcd(a,b): 
##    if a == 0: 
##        return b 
##    return gcd(b % a, a)
prime1=[]
def SieveOfEratosthenes(n): #list of primes upto n
    global prime1
    prime1 = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime1[p] == True): 
            for i in range(p * p, n+1, p): 
                prime1[i] = False
        p += 1
    f=[]
    for p in range(2, n): 
        if prime1[p]: 
            f.append(p)
    return f

def lcm(a,b): 
    return (a*b) // math.gcd(a,b) 
for _ in range(1):
    n=inin()
    l=ain()
    f1,f2=0,0
    gc=lc=l[0]
    d=dd(int)
    lp=SieveOfEratosthenes(int(max(l)**(0.5)))
    for i in l:
        for j in lp:
            if(i%j==0):
                if(d[j]==1):
                    f1=1
                    break
                d[j]=1
        if(f1):break
    for i in range(1,n):
        gc=math.gcd(gc,l[i])
    if(gc!=1):print("not coprime")
    else:
        if(f1):
            print("setwise coprime")
        else:
            print("pairwise coprime")
        
        
    
    
    

 
    
    
    
    
        
        
    
    
    
    


    




##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo

Submission status: Wrong Answer

Solution code:
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
# print(p)
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 = 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:
from math import gcd
n=int(input())
a=list(map(int,input().split()))
a.sort()
lis=[False]*(10**6+1)
ok=True
s=set(a)
for num in range(2,10**6+1):
    if lis[num]:
        continue
    cnt=0
    for i in range(num,10**6+1,num):
        lis[i]=True
        if i in s:
            cnt+=1
    if cnt>=2:
        ok=False
if ok:
    print("pairwise coprime")
else:
    g=a[0]
    for num in a:
        g=gcd(g,num)
    if g==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

pl = eratosthenes(10**6)
pd = {}
for p in pl:
    pd[p] = 0

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


A.sort()

d = {}
ans = 0
if len(set(A)) != N:
    ans = 1
else:
    for i in range(N):
        if A[i] in d:
            ans = 1
            break
        if A[i] not in pd:
            primes = prime_decomposition(A[i])
            for p in primes:
                if p not in d:
                    for j in range(1,(10**6)//p+1):
                        d[j*p] = 0
                else:
                    ans = 1
                    break
        else:
            d[A[i]] = 0




if ans == 0:
    print('pairwise coprime')
else:
    def gcd(a, b):
    	while b:
    		a, b = b, a % b
    	return a
    a = A[0]
    for i in range(N):
        a = gcd(a,A[i])
    if a==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
def eratosthenes(mx, arr):
    sss = set(arr)
    if len(arr) > len(sss) or 1 in sss:
        print('not coprime')
        return
    array = [1 for _ in range(mx + 1)]
    array[0] = array[1] = 0
    pair_wise = True
    set_wise = True
    cnt = 0
    for i in range(2, mx+1, 2):
        array[i] = 0
        if i in sss:
            cnt += 1
    if cnt > 1:
        pair_wise = False
    if cnt == len(sss):
        set_wise = False

    for i in range(3, mx + 1, 2):
        if not array[i]:
            continue
        cnt = 0
        for j in range(i, mx + 1, i):
            array[j] = 0
            if i in sss:
                cnt += 1
        if cnt > 1:
            pair_wise = False
        if cnt == len(sss):
            set_wise = False
            break

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

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

    eratosthenes(max(a), a)

if __name__ == "__main__":
    resolve()