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 functools import reduce
from math import gcd

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

for i in A:
    if i==1:
        continue
    temp=i
    pt=[]
    while temp!=1:
        div[D[temp]]+=1
        temp2=D[temp]
        while temp%temp2==0 or temp!=1:
            temp=temp//temp2

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

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
def searchPrimeNum(N):
    max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

plis = searchPrimeNum(10**3+1)
N = int(input())
d = [0]*(10**6)
A = [int(i) for i in input().split()]


#素因数分解(素数列挙が必要)
def pfact(N):
    #素数列挙
    for p in plis:
        if N%p == 0:
            d[p] += 1
            N = N//p
        while N%p == 0:
            N = N//p
        if N == 1:
            break
    if N != 1:
        d[N] += 1

for a in A:
    pfact(a)
m = max(d)
if m == 1:
    print("pairwise coprime")
elif m == N:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:

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

plis = searchPrimeNum(10**3+1)
N = int(input())
d = {p:0 for p in plis}
A = [int(i) for i in input().split()]


#素因数分解(素数列挙が必要)
def pfact(N):
    #素数列挙
    for p in plis:
        if N%p == 0:
            d[p] += 1
            N = N//p
        while N%p == 0:
            N = N//p
        if N == 1:
            break
    if N != 1:
        if N in d.keys():
            d[N] += 1
        else:
            d[N] = 1
    return 0

for a in A:
    pfact(a)
m = max(d.values())
if m == 1:
    print("pairwise coprime")
elif m == N:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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

for i in A:
    if i==1:
        continue
    temp=i
    pt=[]
    while temp!=1:
        if D[temp] not in pt:
            div[D[temp]]+=1
        pt.append(D[temp])
        temp=temp//D[temp]

if max(div)==1:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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

for i in A:
    if i==1:
        continue
    temp=i
    pt=[]
    while temp!=1:
        if temp not in pt:
            div[D[temp]]+=1
        pt.append(D[temp])
        temp=temp//D[temp]

#print(div)

if max(div)==1:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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

for i in A:
    if i==1:
        continue
    temp=i
    pt=[]
    while temp!=1:
        if temp not in pt:
            div[D[temp]]+=1
        pt.append(D[temp])
        temp=temp//D[temp]

print(div)

if max(div)==1:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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
g=c
f=0
for i in A:
    if i==1:
        continue
    temp=i
    pt=[]
    while temp!=1:
        if D[temp] not in pt:
            pt.append(D[temp])
            div[D[temp]]+=1
        temp=temp//D[temp]

#print(div)

if max(div)==1:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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
g=c
f=0
for i in A:
    if i==1:
        continue
    temp=i
    pt=[]
    while temp!=1:
        if temp==D[temp] and temp not in pt: 
            div[D[temp]]+=1
            break
        if D[temp] not in pt:
            pt.append(D[temp])
            div[D[temp]]+=1
        temp=temp//D[temp]

if max(div)==1:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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
g=c
f=0
for i in A:
    if i==1:
        continue
    temp=i
    pt=[]
    if temp==D[temp]:
        if div[D[temp]]>=1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=1:
        if div[D[temp]]>=1 and temp not in pt:
            f=1
            break
        div[D[temp]]+=1
        pt.append(D[temp])
        temp=temp//D[temp]
    if f==1:
        break


if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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
g=c
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]>=1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]>=1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]
    div[temp]+=1

    if f==1:
        break


if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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
g=c
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]>=1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]>=1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]
    if div[temp]>=1:
        f=1
        break

    div[temp]+=1

    if f==1:
        break


if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd
import sys
sys.setrecursionlimit(10**8)
global f


def chk(a):
    global f
    if a==D[a]:
        if div[D[a]]>=1:
            f=1
            return 
        div[D[a]]+=1
        return
    while a!=D[a]:
        if div[D[a]]>=1:
            f=1
            return
        div[D[a]]+=1
        chk(a//D[a])
    if a!=D[a] and a in P:
        if div[a]>=1:
            f=1
            return
        div[a]+=1


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
g=c
f=0
for i in A:
    if i==1:
        continue
    chk(i)
    if f==1:
        break



if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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
g=c
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]>=1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]>=1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]
    if temp in P:
        div[temp]+=1

    if f==1:
        break


if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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
g=c
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]>=1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]>=1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]
    if temp in P:
        div[temp]+=1
        
    if f==1:
        break

print(div)

if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
prime=[[] for _ in range(1000000+1)]

for i in range(2,1000000+1):
    if prime[i]==[]:
        for j in range(i,1000000+1,i):
            prime[j].append(i)
n=eval(input())
lis=[]
trs=list(map(int,input().split()))
for m in trs:
    lis.append(prime[m])
check=[]
dic={}
for i in range(n):
    flag=True
    for _ in lis[i]:
        if _ in check:
            flag=False
            if _ in dic.keys():
                dic[_]+=1
            else:
                dic[_]=1
        else:
            check.append(_)
if flag==False:    
    c=max(dic.values())
    if c==n-1:
        print('not coprime')
    else:
        print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Wrong Answer

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

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

#高速素因数分解

#エラストテネスのふるい
#sieveが0なら素数、0以外ならその値を割り切る素数
def create_sieve(n):
  sieve=[0]*(n+1)
  for i in range(2,n+1):
    if sieve[i]==0:
      for j in range(i*i,n+1,i):
        sieve[j]=i
  return sieve
#素因数分解
#dicではkey=素数、value=何乗か
def prime(n):
  sieve=create_sieve(n)
  dic={}
  while(1):
    if sieve[n]==0:
      dic[n]=dic.get(n,0)+1
      break
    else:
      p=sieve[n]
      dic[p]=dic.get(p,0)+1
      n=n//p
  return dic

def setwise(a):
  l=a[0]
  for i in range(len(a)):
    l=gcd(l,a[i])
  return l==1


if setwise(a):
  check=set()
  for num in a:
    dic=prime(num)
    for j in dic:
      if j in check:
        print("setwise coprime")
        exit()
      else:
        check.add(j)
  print("pairwise coprime")
  
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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
g=c
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]
    if f==1:
        break
    if temp!=D[temp] and temp in P:
        div[temp]+=1


if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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
g=c
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]
    if f==1:
        break
    print(temp)
    if temp!=D[temp] and temp in P:
        div[temp]+=1

print(div)

if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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
g=c
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]
    if div[temp]==1:
        f=1
        break
    if f==1:
        break
    div[temp]+=1

if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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
g=c
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]
    div[temp]+=1
    if f==1:
        break
if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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
g=c
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]
    if div[D[temp]]==1:
            f=1
            break
    if f==1:
        break

if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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-1  or j>D[i] :
           break
        D[i*j]=j
g=A[0]
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]
    if f==1:
        break

if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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

c=10**6+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-1  or j>D[i] :
           break
        D[i*j]=j
g=A[0]
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]
    if f==1:
        break

if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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

c=10**6+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-1  or j>D[i] :
           break
        D[i*j]=j
g=A[0]
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]

if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd

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

c=10**6+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-1  or j>D[i] :
           break
        D[i*j]=j
g=A[0]
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        div[D[temp]]+=1
        temp=temp//D[temp]

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

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

c=10**6+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-1  or j>D[i] :
           break
        D[i*j]=j
g=A[0]
for i in A:
    g=gcd(g,i)
    if i==1:
        continue
    temp=i
    
    if temp==D[temp]:
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        div[D[temp]]+=1
        temp=temp//D[temp]

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

elif g==1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

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

maxV = (10 ** 6 + 1)

sieve = [i for i in range(maxV)]
p = 2

while p*p < maxV:
    if sieve[p] == p:
        for q in range(p*2, maxV, p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1

from math import gcd

g = 0
primes = set()
for a in A:
    g = gcd(g, a)

    v = a


if g > 1:
    print('not coprime')
    exit()

for a in A:
    temp_prime = set()
    while a > 1:
        prime = sieve[a]
        temp_prime.add(prime)
        a = a // prime

    for t in temp_prime:
        if t in primes:
            print('setwise coprime')
            exit()

print('pairwise coprime')

Submission status: Wrong Answer

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

maxV = (10 ** 6 + 1)

sieve = [i for i in range(maxV)]
p = 2

while p*p < maxV:
    if sieve[p] == p:
        for q in range(p*2, maxV, p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1

from math import gcd

g = 0
primes = set()
for a in A:
    g = gcd(g, a)

    v = a


if g > 1:
    print('not coprime')
    exit()

for a in A:
    while a > 1:
        prime = sieve[a]
        if prime in primes:
            print('setwise coprime')
            exit()
        primes.add(prime)
        a = a // prime

print('pairwise coprime')

Submission status: Wrong Answer

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

maxV = (10 ** 6 + 1)

sieve = [i for i in range(maxV)]
p = 2

while p*p < maxV:
    if sieve[p] == p:
        for q in range(p*2, maxV, p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1

from math import gcd

g = 0
primes = set()
for a in A:
    g = gcd(g, a)

    v = a
    

if g > 1:
    print('not coprime')
    exit()

for a in A:
    while a > 1:
        prime = sieve[a]
        if prime in primes:
            print('pairwise coprime')
            exit()
        primes.add(prime)
        a = a // prime

print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n, *a = map(int, read().split())

    maxa = max(a) + 1  # aはint配列
    d = [i for i in range(maxa)]
    for p0 in range(2, maxa):
        if p0 == d[p0]:
            for p1 in range(p0 ** 2, maxa, p0):
                if d[p1] % p0 == 0:
                    d[p1] = p0

    def factorization(f):  # f > maxaだとエラー
        l = []
        t = f
        while True:
            if t == d[t]:
                l.append(d[t])
                break
            else:
                l.append(d[t])
                t = t // d[t]
        return l

    if all([i == 1 for i in a]):
        print('pairwise coprime')
        sys.exit()
    if len(set(a)) == 1:
        print('not coprime')
        sys.exit()
    d1 = defaultdict(int)
    for ae in a:
        t1 = set(factorization(ae))
        for t1e in t1:
            d1[t1e] += 1
    d1v = tuple(d1.values())
    if all([i == 1 for i in d1v]):
        print('pairwise coprime')
    elif max(d1v) == n:
        print('not coprime')
    else:
        print('setwise coprime')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n, *a = map(int, read().split())

    maxa = max(a) + 1  # aはint配列
    d = [i for i in range(maxa)]
    for p0 in range(2, maxa):
        if p0 == d[p0]:
            for p1 in range(p0 ** 2, maxa, p0):
                if d[p1] % p0 == 0:
                    d[p1] = p0

    def factorization(f):  # f > maxaだとエラー
        l = []
        t = f
        while True:
            if t == d[t]:
                l.append(d[t])
                break
            else:
                l.append(d[t])
                t = t // d[t]
        return l

    if all([i == 1 for i in a]):
        print('pairwise coprime')
    d1 = defaultdict(int)
    for ae in a:
        t1 = set(factorization(ae))
        for t1e in t1:
            d1[t1e] += 1
    d1v = tuple(d1.values())
    if all([i == 1 for i in d1v]):
        print('pairwise coprime')
    elif max(d1v) == n:
        print('not coprime')
    else:
        print('setwise coprime')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd

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

c=10**6+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-1  or j>D[i] :
           break
        D[i*j]=j
f=0
for i in A:
    c=gcd(c,i)
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        div[temp]+=1
    while temp!=D[temp]:
        div[D[temp]]+=1
        if div[temp]>=2:
            f=1
        temp=temp//D[temp]

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

elif c==1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
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

setC = dict()

not_pairwise = False
fs = []
for a in A:
    f = factorization(a)

    vs = set()
    for v, n in f:
        if v in setC:
            not_pairwise = True
        setC.update({v:n})
        vs.add(v)


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

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


if not not_pairwise:
    print('pairwise coprime')
elif g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

c=10**6+1
D=[0]*(c+1)
div=[0]*(c+1)
P=[]

for i in range(2,c+1):
    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:
    c=gcd(c,i)
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        div[temp]+=1
    while temp!=D[temp]:
        div[D[temp]]+=1
        if div[temp]>=2:
            f=1
        temp=temp//D[temp]

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

elif c==1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n, *a = map(int, read().split())

    maxa = max(a) + 1  # aはint配列
    d = [i for i in range(maxa)]
    for p0 in range(2, maxa):
        if p0 == d[p0]:
            for p1 in range(p0 ** 2, maxa, p0):
                if d[p1] % p0 == 0:
                    d[p1] = p0

    def factorization(f):  # f > maxaだとエラー
        l = []
        t = f
        while True:
            if t == d[t]:
                l.append(d[t])
                break
            else:
                l.append(d[t])
                t = t // d[t]
        return l

    d1 = defaultdict(int)
    for ae in a:
        t1 = set(factorization(ae))
        for t1e in t1:
            d1[t1e] += 1

    d1v = tuple(d1.values())
    if all([i == 1 for i in d1v]):
        print('pairwise coprime')
    if max(d1v) == n:
        print('not coprime')
    else:
        print('setwise coprime')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd

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

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

for i in range(2,c+1):
    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 c>1:
        c=gcd(c,i)
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        div[temp]+=1
#        if div[temp]>=2:
#            f=1
#        continue
    while temp!=D[temp]:
        div[D[temp]]+=1
        if div[temp]>=2:
            f=1
        temp=temp//D[temp]
#    if c==1 and f==1:
#        break

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

elif c==1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

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

for i in range(2,c+1):
    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 c>1:
        c=gcd(c,i)
    if i==1:
        continue
    temp=i
    print(temp,D[temp])
    if temp==D[temp]:
        div[temp]+=1
#        if div[temp]>=2:
#            f=1
#        continue
    while temp!=D[temp]:
        div[D[temp]]+=1
        if div[temp]>=2:
            f=1
        temp=temp//D[temp]
#    if c==1 and f==1:
#        break

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

elif c==1:
    print('setwise coprime')

else:
    print('not coprime')