Problem: 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.

Submission attempts (in order):
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

#            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')

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')

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')

from functools import reduce
from math import gcd

N=int(input())
A=list(map(int, input().split()))
c=10**6+1
C=[0]*c
f=1
for i in A:
    C[i]+=1

for i in range(2,c):
    cnt=0
    for j in range(i,c,i):
        cnt+=C[j]
    if cnt>1:
        f=0


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

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

else:
    print('not coprime')

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')

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')

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')

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')

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 and i>D[j]:
           break
        D[i*j]=j

for i in A:
    c=gcd(c,i)
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        div[temp]+=1
        continue
    while temp!=D[temp]:
        div[D[temp]]+=1
        temp=temp//D[temp]

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

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

else:
    print('not coprime')

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')

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
    while temp!=1:
        div[D[temp]]+=1
        temp2=D[temp]
        while temp%temp2==0 and temp>=temp2:
            print(temp)
            temp=temp//temp2


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

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

else:
    print('not coprime')

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
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 f==0:
    print('pairwise coprime')

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

else:
    print('not coprime')

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Time Limit Exceeded

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Accepted