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 sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    #l,r,d=map(int,input().split())
    n=int(input())
    a=list(map(int,input().split()))
    sosu=[]
    for i in range(n):
        sosu.append(set(soinsubunkai(a[i])))

    memo = defaultdict(int)
    for i in range(n):
        for j in sosu[i]:
            memo[j]+=1
 #   print(sosu)
#    print(memo)
 #   print(memo.values())
    mmm=max(memo.values())
    if mmm<=1:
        print("pairwise coprime")
    elif mmm<n:
        print("setwise coprime")
    else:
        print("not coprime")








if __name__ == "__main__":

    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
N = int(input())
A = sorted([int(i) for i in 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 [a[0] for a in arr]
all_flag = True
devisors = set()
for n in range(N-1):
    if n == 0:
        g = gcd(A[n],A[n+1])
    else:
        g = gcd(A[n+1],g)
    temp = factorization(A[n])
    for t in temp:
        if t in devisors:
            all_flag=False
        else:
            devisors.add(t)
if all_flag and g == 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()))
l=[0]*(10**6+1)
for m in a:
  l[m]=1
x=0
j=2
#print(l)
for i in range(n):
  c=0
  k=1
  while j*k<=10**3+1 :
    if l[j*k]==1:
      c+=1
      l[j*k]=0
    k+=1
  if c==n:
    print("not coprime")
    exit()
  elif c>1:
    x=1
  j+=1 
if x==1:
  print("setwise coprime")
else:
  print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
ans=['pairwise coprime','setwise coprime','not coprime']
k=0
g=A[-1]
for i in range(2,N+1):
    g=math.gcd(g,A[-i])
    if g!=1:
        k=-1
if k==-1:
    if g==1:
        k=1
    else:
        k=2
print(ans[k])

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict
def main():
    n = int(input())
    a = list(map(int,input().split()))
    dic = defaultdict(bool)
    pairW = True
    setW = a[0]
    for i in a:
        t = 1
        while t**2 <= i:
            if i % t == 0:
                if t != 1 and (dic[t] or dic[i//t]):
                    pairW = False
                    break
                else:
                    dic[t] = True
                    dic[i//t] = True
            t += 1
        setW = gcd(setW,i)
    

    if pairW:
        print("pairwise coprime")
        return
    elif setW == 1:
        print("setwise coprime")
        return
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
m = min(A)
M = max(A)

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(M//2+1)


for i in range(2, M//2+1):
    if checked[i]:
        continue
    if i > m:
        break
    
    tmp = 0
    for j in range(N):
        if A[j]%i == 0:
            tmp += 1
    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    if is_setwise_coprime == False:
        break
    
    n = i
    while n < M//2+1:
        checked[n] = 1
        n += i

if is_pairwise_coprime:
    print('pairwise coprime')
elif is_setwise_coprime:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import *
import fractions
import sys
import collections
import itertools
import pprint
from collections import deque
from heapq import *
import copy
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
n = 10**6
d={}
pairflag=1
setflag=0
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)
#print(len(primes))
buf=[0]*(max(A)+10)
seen=[0]*(max(A)+10)
for i in range(N):
    if d.get(A[i])==None:
        d[A[i]]=1
    else:
        d[A[i]]=d[A[i]]+1
#print(d)
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
for i in primes:
    cnt=0
    for j in range(i,10**6+1,i):
        if d.get(j)!=None:
            cnt=cnt+d[j]
    if cnt>2:
        pairflag=0
        break

num=A[0]
for i in range(1,N):
    num=ggcd(num,A[i])
if num==1:
    setflag=1
else:
    setflag=0

if pairflag==1:
    print("pairwise coprime")
elif setflag==1:
    print("setwise coprime")
else:
    print("not coprime")

"""
x=list(set(A))
for i in x:
    for j in range(2*i,10**6+1,i):
        if d.get(j)!=None:
            pairflag=0
            break
    if pairflag==0:
        break
print(pairflag)

"""

Submission status: Wrong Answer

Solution code:
N = int(input())

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

max_a = max(A)

set_a = set(A)

setFlag = False

if len(set_a) != len(A):
    setFlag = True

for i in range(2,int(max_a**0.5)+2):
    tmp_count = 0
    pairFlag = True
    for key,a in enumerate(A):
        if a%i == 0:
            tmp_count += 1
            if 1 < tmp_count and tmp_count != key+1:
                setFlag = True
                break
        else:
            pairFlag = False
    if pairFlag:
        print('not coprime')
        exit()

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

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
#input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

data = get_sieve_of_eratosthenes(1000001)
data2 = get_sieve_of_eratosthenes(2000)

# 1~1000000の素数リストを作成
check = [0] * (10 ** 6 + 1)
for d in data:
    check[d] = 1

# 素因数分解
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

def is_pairwise(arr):

    cnt = [0] * 1000001
    
    # 非素数が168個以上あったらアウト
    non_prime = []
    for a in arr:
        if check[a] == 0:
            non_prime.append(a)
        else:
            cnt[a] += 1
    if len(non_prime) > 200:
        return 0
    
    # 非素数を素因数分解して、cntに足し合わせる
    for np in non_prime:
        for a, b in factorization(np):
            cnt[a] += 1
    if max(cnt[2:]) >= 2:
        return 0
    
    return 1
    
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def is_setwise(arr):
    
    tmp = arr[0]
    for a in arr:
        tmp = gcd(tmp, a)
    if tmp == 1:
        return 1
    else:
        return 0
        
ip = is_pairwise(A)
iss = is_setwise(A)

if ip:
    print("pairwise coprime")
else:
    if iss:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

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

sosuu = [2]
import math
max_prime = int(math.sqrt( min(A) ))+2
for L in range(3, max_prime, 2):
    if all(L % L2 != 0 for L2 in sosuu): 
        sosuu.append(L)

pair_coprime=True
set_coprime=True

for p in sosuu:
    s = sum(aa%p==0 for aa in A)
    if s>=2:
        pair_coprime=False
    if s==N:
        set_coprime=False
        
if pair_coprime:
    print("pairwise coprime")
elif set_coprime:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

"""
pairwise coprime 1,3,7,10
setwise coprime 2,3,4,10


coprimeかどうかで全部やる
"""

def primes(n): #試し割り法で各素因数とその指数を求める
    cnt=collections.defaultdict(int)
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            while n%i==0:
                cnt[i]+=1
                n//=i
    if n!=1:
        cnt[n]+=1
    return cnt


def solve():
    gcd = A[0]
    for a in A:
        gcd = math.gcd(gcd, a)
    if gcd != 1:
        return "not coprime"


    d = primes(A[0])
    prime_his = list(d.keys())
    for a in A[0:]:
        d = primes(a)
        # print(prime_his, d.keys())
        if len(set(prime_his) - set(d.keys())) != len(prime_his) - len(d.keys()):
            return "setwise coprime"
        
        prime_his += d.keys()
    
    return "pairwise coprime"

    
print(solve())

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = LIST()
lim = 10**6+1
g = [[] for _ in range(lim+1)]
g[1].append(1)
for i in range(2, lim+1):
	if g[i] == []:
		for j in range(1, lim//i + 1):
			g[i*j].append(i)

num = [0]*(lim+1)

for a in A:
	for x in g[a]:
		if num[x]:
			break
		num[x] = 1

	else:
		continue
	break
else:
	print("pairwise coprime")
	exit()


#素因数分解
def factorization(n):
	arr = []
	tmp = n
	for i in range(2, int(-(-n**0.5//1))+1):
		if tmp%i == 0:
			cnt = 0
			while tmp%i == 0:
				cnt += 1
				tmp //= i
			arr.append([i, cnt])
	if tmp != 1:
		arr.append([tmp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr
	
dic = defaultdict(int)
for x, y in factorization(A[0]):
	dic[x]=y

for a in A[1:]:
	for x, y in dic.items():
		if a%x:
			dic[x] = 0
		else:
			dic[x] = min(y, a//x)

for x, y in dic.items():
	if x != 1 and y != 0:
		print("not coprime")
		break
else:
	print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  # ここにバグがないか心配
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append((i, cnt))
            if temp == 1:
                break

    if temp != 1:
        arr.append((temp, 1))

    if arr == []:
        arr.append((n, 1))

    return arr


def can_factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  # ここにバグがないか心配
        if temp % i == 0:
            arr.append(i)

    if temp != 1:
        arr.append((temp, 1))

    # if arr == []:
    #     arr.append((n, 1))

    return arr


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
if N > 4 * (10**5):
    flg = 0
    for a in A:
        g_set = gcd(g_set, a)
else:
    for a in A:
        g_set = gcd(g_set, a)
        for p, n in factorization(a):
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from itertools import combinations
from math import gcd


def func(A):
    n = len(A) - len(set(A))
    if n > 0 and n+1 != A.count(1):
        return False
    is_A = [False] * (10**6+1)
    for a in A:
        is_A[a] = True
    n = 0
    for i in range(2, 10**6+1, 2):
        if is_A[i]:
            n += 1
    if n > 1:
        return False
    # for i in range(3, 10**6+1, 2):
    for i in range(3, int((10**6+1)**.5+1), 2):
        n = 0
        for j in range(i, 10**6+1, i):
            if is_A[j]:
                n += 1
        if n > 1:
            return False
    return True


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    if func(A):
        # if not all(gcd(i, j)==1 for i, j in combinations(A, 2)):
        #     raise NameError
        print('pairwise coprime')
    elif reduce(gcd, A) == 1:
        print('setwise coprime')
    else:
        print('not coprime')
    

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    aaa = np.unique(inp[1:])
    PRIMES = (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)

    if len(aaa) == n:
        pairwise = 1
    else:
        pairwise = 0

    one_count = 0
    for p in PRIMES:
        exists_not_multiple = 0
        multiple_count = 0
        for i in range(len(aaa)):
            if aaa[i] % p == 0:
                multiple_count += 1
                aaa[i] //= p
                while aaa[i] % p == 0:
                    aaa[i] //= p
            else:
                exists_not_multiple = 1

        if exists_not_multiple == 0:
            return -1
        if multiple_count > 1:
            pairwise = 0

        oc = (aaa == 1).sum()
        if oc > 0:
            one_count += oc - 1
        aaa = np.unique(aaa)

    if pairwise == 0:
        return 0

    if one_count + len(aaa) == n:
        return 1

    return 0


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(['setwise coprime', 'pairwise coprime', 'not coprime'][ans])

Submission status: Wrong Answer

Solution code:
from math import gcd
from functools import reduce
N = int(input())
*A, = map(int, input().split())
mod = 10**9 + 7
mod2 = 2147483647

def lcm(a, b):
    return a*b//gcd(a,b) % mod

def mul(a, b):
    return a*b % mod

def lcm2(a, b):
    return a*b//gcd(a,b) % mod2

def mul2(a, b):
    return a*b % mod2

if reduce(lcm, A) == reduce(mul, A) and reduce(mul2, A) == reduce(lcm2, A):
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print("setwise coprime")
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
gcd=lambda x,y:gcd(y,x%y) if y!=0 else x
def f(a):
    p=a[0]
    for i in range(1,len(a)):
        p=gcd(p,a[i])
    if p==1:
        print("setwise coprime")
    else:
        print("not coprime")

n=int(input())
a=list(map(int,input().split()))
if 1 in a:
    print("not coprime")
    exit()
l=[0 for i in range(2*10**6)]
for i in a:
    l[i]+=1
h=[0 for i in range(2*10**6)]
for i in range(2,2*10**6):
    if h[i]:
        continue
    p=0
    for j in range(i,2*10**6,i):
        #h[j]=1
        p+=l[j]
    if p>1:
        f(a)
        exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
n = int(input())
a = list(map(int, input().split()))
b = a[0]
c = 0
for i in range(1, n):
    b = math.gcd(b, a[i])
    if a[i-1] == a[i] and a[i] != 1: c = 1
if b != 1: print("not coprime")
elif c == 1: print("pairwise coprime")
else:
    data = primes(10**3)
    count = [0]*(len(data))
    d = 0
    for i in range(n):
        for j in range(len(data)):
            if a[i]%data[j] == 0:
                if count[j] == 1:
                    print("setwise coprime")
                    d = 1
                    break
                else:
                    count[j] = 1
        if d == 1:
            break
    else: print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def prime(n):
    nums = [True]*n
    primes = []
    for i in range(2,n):
        if nums[i]:
            primes.append(i)
            for j in range(2*i,n,i):
                nums[j] = False
    return primes

def main():
    n = int(input())
    A = set(map(int,input().split()))

    Amax = max(A)
    primes = set(prime(Amax+1))
    ct = 1
    if len(A) != n:
        ct = 2
    for p in primes:
        g = set(())
        temp = p
        while temp <= Amax:
            g.add(temp)
            temp+=p
        
        k = len(g & A)
        if k > ct:
            ct = k
    
    if ct == n:
        print("not coprime")
    elif ct == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
main()

Submission status: Wrong Answer

Solution code:
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)

n=int(input())
a=list(map(int,input().split()))
b=gcd(a[0],a[1])
res1=True
res2=True
for i in range(n-1):
    c=a[i];d=a[i+1]
    if gcd(c,d)==1:
        continue
    else:
        res1=False
        b=gcd(b,d)

if res1:
    print("pairwise coprime")
elif b==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

from math import gcd

def factor(n):
    ans = []
    i = 0
    while n & 1 == 0:
        n >>= 1
        i += 1

    if i > 0:
        ans.append((2, i))

    for i in range(3, int(n**.5) +1, 2):
        x, y = divmod(n, i)

        if y == 0:
            j = 1
            x1 = x
            while True:
                x1, y = divmod(x, i)
                if y == 0:
                    x = x1
                    j += 1
                else:
                    ans.append((i, j))
                    break
            n = x

    if n > 1:
        ans.append((n, 1))

    return ans

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = list(it)
    A.sort()
    M = A[-1]
    M1 = M + 1

    if A[0] == 1:
        print("setwise coprime")
        return

    dp = [0] * M1

    g1 = A[0]
    for i, a in enumerate(A):
        g1 = gcd(g1, a)

        for x, _ in factor(a):
            for y in range(x, M1, x):
                if dp[y]:
                    for i in range(i, N):
                        a = A[i]
                        g1 = gcd(g1, a)
                        if g1 == 1:
                            print("setwise coprime")
                            return
                    print("not coprime")
                    return
                dp[y] = 1

    print("pairwise coprime")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
import math

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

set_A = set(A)
set_flag = len(set_A) != N

co_prime = True
max_a = max(A)

coprime = True
exists = set()
for i in range(2, max_a + 1):
    flag = False
    for j in range(i, max_a + 1, i):
        if j in set_A:
            if not flag:
                flag = True
            elif flag:
                coprime = False
                break
    if not coprime:
        break
pairwise = (coprime and N == len(set_A))
if pairwise:
    print("pairwise coprime")
    sys.exit()

setwise = False
tmp = A[0]
for i in range(N):
    tmp = math.gcd(tmp, A[i])
if tmp == 1:
    setwise = True

if setwise:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import numpy as np
 
def prime(n):
    primes = np.zeros(n + 1, dtype=np.bool)
    primes[2] = 1
    primes[3::2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            primes[p * p::2 * p] = 0
    return primes
pp=prime(10**3)
p=[]
for i in range(2,1001):
  if pp[i]:
    p.append(i)
n=int(input())
a=list(map(int,input().split()))
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

g=a[0]
for i in a[1:]:
  g=gcd(g,i)
if g==1:
  mm=[0 for i in range(10**6+1)]
  f=True
  for i in a:
    if mm[i]:
      f=False
      break
    mm[i]=1
    for j in range(168):
      if i%p[j]==0:
        if mm[p[j]]:
          f=False
          break
        mm[p[j]]=1
        if mm[i//p[j]]:
          f=False
          break
        mm[i//p[j]]=1
    if not f:
      break
  if f:
    print("pairwise coprime")
  else:
    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()))

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

sa = set(A)
if len(sa) < N:
    print('setwise coprime')
    exit()

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
while p*p <= MAXN:
    if sieve[p]:
        c = 0
        if p in sa: c += 1
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
            if q in sa:
                c += 1
                if c > 1:
                    print('setwise coprime')
                    exit()
    p += 1

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-


def factor_osa(A):
    Max = max(A) + 1
    IsPrime = [True] * Max
    MinFactor = [-1] * Max
    Primes = []
    IsPrime[0], IsPrime[1] = False, False
    MinFactor[0], MinFactor[1] = 0, 1
    for i in range(2, Max):
        if IsPrime[i]:
            MinFactor[i] = i
            Primes.append(i)
            for j in range(i*2, Max, i):
                IsPrime[j] = False
                if MinFactor[j] == -1:
                    MinFactor[j] = i
    ret = []
    for a in A:
        res = []
        while a != 1:
            prime = MinFactor[a]
            exp = 0
            while MinFactor[a] == prime:
                exp += 1
                a //= prime
            res.append((prime, exp))
        ret.append(res)
    return ret

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

aa = factor_osa(a)
dica = {}
dicb = {}
mxa = 0
for i in aa:
    for j in i:
        if not j[0] in dica:
            dica[j[0]] = 1
        else:
            dica[j[0]] += 1
        mxa = max(mxa, dica[j[0]])

from math import gcd        #for python3.8

def Gcd(lt):
    l = len(lt)
    ret = [1]*l
    ret[0] = lt[0]
    for i in range(1,l):
        ret[i] = gcd(ret[i-1], lt[i])
    return ret

if mxa == 1:
    print('pairwise coprime')
elif Gcd(a)[-1]==1:
    print('setwise coprime')
else:
    print('not coprime')