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):
n=int(input())
import copy
a=list(map(int,input().split()))
q=copy.copy(a)
m=10**6
tab=[0]*(m+1)
for aa in a:
  tab[aa]=1
for i in range(2,m+1):
  cnt=0
  for j in tab[i::i]:
    cnt+=j
  if cnt>1:
    break
else:
  print('pairwise coprime')
  exit()
from math import gcd
g=gcd(q[0],q[1])
if n==2:
  print('setwise coprime' if g==1 else 'not coprime')
  exit()
for i in range(2,n):
  g=gcd(g,q[i])
if g==1:
  print('setwise coprime')
else:
  print('not coprime')


n=int(input())
import copy
a= [int(x) for x in input().split()]
MAX_A = 10 ** 6 + 1
histogram = [0] * MAX_A
for x in a:
  histogram[int(x)] = 1
for divider in range(2, MAX_A):
  count = 0
  for counted in histogram[divider::divider]:
    count += counted
  if count > 1:
    break
else:
  print('pairwise coprime')
  exit()
from math import gcd
g=gcd(a[0],a[1])
if n==2:
  print('setwise coprime' if g==1 else 'not coprime')
  exit()
for i in range(2,n):
  g=gcd(g,a[i])
if g==1:
  print('setwise coprime')
else:
  print('not coprime')


n=int(input())
import copy
a=list(map(int,input().split()))
q=copy.copy(a)
l=[]
prime=[True]*(max(a)+1)
prime[0]=False
prime[1]=False
for i in range(2,int(max(a)**0.5)+1):
  if prime[i]:
    for j in range(i*2,max(a)+1,i):
      prime[j]=False
primetab=[i for i in range(max(a)+1) if prime[i]]
for i in range(n):
  b=i**0.5
  ll=[]
  for j in primetab:
    if a[i]%j==0:
      ll.append(j)
      a[i]//=j
  if a[i]>b:
    l.append(a[i])
  l+=ll
x=len(l)
y=len(set(l))
if x==y:
  print('pairwise coprime')
  exit()
from math import gcd
g=gcd(q[0],q[1])
if n==2:
  print('setwise coprime' if g==1 else 'not coprime')
  exit()
for i in range(2,n):
  g=gcd(g,q[i])
if g==1:
  print('setwise coprime')
else:
  print('not coprime')


n=int(input())
import copy
a=list(map(int,input().split()))
q=copy.copy(a)
l=[]
prime=[True]*(max(a)+1)
prime[0]=False
prime[1]=False
for i in range(2,int(max(a)**0.5)+1):
  if not prime[i]:
    continue
  for j in range(i*2,max(a)+1,i):
    prime[j]=False
primetab=[i for i in range(max(a)+1) if prime[i]]
for i in range(n):
  b=i**0.5
  ll=[]
  for j in primetab:
    if a[i]%j==0:
      ll.append(j)
      a[i]//=j
  if a[i]>b:
    l.append(a[i])
  l+=ll
x=len(l)
y=len(set(l))
if x==y:
  print('pairwise coprime')
  exit()
from math import gcd
g=gcd(q[0],q[1])
if n==2:
  print('setwise coprime' if g==1 else 'not coprime')
  exit()
for i in range(2,n):
  g=gcd(g,q[i])
if g==1:
  print('setwise coprime')
else:
  print('not coprime')

n=int(input())
l=list(map(int,input().split()))
m=max(l)

from math import gcd
g=gcd(l[0],l[1])
for i in range(2,n):
  g=gcd(g,l[i])
if g!=1:
  print('not coprime')
  exit()

prime=[True]*(m+1)
prime[0]=False
prime[1]=False
d=[0]*(m+1)
for i in range(2,int(m**0.5)+1):
  if prime[i]:
    for j in range(i*2,m+1,i):
      prime[j]=False
      d[j]=i
s=[i for i in range(m+1) if prime[i]]
for ss in s:
  d[ss]=ss

sl=set()
for i in range(n):
  div=set()
  ll=l[i]
  while ll>1:
    div.add(d[ll])
    ll//=d[ll]
  div=list(div)
  for dd in div:
    if dd not in sl:
      sl.add(dd)
    else:
      print('setwise coprime')
      exit()

print('pairwise coprime')

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted