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


def prime_factorize(n):
    r = set()
    if n % 2 == 0:
        r.add(2)
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.add(n)
    return collections.Counter(r)


a1 = collections.Counter([])
a2 = prime_factorize(A[0])
for a in A:
    tmp = prime_factorize(a)

Submission status: Wrong Answer

Solution code:

import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret


n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)

bp=enum_div(amin)+[amin]
bp=bp[1:]
for bpi in bp:
    lap=len([ai for ai in ap if ai%bpi==0])
    if lap==n:
        print("not coprime")
        sys.exit()

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,1009]


ptype="pairwise coprime"
for pp in p:
    lap=len([ai for ai in ap if ai%pp==0])
#    print("pp:",pp,lap)
#    if lap==n:
#        ptype="not coprime"
#        print("not coprime")
#        break
    if lap>=2:
#        if ptype!="not coprime":
        ptype="setwise coprime"

print(ptype)

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    if a < b:
        a, b = b, a
    c = 1
    while c != 0:
        c = a % b
        a = b
        b = c
    return a


numbers = [[] for i in range(10**6 + 1)]
flag = [True for i in range(10**6 + 1)]
for i in range(2, 10**3 + 1):
    if flag[i]:
        for j in range(2, 10**6 + 1):
            if i * j > 10**6:
                break
            flag[i * j] = False
            numbers[i * j].append(i)
N = int(input())
alist = list(map(int, input().split()))
adict = {}
flag = False
for a in alist:
    if a == 1:
        continue
    temp = numbers[a]
    if temp == []:
        temp = [a]
    for i in temp:
        if i not in adict:
            adict[i] = 0
        else:
            flag = True
            break
    if flag:
        break

if not flag:
    print("pairwise coprime")
    exit(0)

temp = gcd(alist[0], alist[1])
for a in alist[2:]:
    temp = gcd(temp, a)
    if temp == 1:
        print("setwise coprime")
        exit(0)

print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
A = list(map(int, input().split()))
MAX = 10**6


def prime_factor_sieve(n):
    """
    エラトステネスの篩で、
    2 ~ Nの各数に対して、その整数のもつ最小の素因数
    (その整数を篩落とした最小の素因数)を記録して返す
    O(nloglog(n))
    """
    res = [i for i in range(n+1)]
    for i in range(2, int(n**0.5)+1):
        if res[i] < i:
            continue
        for j in range(i*i, n+1, i):
            if res[j] == j:
                res[j] = i
    return res

def factorization(n, min_factor):
    """
    エラトステネスの篩で手に入れた、各整数の最小素因数のリスト
    からO(log(n))で素因数分解する
    """
    res = set()
    while n > 1:
        res.add(min_factor[n])
        n //= min_factor[n]
        # 割った後の素因数についてもO(1)で参照できる
    return res

# 素因数が重複しているかを調べる
min_factor = prime_factor_sieve(MAX)
res = set()
is_ok = 1
for a in A:
    if a == 1:
        continue
    tmp = factorization(a, min_factor)
    if res & tmp:
        is_ok = 0
        break
    res = factorization(a, min_factor)
if is_ok:
    print("pairwise coprime")
else:
    g = A[0]
    for i in range(1, N):
        g = gcd(g, A[i])
    if 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()))
MAX = 10**6


def prime_factor_sieve(n):
    """
    エラトステネスの篩で、
    2 ~ Nの各数に対して、その整数のもつ最小の素因数
    (その整数を篩落とした最小の素因数)を記録して返す
    O(nloglog(n))
    """
    res = [i for i in range(n+1)]
    for i in range(2, int(n**0.5)+1):
        if res[i] < i:
            continue
        for j in range(i*i, n+1, i):
            if res[j] == j:
                res[j] = i
    return res

def factorization(n, min_factor):
    """
    エラトステネスの篩で手に入れた、各整数の最小素因数のリスト
    からO(log(n))で素因数分解する
    """
    res = set()
    while n > 1:
        res.add(min_factor[n])
        n //= min_factor[n]
        # 割った後の素因数についてもO(1)で参照できる
    return res

# 素因数が重複しているかを調べる
min_factor = prime_factor_sieve(MAX)
res = set()
is_ok = 1
for a in A:
    tmp = factorization(a, min_factor)
    if res & tmp:
        is_ok = 0
        break
    res = factorization(a, min_factor)
if is_ok:
    print("pairwise coprime")
else:
    g = A[0]
    for i in range(1, N):
        g = gcd(g, A[i])
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
import random
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
sa=set(a)
ans=[]
era=[1]*(10**6+1)
era[0]=0
ca=Counter(a)

k=2
while k<(10**6+1)**0.5+1:
  if era[k]==1:
    for i in range(k,10**6+1,k):
      if i!=k:
        era[i]=0
      if i in sa:
        ans.append(k)
  if k==2:
    k+=1
  else:
    k+=2

pflag=True
if len(ans)!=len(set(ans)):
  pflag=False

for i in ca:
  if i!=1 and ca[i]>=2:
    pflag=False
    break
  
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

def is_prime(n):
  if n==1:
    return False
  if n==2:
    return True
  else:
    for i in range(2,int(math.sqrt(n))+1):
      if n%i==0:
        return False
    return True
  
check=set()
for i in range(n):
  if is_prime(a[i]):
    check.add(a[i])
  
if setwise_coprime(a)==1:
  s=erast(1000)
  s.sort()
  for i in range(n):
    if a[i]!=1:
      for j in range(len(s)):
        if a[i]%s[j]==0:
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
            
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import math as m

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


D=[0]*(10**6+1)
for i in range(2,int(m.sqrt(10**6))+2):
    if D[i]!=0:
        continue
    j=2*i
    while j < 10**6+1:
        D[j]=i
        j+=i

P=[0]*10**6
pc=True
g=As[0]
for n in range(N):
    A=As[n]
    if A==1:
        continue
    ppre=1
    while True:
        p=D[A] if D[A]!=0 else A
        if ppre != p:
            if P[p] > 0:
                pc=False
            P[p]+=1
            ppre=p
        A=A//p
        if A==1:
            break
    g=m.gcd(g,A)

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

Submission status: Wrong Answer

Solution code:
import math as m

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


D=[0]*(10**6+1)
for i in range(2,int(m.sqrt(10**6))+2):
    if D[i]!=0:
        continue
    j=2*i
    while j < 10**6+1:
        D[j]=i
        j+=i

P=[0]*10**6
pc=True
g=As[0]
for n in range(N):
    A=As[n]
    ppre=1
    while True:
        p=D[A] if D[A]!=0 else A
        if ppre != p:
            if P[p] > 0:
                pc=False
            P[p]+=1
            ppre=p
        A=A//p
        if A==1:
            break
    g=m.gcd(g,A)

if pc:
    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()))

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

check=set()
if setwise_coprime(a)==1:
  s=erast(1100)
  s.sort()
  for i in range(n):
    if a[i]!=1:
      for j in range(len(s)):
        if a[i]%s[j]==0:
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict

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

S=[0]*(max(A)+1)
E=int(math.sqrt(N))
S[1]=1
for i in range(2,max(A)+1):
    if S[i]==0:
        for j in range(i,max(A)+1,i):
            if S[j]==0:
                S[j]=i

p=True
s=defaultdict(lambda:False)
for i in range(0,N):
#    print(A[i],S[A[i]])
    if s[S[A[i]]]==True:
        p=False
        break
    s[S[A[i]]]=True

gcd=A[0]
for i in range(1,N):
    gcd=math.gcd(gcd, A[i])

if p:
    print('pairwise coprime')
else:
    if gcd==1:
        print('setwise coprime')
    else:
        print('not coprime')
#print(S)

Submission status: Wrong Answer

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


def prime_factorize(n):
    r = set()
    while n % 2 == 0:
        r.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.add(n)
    return r


d = [0]*10**6
ans = prime_factorize(A[0])
for a in A:
    tmp = prime_factorize(a)

Submission status: Wrong Answer

Solution code:
import math
(_,), a  = [list(map(int, s.split())) for s in open(0)]

def fast_factorize(num):
    min_factor_list = list(range(num + 1))
    for i in range(int(math.sqrt(num) + 1), 1, -1):
        for j in range(i, num+1, i):
            min_factor_list[j] = i
    return min_factor_list

min_factor_list = fast_factorize(max(a))

prime_factor_sets = []
for x in a:
    prime_factor_set = set()
    while min_factor_list[x] != 1:
        prime_factor_set.add(min_factor_list[x])
        x //= min_factor_list[x]
    prime_factor_sets.append(prime_factor_set)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

INF = 10**6

def min_primes(n):
  ret = [i for i in range(n+1)]
  for i in range(2, int(n**0.5)+1):
    if ret[i] < i:
      continue
    for j in range(i, n+1, i):
      ret[j] = min(i, ret[j])
  return ret

D = min_primes(INF)
Ps = defaultdict(int)

def fact(x):
  Ps[D[x]] += 1
  pre = x
  x //= D[x]
  while x > 1:
    if D[x] > D[pre]:
      Ps[D[x]] += 1
    pre = x
    x //= D[x]

for a in A:
  fact(a)

cnt = max(Ps.values())

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

Submission status: Wrong Answer

Solution code:

n=int(input())
ap=list(map(int,input().split()))
    
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,1009]


ptype="pairwise coprime"
for pp in p:
    lap=len([ai for ai in ap if ai%pp==0])
#    print("pp:",pp,lap)
    if lap==n:
        ptype="not coprime"
#        print("not coprime")
        break
    elif lap>=2:
        if ptype!="not coprime":
            ptype="setwise coprime"

#if ptype=="not coprime":    
#    print("not coprime")
#elif ptype=="setwise coprime":    
#    print("setwise coprime")
#else:    
#    print("pairwise coprime")
print(ptype)

Submission status: Wrong Answer

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

check=set()
if setwise_coprime(a)==1:
  s=erast(1100)
  s.sort()
  for i in range(n):
    for j in range(len(s)):
      if a[i]==1:
        break
        
      if a[i]%s[j]==0:
        if s[j] in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(s[j])
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
sa=set(a)
ans=[]
era=[1]*(10**6+1)
era[0]=0
ca=Counter(a)

k=2
while k<(10**6+1)**0.5+1:
  if era[k]==1:
    for i in range(k,10**6+1,k):
      if i!=k:
        era[i]=0
      if i in sa:
        for t in range(ca[i]):
          ans.append(k)
  if k==2:
    k+=1
  else:
    k+=2

pflag=True
if len(ans)!=len(set(ans)):
  pflag=False



if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:

n=int(input())
ap=list(map(int,input().split()))
    
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,1009]


ptype=""
for pp in p:
    lap=len([ai for ai in ap if ai%pp==0])
#    print("pp:",pp,lap)
    if lap==n:
        ptype="not coprime"
#        print("not coprime")
        break
    elif lap>=2:
        if ptype!="not coprime":
            ptype="setwise coprime"

if ptype=="not coprime":    
    print("not coprime")
if ptype=="setwise coprime":    
    print("setwise coprime")
else:    
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    if a < b:
        a, b = b, a
    c = 1
    while c != 0:
        c = a % b
        a = b
        b = c
    return a


numbers = [[] for i in range(10**6 + 1)]
flag = [True for i in range(10**6 + 1)]
for i in range(2, 2 * 10**3):
    if flag[i]:
        for j in range(2, 10**6 + 1):
            if i * j > 10**6:
                break
            flag[i * j] = False
            numbers[i * j].append(i)
N = int(input())
alist = list(map(int, input().split()))
adict = {}
flag = False
for a in alist:
    if a == 1:
        continue
    temp = numbers[a]
    if temp == []:
        temp = [a]
    for i in temp:
        if i not in adict:
            adict[i] = 0
        else:
            flag = True
            break
    if flag:
        break

if not flag:
    print("pairwise coprime")
    exit(0)

temp = gcd(alist[0], alist[1])
for a in alist[2:]:
    temp = gcd(temp, a)
    if temp == 1:
        print("setwise coprime")
        exit(0)

print("not coprime")

Submission status: Wrong Answer

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans==1

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

check=set()
if setwise_coprime(a):
  s=erast(1100)
  s.sort()
  for i in range(n):
    for j in range(len(s)):
      if a[i]==1:
        break
      if s[j]>a[i]:
        break
      if a[i]%s[j]==0:
        if s[j] in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(s[j])
  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()))

am = max(a)

memo = [1] * (am+1)
memo[0] = 0
memo[1] = 0

d = set([])

for ai in range(2, am+1):
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0

cs = set([])
for i, memoi in enumerate(memo):
    if memoi:
        cs.add(i)

# print(cs)


f1 = 1
f2 = 1

for ai in a:
    lim = int(ai**0.5)+1
    f0 = 0
    if ai in cs:
        if ai in d:
            f0 = 1
        else:
            d.add(ai)
    else:  
        for i in cs:
            if i >= lim:
                break
            if ai % i == 0:
                if i in d or ai//i in d:
                    f1 = 0
                    f0 = 1
                    break
                else:
                    d.add(i)
                    d.add(ai//i)
    if f0:
        break


if f1:
    print('pairwise coprime')
else:
    g = a[0]
    for ai in a:
        g = gcd(ai, g)
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    min_pri = [i for i in range(10**6+1)]
    ps = []
    for i in range(2,10**3):
        if min_pri[i] != i:
            continue
        else:
            ps.append(i)
            for j in range(i,10**6+1,i):
                if min_pri[j] == j:
                    min_pri[j] = i

    a = [int(i) for i in ipt().split()]
    g = a[0]
    d = defaultdict(bool)
    f1 = True
    for i in a:
        g = math.gcd(g,i)
        if f1 and i != 1:
            ni = i
            pi = bisect.bisect_left(ps,min_pri[i])
            for j in ps[pi::]:
                ff = True
                while ni%j == 0:
                    if ff:
                        if d[j]:
                            f1 = False
                            break
                        d[j] = True
                        ff = False
                    ni //= j
                if not f1 or ni == 1:
                    break
            if ni != 1:
                d[ni] = True

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




    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans==1

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

check=set()
if setwise_coprime(a):
  s=erast(1100)
  s.sort()
  for i in range(n):
    for j in range(len(s)):
      if s[j]>a[i]:
        break
      if a[i]%s[j]==0:
        if s[j] in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(s[j])
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Wrong Answer

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans==1

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

check=set()
if setwise_coprime(a):
  s=erast(1000)
  s.sort()
  for i in range(n):
    for j in range(168):
      if s[j]>a[i]:
        break
      if a[i]%s[j]==0:
        if s[j] in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(s[j])
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

INF = 10**6

def min_primes(n):
  ret = [i for i in range(n+1)]
  ret[1] = 1
  for i in range(2, int(n**0.5)+1):
    if ret[i] < i:
      continue
    for j in range(i, n+1, i):
      ret[j] = min(i, ret[j])
  return ret

D = min_primes(INF)
Ps = defaultdict(int)

def fact(x):
  Ps[D[x]] += 1
  pre = x
  x //= D[x]
  while x > 1:
    if D[x] > D[pre]:
      Ps[D[x]] += 1
    pre = x
    x //= D[x]

for a in A:
  fact(a)

cnt = max(Ps.values())

if cnt == N:
  print("not coprime")
elif cnt > 1:
  print("setwise coprime")
else:
  print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    min_pri = [i for i in range(10**6+1)]
    ps = []
    for i in range(2,10**3):
        if min_pri[i] != i:
            continue
        else:
            ps.append(i)
            for j in range(i,10**6+1,i):
                if min_pri[j] == j:
                    min_pri[j] = i

    a = [int(i) for i in ipt().split()]
    g = a[0]
    d = defaultdict(bool)
    f1 = True
    for i in a:
        g = math.gcd(g,i)
        if f1:
            ni = i
            pi = bisect.bisect_left(ps,min_pri[i])
            for j in ps[pi::]:
                ff = True
                while ni%j == 0:
                    if ff:
                        if d[j]:
                            f1 = False
                            break
                        d[j] = True
                        ff = False
                    ni //= j
                if not f1 or ni == 1:
                    break
                else:
                    d[ni] = True

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




    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
sa=set(a)
ans=[]
era=[1]*(10**6+1)
era[0]=0
ca=Counter(a)

k=2
while k<(10**6+1)**0.5+1:
  if era[k]==1:
    
    for i in range(k,10**6+1,k):
      if i!=k:
        era[i]=0
      if i in sa:
        for t in range(ca[k]):
          ans.append(k)
  if k==2:
    k+=1
  else:
    k+=2

pflag=True
if len(ans)!=len(set(ans)):
  pflag=False
  
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from collections import Counter


def gcd(a, b):
    if a < b:
        a, b = b, a
    c = 1
    while c != 0:
        c = a % b
        a = b
        b = c
    return a


numbers = [[] for i in range(10**6 + 1)]
flag = [True for i in range(10**6 + 1)]
for i in range(2, 10**3 + 1):
    if flag[i]:
        for j in range(2, 10**6 + 1):
            if i * j > 10**6:
                break
            flag[i * j] = False
            numbers[i * j].append(i)
N = int(input())
alist = list(map(int, input().split()))
adict = {}
flag = False
for a in alist:
    temp = numbers[a]
    if temp == []:
        temp = [a]
    for i in temp:
        if i not in adict:
            adict[i] = 0
        else:
            flag = True
            break
    if flag:
        break

if not flag:
    print("pairwise coprime")
    exit(0)

temp = gcd(alist[0], alist[1])
for a in alist[2:]:
    temp = gcd(temp, a)
    if temp == 1:
        print("setwise coprime")
        exit(0)

print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys

n=int(input())
ap=list(map(int,input().split()))
    
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,1009]

for pp in p:
    lap=len([ai for ai in ap if ai%pp==0])
#    print("pp:",pp,lap)
    if lap==n:
        print("not coprime")
        sys.exit()
    elif lap>=2:
        print("setwise coprime")
        sys.exit()
    
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
sa=set(a)
ans=[]
era=[1]*(10**6+1)
era[0]=0
ca=Counter(a)

k=2
while k<(10**6+1)**0.5+1:
  if era[k]==1:
    
    for i in range(k,10**6+1,k):
      if i!=k:
        era[i]=0
      if i in sa:
        for k in range(ca[k]):
          ans.append(k)
  if k==2:
    k+=1
  else:
    k+=2

pflag=True
if len(ans)!=len(set(ans)):
  pflag=False
  
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
sa=set(a)
ans=[]
era=[1]*(10**6+1)
era[0]=0
ca=Counter(a)
print(ca)

k=2
while k<(10**6+1)**0.5+1:
  if era[k]==1:
    
    for i in range(k,10**6+1,k):
      if i!=k:
        era[i]=0
      if i in sa:
        for k in range(ca[k]):
          ans.append(k)
  if k==2:
    k+=1
  else:
    k+=2

pflag=True
if len(ans)!=len(set(ans)):
  pflag=False
print(ans)
  
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict

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

am = max(a)

memo = [1] * (am+1)
memo[0] = 0
memo[1] = 0

d = defaultdict(int)

for ai in range(2, am+1):
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0

cs = []
for i, memoi in enumerate(memo):
    if memoi:
        cs.append(i)

# print(cs)


f1 = 1
f2 = 1

for ai in a:
    f0 = 0
    for i in cs:
        if ai % i == 0:
            d[i] += 1
            if i != ai // i:
                d[ai//i] += 1
            if d[i] > 1 or d[ai//i] > 1:
                f1 = 0
                f0 = 1
                break
    if f0:
        break


if f1:
    print('pairwise coprime')
else:
    g = a[0]
    for ai in a:
        g = gcd(ai, g)
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')