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:
# 自然数m以下の素数を返す（SETでRETURN）
import math
def prime_numbers(m):
    # 素数を保持するset
    primes = []

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.append(n)
        n += 1
    return primes

#素数で割れるか、同じ素数で何回割れるかは見てないから素因数分解とは違う（10**6まで）
def soinsu_bunkai(m):
    pf=set()

    for i in pri_num:
        if i >m:
            break
        elif m%i==0:
            pf.add(i)

    return pf

    # 初期入力
import sys
from collections import Counter
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
intersect =set()
pair_w =set()

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
pri_num =prime_numbers(sq_pri )

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    for a in A:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            pair_w.add(0)
            break #共通要素があったらpair_wではない→set_w
        else:
            pair_w.add(1)
        intersect |=aa

    if 0 in pair_w:
        ans ="setwise coprime"        
    else:
        ans ="pairwise coprime"
print(ans)

Submission status: Wrong Answer

Solution code:
# 自然数m以下の素数を返す（SETでRETURN）
import math
def prime_numbers(m):
    # 素数を保持するset
    primes = []

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.append(n)
        n += 1
    return primes

#素数で割れるか、同じ素数で何回割れるかは見てないから素因数分解とは違う（10**6まで）
def soinsu_bunkai(m):
    pf=set()

    for i in pri_num:
        if i >m:
            break
        elif m%i==0:
            pf.add(i)

    return pf

    # 初期入力
import sys
from collections import Counter
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
intersect =set()
pair_w =set()

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
pri_num =prime_numbers(sq_pri +15)

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    for a in A:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            pair_w.add(0)
            break #共通要素があったらpair_wではない→set_w
        else:
            pair_w.add(1)
        intersect |=aa

    if 0 in pair_w:
        ans ="setwise coprime"        
    else:
        ans ="pairwise coprime"
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

D = [i for i in range(1000001)]

for i in range(2,1001):
    if D[i] == i:
        for j in range(2,1+100000//i):
            D[i*j] = i

###
#print(D[:10])
###

det = 1
P = []

for a in A:
    Q = []
    aa = a
    while aa > 1:
        Q.append(D[aa])
        aa //= D[aa]
    P = P + list(set(Q))
    ###
    #print(P)
    #print(Q)
    ###

if len(P) == len(set(P)):
    print('pairwise coprime')

else:
    g = A[0]
    for i in range(1,N):
        g = math.gcd(g,A[i])
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
'''
なんで通らないのかわからん
Xの値もしかして間違ってた？
'''


import sys
import math

X = 1000

prime = []

for i in range(2,X+1):
    det = 0
    for j in range(2,int(i**(1/2))+1):
        if i%j==0:
            det = -1
            break
    if det == 0:
        prime.append(i)

#print(prime)
#print(len(prime))

N = int(input())
A = list(map(int,input().split()))
B = []###Aのうち1ではないもの
det = False###Aが1を含んでいたか否か

for i in range(N):
    if A[i] == 1:
        det = True
    else:
        B.append(A[i])

#print(det)
#print(B)

###len(B)は10^6以下の素数の数よりも少なくなければならない
if len(B) <= 100000 and len(B) == len(set(B)):

    m = 1

    ### 1000以上の素数は素因数として高々1個しかないことを利用できる
    ### が、同じ素数単体が複数あったらアウト
    for p in prime:
        count = 0
        for b in B:
            if b%p==0:
                count += 1
        m = max(m,count)
        #print(p,count,m)
        if m >= 2:
            break
    
    if m == 1:
        print('pairwise coprime')
        sys.exit(0)

if det:
    print('setwise coprime')

else:
    g = A[0]
    for i in range(1,N):
        g = math.gcd(g,A[i])
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
print('setwise coprime')

Submission status: Wrong Answer

Solution code:
'''
なんで通らないのかわからん
Xの値もしかして間違ってた？
'''


import sys
import math

X = 1000

prime = []

for i in range(2,X+1):
    det = 0
    for j in range(2,int(i**(1/2))+1):
        if i%j==0:
            det = -1
            break
    if det == 0:
        prime.append(i)

#print(prime)
#print(len(prime))

N = int(input())
A = list(map(int,input().split()))
B = []###Aのうち1ではないもの
det = False###Aが1を含んでいたか否か

for i in range(N):
    if A[i] == 1:
        det = True
    else:
        B.append(A[i])

#print(det)
#print(B)

if len(B) <= 78498 and len(B) == len(set(B)):

    m = 1

    ### 1000以上の素数は素因数として高々1個しかないことを利用できる
    ### が、同じ素数単体が複数あったらアウト
    for p in prime:
        count = 0
        for b in B:
            if b%p==0:
                count += 1
        m = max(m,count)
        #print(p,count,m)
        if m >= 2:
            break
    
    if m == 1:
        print('pairwise coprime')
        sys.exit(0)

if det:
    print('setwise coprime')

else:
    g = A[0]
    for i in range(1,N):
        g = math.gcd(g,A[i])
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
# 自然数m以下の素数を返す（SETでRETURN）
import math
def prime_numbers(m):
    # 素数を保持するset
    primes = []

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.append(n)
        n += 1
    return primes

#素因数分解（10**6まで）
def soinsu_bunkai(m):
    pf=set()

    for i in pri_num:
        if i >m:
            break
        elif m%i==0:
            pf.add(i)

    return pf

    # 初期入力
import sys
from collections import Counter
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
intersect =set()
used =set()
pair_w =set()
set_w =set()

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
pri_num =prime_numbers(sq_pri +10)

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    for a in A:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            pair_w.add(0)
            break #共通要素があったらpair_wではない→set_w
        else:
            pair_w.add(1)
        intersect |=aa

    if 0 in pair_w:
        ans ="setwise coprime"        
    else:
        ans ="pairwise coprime"
print(ans)

Submission status: Wrong Answer

Solution code:
# 自然数m以下の素数を返す（SETでRETURN）
import math
def prime_numbers(m):
    # 素数を保持するset
    primes = []

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.append(n)
        n += 1
    return primes

#素因数分解（10**6まで）
def soinsu_bunkai(m):
    pf=set()

    for i in pri_num:
        if i >m:
            break
        elif m%i==0:
            pf.add(i)

    return pf

    # 初期入力
import sys
from collections import Counter
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
pri_num =prime_numbers(sq_pri +10)

intersect =set()
used =set()
pair_w =set()
set_w =set()

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    for a in A:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            pair_w.add(0)
            break
        else:
            pair_w.add(1)
        intersect |=aa

    if 1 in pair_w and 0 not in pair_w:
        ans ="pairwise coprime"
    else:
        ans ="setwise coprime"
print(ans)

Submission status: Wrong Answer

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


def main():
    N = int(input())
    A = [int(i) for i in input().split()]

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

    if not g == 1:
        print('not coprime')
        return


    limit = int(10 ** 3)
    F = [0] * (10 ** 6 + 1)
    M = [0] * (10 ** 6 + 1)
    for i in range(2, limit + 1):
        if F[i] > 0:
            continue
        v = 2 * i
        while v <= 10 ** 6:
            if F[v] == 0:
                F[v] = i
            v += i

    pc = True
    for v in A:
        S = set()
        x = v
        while True:
            if F[x] > 0:
                S.add(F[x])
                x //= F[x]
            else:
                S.add(x)
                break

        for s in S:
            if M[s] == 1:
                pc = False
                break
            M[s] += 1

        if not pc:
            break

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


def run_prime_factorization(max_number: int) -> dict:
    '''Run prime factorization.
    Args:
        max_number: Int of number (greater than 1).
    Returns:
        A dictionary's items ((base, exponent) pairs).
    Landau notation: O(log n)
    '''

    from math import sqrt

    ans = dict()
    remain = max_number

    for base in range(2, int(sqrt(max_number)) + 1):
        if remain % base == 0:
            exponent_count = 0

            while remain % base == 0:
                exponent_count += 1
                remain //= base

            ans[base] = exponent_count

    if remain != 1:
        ans[remain] = 1

    return ans


def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    numbers = [0 for _ in range(10 ** 6 + 1)]

    for ai in a:
        p = run_prime_factorization(ai)

        if p:
            for key, value in p.items():
                numbers[key] += 1
        else:
            numbers[1] += 1

    if numbers[1] == n:
        print("pairwise coprime")
    elif max(numbers) == 1:
        print("pairwise coprime")
    elif max(numbers) == n:
        print("not coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
def Ii():return int(sys.stdin.readline().rstrip())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))
n = Ii()
a = Li()
sc = 0
pc = 1
b = a[0]
for i in range(n-1):
  b %= a[i+1]
  g = math.gcd(b,a[i+1])
  b *= a[i+1]
  if(g > 1):
    pc = 0
    break
    
g = math.gcd(a[0],a[1])
for i in range(n-2):
  g = math.gcd(g,a[i+2])
  if(g == 1):
    sc = 1

if(pc):
  ans = 'pairwise coprime'
elif(sc):
  ans = 'setwise coprime'
else:
  ans = 'not coprime'
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
def Ii():return int(sys.stdin.readline().rstrip())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))
n = Ii()
a = Li()
sc = 0
pc = 1
b = a[0]
for i in range(n-1):
  b %= a[i+1]
  #if(b == 0): b += a[i+1]
  g = math.gcd(b,a[i+1])
  b *= a[i+1]
  if(g != 1):
    pc = 0

g = math.gcd(a[0],a[1])
if(sc == 0):
  for i in range(n-2):
    g = math.gcd(g,a[i+2])
    if(g == 1):
      sc = 1

if(pc):
  ans = 'pairwise coprime'
elif(sc):
  ans = 'setwise coprime'
else:
  ans = 'not coprime'
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
def Ii():return int(sys.stdin.readline().rstrip())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))
n = Ii()
a = Li()
sc = 0
pc = 1
b = a[0]
for i in range(n-1):
  b %= a[i+1]
  if(b == 0): b += a[i+1]
  g = math.gcd(b,a[i+1])
  b *= a[i+1]
  if(g != 1):
    pc = 0

g = math.gcd(a[0],a[1])
if(sc == 0):
  for i in range(n-2):
    g = math.gcd(g,a[i+2])
    if(g == 1):
      sc = 1

if(pc):
  ans = 'pairwise coprime'
elif(sc):
  ans = 'setwise coprime'
else:
  ans = 'not coprime'
  
print(ans)

Submission status: Wrong Answer

Solution code:
def li():
    return [int(x) for x in input().split()]

N = int(input())
A = li()

import math
from functools import reduce
from collections import defaultdict

# 最大公約数（リスト引数）
# 空のリストを渡さないよう注意
def GCD_list(numbers):
    return reduce(math.gcd, numbers)



# 数列全ての高速素因数分解
MAX = 10 ** 6
is_prime = [True] * (MAX + 1)
divs = [1] * (MAX + 1)
is_prime[0], is_prime[1] = False, False
i = 1
while i * i <= MAX:
    if not is_prime[i]:
        i += 1
        continue
    for j in range(2 * i, MAX + 1, i):
        is_prime[j] = False
        divs[j] = i
    i += 1

pairwise_coprime = False
all_primes = defaultdict(int)
for k in range(N):
    n = A[k]
    p = divs[n]
    primes = defaultdict(int)
    while p > 1:
        primes[p] += 1
        n = n // p
        p = divs[n]
    # 最後に残った数は1か素数にしかならない
    if n != 1:
        primes[n] += 1
    for key in primes:
        if all_primes[key] > 0 and primes[key] > 0:
            pairwise_coprime = True
            break
        all_primes[key] += primes[key]

gcd = GCD_list(A)
setwise_comprime = (gcd == 1)

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

Submission status: Wrong Answer

Solution code:
import sys
import math
def Ii():return int(sys.stdin.readline().rstrip())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))
n = Ii()
a = Li()
sc = 0
pc = 1
b = a[0]
for i in range(n-1):
  b %= a[i+1]
  if(b == 0): b += a[i+1]
  g = math.gcd(b,a[i+1])
  b *= a[i+1]
  if(g == 1):
    sc = 1
  if(g != 1):
    pc = 0

g = math.gcd(a[0],a[1])
if(sc == 0):
  for i in range(n-2):
    g = math.gcd(g,a[i+2])
    if(g == 1):
      sc = 1

if(pc):
  ans = 'pairwise coprime'
elif(sc):
  ans = 'setwise coprime'
else:
  ans = 'not coprime'
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
def Ii():return int(sys.stdin.readline().rstrip())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))
n = Ii()
a = Li()
sc = 0
pc = 1
b = a[0]
for i in range(n-1):
  b %= a[i+1]
  b += a[i+1]
  g = math.gcd(b,a[i+1])
  b *= a[i+1]
  if(g == 1):
    sc = 1
  if(g != 1):
    pc = 0

g = math.gcd(a[0],a[1])
if(sc == 0):
  for i in range(n-2):
    g = math.gcd(g,a[i+2])
    if(g == 1):
      sc = 1

if(pc):
  ans = 'pairwise coprime'
elif(sc):
  ans = 'setwise coprime'
else:
  ans = 'not coprime'
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
def Ii():return int(sys.stdin.readline().rstrip())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))
n = Ii()
a = Li()
sc = 0
pc = 1
b = a[0]
for i in range(n-1):
  b %= a[i+1]
  g = math.gcd(b,a[i+1])
  b *= a[i+1]
  if(g == 1):
    sc = 1
  if(g != 1):
    pc = 0

g = math.gcd(a[0],a[1])
if(sc == 0):
  for i in range(n-2):
    g = math.gcd(g,a[i+2])
    if(g == 1):
      sc = 1

if(pc):
  ans = 'pairwise coprime'
elif(sc):
  ans = 'setwise coprime'
else:
  ans = 'not coprime'
  
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
A=list(map(int,input().split()))
ans=A[0]
X=[0]*(max(A)+1)
def div(x):
    if x%2==0:
        x//=2
        if X[2]!=0:
            return False
        else:
            X[2]+=1
    for i in range(3,int(x**0.5)+1,2):
        if x%i==0:
            x//=i
            if X[i]!=0:
                return False
            else:
                X[i]+=1
    return True



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

if ans!=1:
    print('not coprime')
else:
    ans='pairwise coprime'
    for a in A:
        if not div(a):
            ans='setwise coprime'
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
idx = list(range(n))
d = list(a) 
lim = int(max(a)**0.5)+1

for i in range(2, lim):
  idxbef = list(idx)
  for j in idxbef:
    if a[j]%i == 0:
      d[j]=i
      idx.remove(j)
print(d)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
k=10**6+1
def judge(n,a):
  c=[0]*k
  for x in a:
    c[x]=+1
  t=any(sum(c[i::i])>1 for i in range(2,k))
  t+=reduce(math.gcd,a)>1
  return ['pairwise','setwise','not'][t]+' coprime'
n=int(input())
a=list(map(int,input().split()))
print(judge(n,a))

Submission status: Wrong Answer

Solution code:
import math,sys

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


ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n=int(math.sqrt(10**6))+20
count=[0 for _ in range(max_n)]

def fac(x):
    for i in range(2,int(math.sqrt(x))+10):
        if x%i ==0:
            if count[i]==1:
                return False
            else:
                count[i]+=1
    return True
flag=True
for each in Ns:
    flag_2=fac(each)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
    sys.exit()

gcd_ans=Ns[0]
for i in range(1,n):
    gcd_ans= math.gcd( gcd_ans , Ns[i])

if gcd_ans==1:
    print(ans_s)
else:
    print(ans_n)

Submission status: Wrong Answer

Solution code:
import math,sys

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


ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n=int(math.sqrt(10**6))+20
count=[0 for _ in range(max_n)]

def fac(x):
    for i in range(2,int(math.sqrt(x))+10):
        if x%i ==0:
            if count[i]==1:
                return False
            else:
                count[i]+=1
    return True
print(fac(4),count)
flag=True
for each in Ns:
    flag_2=fac(each)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
    sys.exit()

gcd_ans=Ns[0]
for i in range(1,n):
    gcd_ans= math.gcd( gcd_ans , Ns[i])

if gcd_ans==1:
    print(ans_s)
else:
    print(ans_n)

Submission status: Wrong Answer

Solution code:
import math,sys

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


ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n=int(math.sqrt(10**6))+1
count=[0 for _ in range(max_n)]

def fac(x):
    for i in range(2,int(math.sqrt(x))+1):
        if x%i ==0:
            if count[i]==1:
                return False
            else:
                count[i]+=1
    return True

flag=True
for each in Ns:
    flag_2=fac(each)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
    sys.exit()

gcd_ans=Ns[0]
for i in range(1,n):
    gcd_ans= math.gcd( gcd_ans , Ns[i])

if gcd_ans==1:
    print(ans_s)
else:
    print(ans_n)

Submission status: Wrong Answer

Solution code:
import math,sys

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


ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n=int(math.sqrt(10**6))+1
count=[0 for _ in range(max_n)]

def fac(x,T):
    for i in range(2,int(math.sqrt(x))+1):
        if x%i ==0:
            if count[i]==1:
                return False
            else:
                count[i]+=1
    return True

flag=True
for each in Ns:
    flag_2=fac(each,count)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
    sys.exit()

gcd_ans=Ns[0]
for i in range(1,n):
    gcd_ans= math.gcd( gcd_ans , Ns[i])

if gcd_ans==1:
    print(ans_s)
else:
    print(ans_n)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
l=list(map(int,input().split()))
su=1
for values in l:
    su=su*values
lcm=1
gcc=l[0]
for values in l:
    gc=math.gcd(lcm,values)
    gcc=math.gcd(gcc,values)
    lcm=(lcm*values)//gc;
# print(gcc)
# print(lcm)
# print(su)
if lcm==su and gcc==1:
    print("pairwise prime")
elif lcm!=su and gcc==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)
    N = 1000001
    f = [1]*N
    lis = []
    p = 2
    while p < N:
        while p < N and not f[p]:
            p += 1
        j = p
        lis.append(p)
        while j < N:
            f[j] = 0
            j += p
    def func(n):
        i = 0
        p = lis[i]
        if n < 2:
            return 0
        if n < 4:
            if c[n]:
                return 1
            c[n] = 1
        while p*p <= n:
            print(p,n)
            if n%p == 0:
                if c[p]:
                    return 1
                c[p] = 1
                while n%p == 0:
                    n //= p
            i += 1
            p = lis[i]
        c[n] = 1
        return 0
    n = I()
    a = LI()
    g = a[0]
    for i in a[1:]:
        g = gcd(g,i)
    if g != 1:
        print("not coprime")
        return
    c = [0]*N
    for i in a:
        if func(i):
            print("setwise coprime")
            return
    print("pairwise coprime")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)
    N = 1000001
    f = [1]*N
    lis = []
    p = 2
    while p < N:
        while p < N and not f[p]:
            p += 1
        j = p
        lis.append(p)
        while j < N:
            f[j] = 0
            j += p
    def func(n):
        i = 0
        p = lis[i]
        if n < 2:
            return 0
        if n < 4:
            if c[n]:
                return 1
            c[n] = 1
        while p*p <= n:
            if n%p == 0:
                if c[p]:
                    return 1
                c[p] = 1
                while n%p == 0:
                    n //= p
            i += 1
            p = lis[i]
        return 0
    n = I()
    a = LI()
    g = a[0]
    for i in a[1:]:
        g = gcd(g,i)
    if g != 1:
        print("not coprime")
        return
    c = [0]*N
    for i in a:
        if func(i):
            print("setwise coprime")
            return
    print("pairwise coprime")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)
    N = 1000001
    f = [1]*N
    lis = []
    p = 2
    while p < N:
        while p < N and not f[p]:
            p += 1
        j = p
        lis.append(p)
        while j < N:
            f[j] = 0
            j += p
    def func(n):
        i = 0
        p = lis[i]
        if n < 2:
            return 0
        if n < 4:
            if c[n]:
                return 1
        while p*p <= n:
            if n%p == 0:
                if c[p]:
                    return 1
                c[p] = 1
            i += 1
            p = lis[i]
        return 0
    n = I()
    a = LI()
    g = a[0]
    for i in a[1:]:
        g = gcd(g,i)
    if g != 1:
        print("not coprime")
        return
    c = [0]*N
    for i in a:
        if func(i):
            print("setwise coprime")
            return
    print("pairwise coprime")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
Alist = list(map(int,input().split()))
box = [0]*(N+1)
sign = math.gcd(Alist[0],Alist[1])
Amax = max(Alist[0],Alist[1])
for i in range(0,len(Alist)):
    A = Alist[i]
    sign = math.gcd(sign, A)
    Amax = max(Amax, A)
    box[i] += 1
setwise = (sign == 1)
pairwise = (sign == 1)
Amax = math.sqrt(Amax)+1
for i in range(2,10**6+1):
    if sum(box[i::i]) >1:
        pairwise = False
        break
if setwise:
    if pairwise:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
Answer = 'pairwise coprime'
N = int(input())
Alist = list(map(int,input().split()))
sign = math.gcd(Alist[0],Alist[1])
Aset = set()
Bset = set()
def factorization(n):
    arr = set()
    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.add(i)

    if temp!=1:
        arr.add(temp)

    if arr==[]:
        arr.add(n)

    return arr
Alist = deque(Alist)
sig =1
A = Alist.popleft()
An = factorization(A)
Aset = An
Bset = An
for _ in range(len(Alist)):
    A = Alist.popleft()
    An =  factorization(A)
    if Aset & An == set():
        Aset = Aset | An
    else:
        Answer ='setwise coprime'
        sign = math.gcd(A,sign)
        break
    sign = math.gcd(A,sign)
for _ in range(len(Alist)):
    A = Alist.popleft()
    sign = math.gcd(A,sign)
if sign != 1 and Answer == 'setwise coprime':
    Answer = 'not corprime'
print(Answer)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
Answer = 'pairwise coprime'
N = int(input())
Alist = list(map(int,input().split()))
sign = math.gcd(Alist[0],Alist[1])
Aset = set()
Bset = set()
def factorization(n):
    arr = set()
    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.add(i)

    if temp!=1:
        arr.add(temp)

    if arr==[]:
        arr.add(n)

    return arr
Alist = deque(Alist)
sig =1
A = Alist.popleft()
An = factorization(A)
Aset = An
Bset = An
for _ in range(len(Alist)):
    A = Alist.popleft()
    An =  factorization(A)
    if Aset & An == set():
        Aset = Aset | An
    else:
        Answer ='setwise coprime'
    sign = math.gcd(A,sign)          
if sign != 1 and Answer == 'setwise coprime':
    Answer = 'not corprime'
print(Answer)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
Answer = 'not coprime'
N = int(input())
Alist = list(map(int,input().split()))
sign = math.gcd(Alist[0],Alist[1])
for i in range(1,N):
    sign = math.gcd(sign,Alist[i])
if sign == 1:
    Answer = 'setwise coprime'
Aset = set()
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
Alist = deque(Alist)
sig =1
if Answer == 'setwise coprime':
    for _ in range(len(Alist)):
        if sig ==0:
            break
        A = Alist.popleft()
        An =  factorization(A)
        for i in range(len(An)):
            if An[i][0] not in Aset:
                Aset.add(An[i][0])
            else:
                sig = 0
    if len(Alist) == 0 and sig == 1:
        Answer = 'pairwise corprime'
print(Answer)

Submission status: Wrong Answer

Solution code:
NUM_MAX = 10**3 + 1
is_prime = [True] * NUM_MAX
is_prime[0] = False
is_prime[1] = False
primes = []
for i in range(NUM_MAX):
    if is_prime[i]:
        primes.append(i)
        for j in range(2*i, NUM_MAX, i):
            is_prime[j] = False

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

def solve(n, a):
    if len(set(a)) == n:
        ok = True
        for p in primes:
            num = 0
            for x in a:
                if x % p == 0:
                    num += 1
            if num > 1:
                ok = False
                break
        if ok:
            return "pairwise coprime"
    p = a[0]
    for i in range(1, n):
       p = gcd(p, a[i])
    return "setwise coprime" if p == 1 else "not coprime"

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