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:

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


N = int(input())
A = list(map(int, input().split()))
D = eratosthenes(max(A))
dic = {}
for i in A:
    while i != 1:
        if i in dic:
            dic[i] += 1
        else:
            dic[i] = 1
        i //= D[i]

isPairwise = True
isNowise = False
for i in dic.items():
    print(i)
    if i[1] > 1:
        isPairwise = False
    if i[1] >= N:
        isNowise = True

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

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class Sieve: #区間[2,n]の値の素因数分解 O(nloglogn+logn)
    def __init__(self,n): #nは計算対象としてありうる最大の値
        self.primes=[]
        self.f=[0]*(n+1) #ふるい（素数ならその値）
        self.f[0]=self.f[1]=-1
        self.f_lis = [0]*(n+1)
        self.max_f_lis = 0
        for i in range(2,n+1): #素数リスト作成
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,n+1,i):
                if not self.f[j]:
                    self.f[j]=i  #最小の素因数を代入
    def prime_fact(self,A): #素因数分解 {2:p,3:q,5:r,...}
        for x in A:
            while x!=1:
                p=self.f[x]
                x//=p
                if x % p > 0:
                    self.f_lis[p] += 1
                    self.max_f_lis = max(self.max_f_lis, self.f_lis[p])

import math
from functools import reduce
def gcd_all(*numbers):#gcd(*A)
    return reduce(math.gcd, numbers)

def main():
    n = int(input())
    A = list(map(int,input().split())) 
    if gcd_all(A) == 1:
        print("pairwise coprime")
    else:
        Sieve_a = Sieve(max(A)+1)
        Sieve_a.prime_fact(A)
        lis = Sieve_a.f_lis
        max_lis = Sieve_a.max_f_lis
        if max_lis == n:
            print("not coprime")
        else:
            print("setwise coprime")

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class Sieve: #区間[2,n]の値の素因数分解 O(nloglogn+logn)
    def __init__(self,n): #nは計算対象としてありうる最大の値
        self.primes=[]
        self.f=[0]*(n+1) #ふるい（素数ならその値）
        self.f[0]=self.f[1]=-1
        self.f_lis = [0]*(n+1)
        self.max_f_lis = 0
        for i in range(2,n+1): #素数リスト作成
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,n+1,i):
                if not self.f[j]:
                    self.f[j]=i  #最小の素因数を代入
    def prime_fact(self,x): #素因数分解 {2:p,3:q,5:r,...}
        while x!=1:
            p=self.f[x]
            x//=p
            if x % p > 0:
                self.f_lis[p] += 1
                self.max_f_lis = max(self.max_f_lis, self.f_lis[p])

def main():
    n = int(input())
    A = list(map(int,input().split())) 
    Sieve_a = Sieve(max(A)+1)
    for a in A:
        Sieve_a.prime_fact(a)
    lis = Sieve_a.f_lis
    max_lis = Sieve_a.max_f_lis
    if max_lis == n:
        print("not coprime")
    elif max_lis == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class Sieve: #区間[2,n]の値の素因数分解 O(nloglogn+logn)
    def __init__(self,n): #nは計算対象としてありうる最大の値
        self.primes=[]
        self.f=[0]*(n+1) #ふるい（素数ならその値）
        self.f[0]=self.f[1]=-1
        self.f_lis = [0]*(n+1)
        for i in range(2,n+1): #素数リスト作成
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,n+1,i):
                if not self.f[j]:
                    self.f[j]=i  #最小の素因数を代入
    def is_prime(self, x):
        return self.f[x]==x
    def prime_fact(self,x): #素因数分解 {2:p,3:q,5:r,...}
        while x!=1:
            p=self.f[x]
            x//=p
            if x % p > 0:
                self.f_lis[p] += 1

def main():
    n = int(input())
    A = list(map(int,input().split())) 
    Sieve_a = Sieve(max(A)+1)
    for a in A:
        Sieve_a.prime_fact(a)
    lis = Sieve_a.f_lis
    if max(lis) == n:
        print("not coprime")
    elif max(lis) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class Sieve2: #√nまでの素因数で試し割り 前処理O(√nloglogn+√n/logn)
    def __init__(self,n):
        self.primes=[]
        self.f=[0]*(int(n**0.5)+1) #ふるい（素数ならその値）
        self.f[0]=self.f[1]=-1
        for i in range(2,int(n**0.5)+1): #素数リスト作成
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,int(n**0.5)+1,i):
                if not self.f[j]:
                    self.f[j]=i  #最小の素因数を代入
    def prime_fact(self,x): #素因数分解 {2:p,3:q,5:r,...}
        fact_dict=dict()
        for p in self.primes:
            if p*p>x:break
            while x%p==0:
                x//=p
                fact_dict[p]=fact_dict.get(p,0)+1
        if x>1:fact_dict[x]=fact_dict.get(x,0)+1
        return fact_dict

def main():
    n = int(input())
    A = list(map(int,input().split())) 
    lis = [0] * (max(A)+1)
    Sieve_a = Sieve2(max(A)+1)
    for a in A:
        dic = Sieve_a.prime_fact(a)
        for d in dic.keys():
            lis[d] += 1
    if max(lis) == n:
        print("not coprime")
    elif max(lis) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class Sieve2: #√nまでの素因数で試し割り 前処理O(√nloglogn+√n/logn)
    def __init__(self,n):
        self.primes=[]
        self.f=[0]*(int(n**0.5)+1) #ふるい（素数ならその値）
        self.f[0]=self.f[1]=-1
        for i in range(2,int(n**0.5)+1): #素数リスト作成
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,int(n**0.5)+1,i):
                if not self.f[j]:
                    self.f[j]=i  #最小の素因数を代入
    def prime_fact(self,x): #素因数分解 {2:p,3:q,5:r,...}
        fact_dict=dict()
        for p in self.primes:
            if p*p>x:break
            while x%p==0:
                x//=p
                fact_dict[p]=fact_dict.get(p,0)+1
        if x>1:fact_dict[x]=fact_dict.get(x,0)+1
        return fact_dict

def main():
    n = int(input())
    A = list(map(int,input().split())) 
    lis = [0] * (max(A)+1)
    Sieve_a = Sieve2(max(A))
    for a in A:
        dic = Sieve_a.prime_fact(a)
        for d in dic.keys():
            lis[d] += 1
    if max(lis) == n:
        print("not coprime")
    elif max(lis) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
print("setwise coprime")

Submission status: Wrong Answer

Solution code:
print("not coprime")

Submission status: Wrong Answer

Solution code:
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:

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


N = int(input())
A = list(map(int, input().split()))
D = eratosthenes(max(A))
dic = {}
for i in A:
    while i != 1:
        if i in dic:
            dic[i] += 1
        else:
            dic[i] = 1
        i //= D[i]

isPairwise = True
isNowise = False
for i in dic.items():
    if i[1] > 1:
        isPairwise = False
    if i[1] == N:
        isNowise = True

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A= list(map(int, input().split()))
a=sorted(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, cnt])

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

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

    return arr
b=factorization(a[0])
Max=a[N-1]
S=0
for i in range(len(b)):
    c=[]
    d=Max//b[i][0]+1
    for _ in range (d):
        c.append(b[i][0]*_)
    s=1
    for j in range(len(a)):
        s*=c.count(a[j])
    if s==1:
        S+=1
if S>=1:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
A = 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
            arr.append([i, cnt])

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

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

    return arr

f_dict = defaultdict(int)

for a in A:
    fct = factorization(a)
    for a, _ in fct:
        f_dict[a] += 1

flag = True

for k, v in f_dict.items():
    if v == N:
        print('not coprime')
        exit()
    if v > 1:
        flag = False

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
MAX = pow(10,6)
#L = get_sieve_of_eratosthenes(MAX)
 
def factorization(n):
    arr = []
    temp = n
    if temp%2 == 0:
      cnt = 0
      while temp%2 == 0:
        cnt += 1
        temp//=2
      arr.append(2)
    for i in range(3, 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)
 
    return arr
 
#XX = factorization(121)
#print(XX)
import math
N = int(input())
A = list(map(int,input().split()))
GCD = math.gcd(A[0],A[1])
for i in range(2,N):
  GCD = math.gcd(GCD,A[i])
  if GCD == 1:
    break
if GCD != 1:
  print("not coprime")
  exit()
A.sort()
SET = set([])
for x in A:
  SL = factorization(x)
  for yakusu in SL:
    if yakusu not in SET:
      SET.add(yakusu)
    else:
      print("setwise coprime")
      #exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
MAX = pow(10,6)
#L = get_sieve_of_eratosthenes(MAX)
 
def factorization(n):
    arr = []
    temp = n
    if temp%2 == 0:
      cnt = 0
      while temp%2 == 0:
        cnt += 1
        temp//=2
      arr.append(2)
    for i in range(3, int(-(-n**0.5//1))+1,2):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
 
    if temp!=1:
        arr.append(temp)
 
    return arr
 
#XX = factorization(121)
#print(XX)
import math
N = int(input())
A = list(map(int,input().split()))
GCD = math.gcd(A[0],A[1])
for i in range(2,N):
  GCD = math.gcd(GCD,A[i])
  if GCD == 1:
    break
if GCD != 1:
  print("not coprime")
  exit()
A.sort()
SET = set([])
for x in A:
  SL = factorization(x)
  for yakusu in SL:
    if yakusu not in SET:
      SET.add(yakusu)
    else:
      print("setwise coprime")
      #exit()
print("pairwise 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:
    print("not comprime")
    exit()

MAXN = 10**6 + 9
D = [i for i in range(MAXN+1)]
p = 2
while(p*p <=MAXN):
    if D[p]==p:
        for q in range(2*p,MAXN+1,p):
            if D[q]==q:
                D[q]=p
    p+=1

st = set()
for a in A:
    tmp = set()
    while(a>1):
        tmp.add(D[a])
        a //=D[a]
    for p in tmp:
        if p in st:
            print("setwise coprime")
            exit()
        st.add(p)

print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7

n=I()
A=LI()
l=A[0]
num=[0]*(10**6+1)
for i in range(1,n):
    num[A[i]]+=1
    l=gcd(l,A[i])



if l!=1:
    print("not coprime")


for j in range(2,10**6):
    ret=0
    for k in range(j,10**6+1,j):
        ret+=num[k]
    if ret>1:
        print("setwise coprime")
        exit()

print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd   # gcd(6, 4) -> 2
from functools import reduce


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


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

c = max(A) + 1
D = [0] * c
div = [0] * c
P = []

for i in range(2, c):
    if D[i]==0:
        P.append(i)
        D[i] = i
    for j in P:
        if i * j >= c  or j > D[i] :
           break
        D[i*j] = j
f = 0
for i in A:
    if i == 1:
        continue
    temp = i
    while temp != 1:
        if div[D[temp]] == 1:
            f = 1
            break
        div[D[temp]] += 1
        temp2 = D[temp]
        while temp % temp2 == 0 and temp >= temp2:
            temp = temp // temp2
    if f == 1:
        break

if max(div) <= 1 and f == 0:
    print('pairwise coprime')

if gcd_list(A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

#main
MAX_A = 10**6+5     #Aの最大値10^6
n = int(input())
a = [int(x) for x in input().split()]
#各数が出てくる回数を保存
b = [0] * MAX_A
for i in range(n):
    b[a[i]] += 1

#pairwise判定
f = False
for i in range(2, MAX_A):   #0,1は除く
    c = 0
    #i=2ならj=2,4,6,8,...のようにiを因数に持つ数が何個あるかカウント
    for j in range(i, MAX_A, i):
        c += b[j]
        if c > 1:
            f = True
            break
    if f:
        break
    else:
        print('pairwise coprime')
        exit()

#setwise判定
g = 0
for ai in a:
    g = math.gcd(g, ai)
if g == 1:
    print('setwise coprime')
    exit()

#どちらでもない
print('not coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
divide_minimam_prime = [i for i in range(max(a) + 1)]
is_prime = [True for i in range(max(a) + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(2,int(max(a)**0.5) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= max(a):
            is_prime[k] = False
            if divide_minimam_prime[k] == k:
                divide_minimam_prime[k] = div
            k += div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(k)
        while k % divide_minimam_prime[k] == 0 and k > 1:
            k = k // divide_minimam_prime[k]
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math

#main
MAX_A = 10**6+5     #Aの最大値10^6
n = int(input())
a = [int(x) for x in input().split()]
b = [0] * MAX_A
c1 = 0
for i in range(n):
    #Aiに1が複数あった場合，下で判定できないので，ここで検出
    if a[i] == 1:
        c1 += 1
    if c1 > 1:
        print('pairwise coprime')
        exit()
    #各数が出てくる回数を保存
    b[a[i]] += 1


#pairwise判定
f = False
for i in range(2, MAX_A):   #0,1は除く
    c = 0
    #i=2ならj=2,4,6,8,...のようにiを因数に持つ数が何個あるかカウント
    for j in range(i, MAX_A, i):
        c += b[j]
        if c > 1:
            f = True
            break
    if f:
        break
    else:
        print('pairwise coprime')
        exit()

#setwise判定
g = 0
for ai in a:
    g = math.gcd(g, ai)
if g == 1:
    print('setwise coprime')
    exit()

#どちらでもない
print('not coprime')

Submission status: Wrong Answer

Solution code:
#ユークリッドの互除法
def gcd(a, b):
    if 0 == b:
        return a
    else:
        return gcd(b, a % b)

#main
MAX_A = 1000002     #Aの最大値10^6
n = int(input())
a = [int(x) for x in input().split()]
#各数が出てくる回数を保存
b = [0] * MAX_A
for ai in a:
    b[ai] += 1

#pairwise判定
f = False
for i in range(2, MAX_A):   #0,1は除く
    c = 0
    #i=2ならj=2,4,6,8,...のようにiを因数に持つ数が何個あるかカウント
    for j in range(i, MAX_A, i):
        c += b[j]
        if c >= 2:
            f = True
            break
    if f:
        break
    else:
        print('pairwise coprime')
        exit()

#setwise判定
g = 0
for ai in a:
    g = gcd(g, ai)
if g == 1:
    print('setwise coprime')
    exit()

#どちらでもない
print('not coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
divide_minimam_prime = [0 for i in range(max(a) + 1)]
is_prime = [True for i in range(max(a) + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(max(a) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= max(a):
            is_prime[k] = False
            if divide_minimam_prime[k] == 0:
                divide_minimam_prime[k] = div
            k += div
    else:
        if divide_minimam_prime[div] == 0:
            divide_minimam_prime[div] = div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    divnum_of_a = set()
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            divnum_of_a.add(divide_minimam_prime[k])
        k = k // divide_minimam_prime[k]
    use_divnum = use_divnum or divnum_of_a
if pairwise_coprime: 
    print("parwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
divide_minimam_prime = [0 for i in range(max(a) + 1)]
is_prime = [True for i in range(max(a) + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(max(a) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= max(a):
            is_prime[k] = False
            if divide_minimam_prime[k] == 0:
                divide_minimam_prime[k] = div
            k += div
    else:
        if divide_minimam_prime[div] == 0:
            divide_minimam_prime[div] = div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    divnum_of_k = set()
    while k != 1:
        divnum_of_k.add(divide_minimam_prime[k])
        k = k // divide_minimam_prime[k]
    if len(use_divnum and divnum_of_k) >= 2:
        pairwise_coprime = False
        break
    else:
        use_divnum = use_divnum or divnum_of_k
if pairwise_coprime: 
    print("parwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
divide_minimam_prime = [0 for i in range(max(a) + 1)]
is_prime = [True for i in range(max(a) + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(max(a) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        while k <= max(a):
            is_prime[k] = False
            if divide_minimam_prime[k] == 0:
                divide_minimam_prime[k] = div
            k += div
    else:
        if divide_minimam_prime[div] == 0:
            divide_minimam_prime[div] = div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    while k != 1:
        if divide_minimam_prime[k] in use_divnum :
            pairwise_coprime = False
            break
        else:
            use_divnum.add(divide_minimam_prime[k])
            k = k // divide_minimam_prime[k]
if pairwise_coprime : 
    print("parwise coprime")
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    pr = [0]*(max(a)+1)
    flag = True
    for num in a:
        pr[num] += 1
    for i in range(2, max(a)+1):
        count = sum(pr[i::i])
        if count == N:
            print("not coprime")
        elif count > 1:
            flag = False
    if flag:
        print("pairwise coprime")
    else:
        print("setwise coprime")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

from math import gcd

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

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

primes = set()

flag = 1

for i in a:
    prime_factors = prime_factorize(i)
    for j in prime_factors:
        if j in primes:
            flag = 0
            break

if flag:
    print('pairwise coprime')
    sys.exit()
            
 
import math
from functools import reduce
 
def gcd(*numbers):
    return abs(reduce(math.gcd, numbers))
 
if gcd(*a) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

from math import gcd

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

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

primes = set()

flag = 1

for i in a:
    prime_factors = prime_factorize(i)
    for j in prime_factors:
        if j in primes:
            flag = 0
            break

if flag:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
num = list(map(int, input().split()))
#N = 10**6
#num = list(range(1, N+1))

MAXX = 10**6 + 1
MAXZ = int(math.sqrt(MAXX)+1)
furui = [[] for _ in range(MAXX)]

furui[1].append(1)
count = [0]*MAXX
for i in range(2, MAXZ):
    if len(furui[i]) == 0:
        for k in range(i, MAXX, i):
            furui[k].append(i)

setwise = True
pairwise = True
for i in range(N):
    if not setwise and not pairwise: break
    for fu in furui[num[i]]:
        count[fu] += 1
        if fu > 1 and count[fu] >= N:
            setwise = False
            pairwise = False
            break
        elif fu > 1 and count[fu] > 1:
            pairwise = False

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
import math
a=A[0]
for i in range(1,N):
  a=math.gcd(a,A[i])
def f():
  a=A[0]
  for i in range(1,N):
    a=math.gcd(a,A[i])
  if a==1:
    print("setwise prime")
    exit()
  else:
    print("not coprime")
    exit()
  
D=[0]*(10**6+1)
for i in range(2,10**6+1):
  for j in range(2*i,10**6+1,i):
    if D[j]==0:
      D[j]=i
for i in range(10**6+1):
  if D[i]==0:
    D[i]=i

s=set()
import copy
for i in range(N):
  tmp=set()
  k=A[i]
  while k>1:
    tmp.add(D[k])
    k=k//D[k]
  for i in tmp:
    if i in s:
      f()
    else:
      s.add(i)


print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
num = list(map(int, input().split()))
#N = 10**6
#num = list(range(1, N+1))

MAXX = 10**6 + 1
MAXZ = int(math.sqrt(MAXX)+1)
furui = [[] for _ in range(MAXX)]

furui[1].append(1)
count = [0]*MAXX
for i in range(2, MAXZ):
    if len(furui[i]) == 0:
        for k in range(i, MAXX, i):
            furui[k].append(i)

setwise = True
pairwise = True
for i in range(N):
    if not setwise and not pairwise: break
    for fu in furui[num[i]]:
        count[fu] += 1
        if count[fu] >= N:
            setwise = False
            pairwise = False
            break
        elif count[fu] > 1:
            pairwise = False

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

Submission status: Wrong Answer

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

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

li = [0] * 10**6
flag = True
flag2 = True

b = list(set(a))
if len(b) != len(a):
    flag = False

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

for i in a:
    li2 = factorization(i)
    for x,y in li2:
        li[x] += 1


for i in li[2:]:
    if i == len(b):
        flag2 = False
    elif i >= 2:
        flag = False

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

Submission status: Wrong Answer

Solution code:
from math import sqrt
N = int(input())
Alist = list(map(int,input().split()))
Aprimes = []
isPC = True
isSC = False
#import time
# import random
# Alist = [random.randint(1,1000000) for i in range(1000000)]
#tt = time.time()

#print(time.time() - tt)
# make primelist
primelist = list(range(1,int(sqrt(max(Alist)))+1))
for n in primelist:
    if n >1:
        for m in range(n*2,len(primelist),n):
            primelist[m-1]=1
primelist=list(set(primelist))


def get_prime(a):
    primes = []
    for p in primelist[1:]:
        if p>a:
            break
        elif a%p == 0:
            primes.append(p)
    return primes

# print(time.time() - tt)
for a in Alist:
    p = get_prime(a)
    # if len(p)>1:
    Aprimes.append(p)
# print(time.time() - tt)

factors = []
cofactors = Aprimes[0]
# cofactors.remove(1)
for a in Aprimes:
    for p in a:
        if p in factors:
            isPC = False
        else:
            factors.append(p)
    for f in cofactors.copy():
        if f not in a:
            cofactors.remove(f)


if isPC:
    print('pairwise coprime')
elif len(cofactors)>0:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:

def gen_factorization(N):
    tables=[-1]*(N+1)
    for i in range(2,N+1):
        if tables[i]!=-1:continue
        tmp=i
        while tmp<=N:
            tables[tmp]=i
            tmp+=i
    def fuctorization(n):
        if n==1:return {1:1}
        elif n<0:n=abs(n)
        if n>N:return "error"
        ans={}
        while n!=1:
            tmp=tables[n]
            #debug print
            #print(tmp,n)
            ans.setdefault(tmp,0)
            ans[tmp]+=1
            n//=tmp
        return ans
    return fuctorization

N=int(input())
f=gen_factorization(10**6+10)
A=list(map(int,input().split()))
primes={}
for i in A:
  d=f(i)
  for j in d:
    primes.setdefault(j,0)
    primes[j]+=1
primes[1]=0
ansMax=max(primes.values())

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

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
A = [int(i) for i in input().split()]
a = math.gcd(A[0],A[1])
for i in range(len(A)-2):
  a = math.gcd(a,A[i+2])
if a > 1:
  print("not coprime")
  exit()
l = int(max(A)**(0.5))+1
L = [0]*l
for i in range(2,l):
  if L[i] == 1:
    continue
  for j in range(2,(l+1)//i):
    L[i*j] = 1
pn = []
for i in range(2,l):
  if L[i] == 0:
    pn.append(i)
for p in pn:
  n = 0
  for a in A:
    if a%p == 0:
      n += 1
  if n > 1:
    print("setwise coprime")
    exit()
print("pairwise coprime")