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
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))

# MOD = 10**9 + 7

def main():
	n = int(input());arr = read()
	sett = set()
	gcd_ = arr[0]
	flag = 1
	for i in range(n):
		tem  =[]; m = arr[i]
		if flag:
			for fact in range(2, int(sqrt(m)+1)):
				if m % fact == 0:
					tem.append(fact)
				while m%fact == 0:m //= fact
			if 1 < m < arr[i]:
				tem.append(m)
			# print(tem)
			for k in tem:
				if k in sett:
					flag = 0
				sett.add(k)

		gcd_ = gcd(gcd_, arr[i])

	if flag:print("pairwise coprime")
	elif gcd_ == 1:print("setwise coprime")
	else:print("not coprime")


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import math


n = int(input())
a = [int(x) for x in input().split()]
l = [[] for i in range(n)]

def gcd(p,q):
    while q != 0:
        p = min(p%q,-(p%q)+q)
        p,q = q,p
    return p


g = a[0]
for i in range(1,n):
    g = gcd(g,a[i])

if g != 1:
    print("not coprime")

else:
    def fur(x):
        k = [1 for i in range(x+1000)]
        k[0]=k[1]=0
        for i in range(2,x+1):
            for j in range(i-1,x//i):
                k[i+j*i] = 0
        return k

    t = fur(10**6)

    cnt = 0

    def soi(x):
        global t,cnt
        for i in range(2,int(math.sqrt(x))+1):
            if t[i] != 0 and x%i==0:
                if t[i] == 1:
                    t[i] = 2
                elif t[i] == 2:
                    cnt = 1
                    break
    
    for i in range(n):
        if cnt == 1:
            break
        else:
            soi(a[i])
    
    if cnt == 1:
        print("setwise coprime")
    
    else:
        print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
divs = [0 for _ in range(max(a)+1)]

for x in a:
    for i in range(1, int(x**0.5)+1):
        if x%i == 0:
            divs[i] += 1
            if i != x//i:
                divs[x//i] += 1

divs[1] = 0
div_max = max(divs)
if div_max == 1:
    print('pairwise coprime')
elif div_max == n:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from math import gcd
from functools import reduce
from collections import defaultdict


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def is_pairwise_coprime(A):
    N = max(A)
    if N == 1:
        return True
    table = defaultdict(bool)
    for a in A:
        k = a
        i = 2
        while i * i <= k:
            is_div = False
            while k % i == 0:
                k //= i
                is_div = True
            if is_div:
                if table[i]:
                    return False
                table[i] = True
            i += 1
        if k > 1:
            table[k] = True
    return True


def solve(N, A):
    if is_pairwise_coprime(A):
        return "pairwise coprime"
    if reduce(gcd, A) == 1:
        return "setwise coprime"
    return "not coprime"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from math import gcd
from functools import reduce


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def is_pairwise_coprime(A):
    N = max(A)
    table = [False for i in range(N+1)]
    for a in A:
        k = a
        i = 2
        while i * i <= k:
            is_div = False
            while k % i == 0:
                k //= i
                is_div = True
            if is_div:
                if table[i]:
                    return False
                table[i] = True
            i += 1
        if k > 1:
            table[k] = True
    return True


def solve(N, A):
    if is_pairwise_coprime(A):
        return "pairwise coprime"
    if reduce(gcd, A) == 1:
        return "setwise coprime"
    return "not coprime"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

Solution code:
import math


n = int(input())
a = [int(x) for x in input().split()]
l = [[] for i in range(n)]

def gcd(p,q):
    while q != 0:
        p = min(p%q,-(p%q)+q)
        p,q = q,p
    return p


g = a[0]
for i in range(1,n):
    g = gcd(g,a[i])

if g != 1:
    print("not coprime")

else:
    def fur(x):
        k = [1 for i in range(x+1)]
        k[0]=k[1]=0
        for i in range(2,x+1):
            for j in range(i-1,x//i):
                k[i+j*i] = 0
        return k

    t = fur(10**6)

    cnt = 0

    def soi(x):
        global t,cnt
        for i in range(2,int(math.sqrt(x))+1):
            if x%i== 0:
                if t[i] == 1:
                    t[i] = 2

                elif t[i] == 2:
                    cnt = 1
    
    for i in range(n):
        if cnt == 1:
            break
        else:
            soi(a[i])
    
    if cnt == 1:
        print("setwise coprime")
    
    else:
        print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math

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

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
    while search_list[0] <= math.sqrt(number):
        #search_listの先頭の値が√nの値を超えたら終了
        #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        for i in range(number // head_num):
            index = head_num * (i + 1)
            if D[index] == index:
                D[index] = head_num
        search_list = [num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list


def factrization_prime(number):
    div = D[number]
    s = math.sqrt(number)
    while div <= s:
        div_cnt = 0
        while number % div == 0:
            div_cnt += 1
            number //= div
        ans_array[div] += 1
        if number == 1:
            break
        div = D[number]
    if number > 1:
        ans_array[number] += 1

# thre = pow(10, 6) + 1
thre = max(a_array) + 1
ans_array = [0] * thre
D = list(range(thre + 1))

prime_list = get_primenumber(thre)
print(D[:10])
for a in a_array:
    factrization_prime(a)

max_ans_array = max(ans_array)
if max_ans_array == 1:
    print('pairwise coprime')
elif max_ans_array < n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))

# MOD = 10**9 + 7

def main():
	n = int(input());arr = read()
	sett = set()
	gcd_ = arr[0]
	flag = 1
	for i in range(n):
		tem  =[]; m = arr[i]
		if flag:
			for fact in range(2, int(sqrt(m)+1)):
				if m % fact == 0:
					if fact in sett:
						flag = 0
						break
					tem.append(fact)
				while m%fact == 0:m //= fact
			if 1 < m < arr[i]:
				if m in sett:
					flag = 0
				tem.append(m)
			# print(tem)
			for k in tem:sett.add(k)
		gcd_ = gcd(gcd_, arr[i])
	if flag:print("pairwise coprime")
	elif gcd_ == 1:print("setwise coprime")
	else:print("not coprime")


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))

# MOD = 10**9 + 7

def main():
	n = int(input());arr = read()
	sett = set()
	gcd_ = arr[0]
	flag = 1
	for i in range(n):
		tem  =[]; m = arr[i]
		if flag:
			for fact in range(2, int(sqrt(m)+1)):
				if m % fact == 0:
					if fact in sett:
						flag = 0
						break
					tem.append(fact)
				while m%fact == 0:m //= fact
			if 1 < m < arr[i]:tem.append(m)
			for k in tem:sett.add(k)
		gcd_ = gcd(gcd_, arr[i])
	if flag:print("pairwise coprime")
	elif gcd_ == 1:print("setwise coprime")
	else:print("not coprime")


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import math
import itertools

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

soinsuu = []

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)

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

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

    return arr

for i in a:
  soinsuu.append(factorization(i))

soinsuu = list(itertools.chain.from_iterable(soinsuu))
if len(set(soinsuu)) == len(soinsuu):
  ans = "pairwise coprime "
else:
  ans = "setwise coprime"
  gcd = a[n-1]
  for i in range(len(a)-1):
    gcd = math.gcd(a[i],gcd)
  if gcd != 1:
    ans = "not coprime"
  
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import math
    n = int(input())
    a = sorted(list(map(int,input().split())))
    g=a[0]
    for i in range(1,n):
        g = math.gcd(g,a[i])
    if g > 1:
        print('not coprime')
        return
    d = [1 for i in range(a[-1])]
    for i in range(2,a[-1]):
        if d[i-1] == 1:
            for j in range(1,a[-1]//i+1):
                if d[i*j-1] == 1:
                    d[i*j-1] = i
    cnt = [0 for i in range(a[-1]+1)]
    flg = 0
    for i in range(n):
        cnt[d[a[i]-1]] += 1
        if cnt[d[a[i]-1]] != 0:
            flg = 1
            break
    if flg == 1:
        print('setwise coprime')
        return
    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

dp = [0] * (10**6 + 1)

for a in A:
    for i in range(1, int(math.sqrt(a)) + 1):
        if a % i == 0:
            dp[i] += 1
            if i != a // i:
                dp[a // i] += 1
            
ans = 0

for i in range(2, max(A) + 1):
    ans = max(ans, dp[i])

if ans == 1:
    print("pairwise coprime")

elif ans < N:
    print("setwise coprime")
    
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

def trial_division(n):  # n > 1
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def eratosthenes(n):
    a = [1]*(n+1)
    for i in range(2,int(n**0.5)+1):
        if a[i]:
            for j in range(i*i,n+1,i):
                a[j]=0
    return [i for i in range(2,n+1) if a[i]]

flag = 0
ans = ['pairwise coprime', 'setwise coprime', 'not coprime']

n = readint()
a = readints()

prime = eratosthenes(10**6)

check = {x:0 for x in prime}

for x in a:
    for y in set(trial_division(x)):
        check[y] += 1

m = max(check.values())
if m==n:
    flag = 2
elif m==2:
    flag = 1
print(ans[flag])

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:
        #while m%i==0:
        if i >m:
            break
        if m%i==0:
            pf.add(i)
        #    m//=i
    #if m>1:
    #    pf.add(1)
    return pf


# 初期入力
import sys
from collections import Counter
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)

#素因数分解しながら判定の下準備
pair_w =set()
set_w =set()
not_judg =[]

prim_list_dic =dict()
gcd_a =math.gcd(A[0],A[1])

ans =""
if N==2:
    if gcd_a ==1:
        ans ="pairwise coprime"
    else:
        ans ="not coprime"
else:
    intersect =set()
    used =set()
    a_0 =soinsu_bunkai(A[0])
    a_1 =soinsu_bunkai(A[1])
    intersect |= a_0 
    intersect |= a_1
    if gcd_a !=1:
        pair_w.add(0)
    else:
        pair_w.add(1)
    for a in A[2:]:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            pair_w.add(0)
        else:
            pair_w.add(1)
        intersect |=aa
        gcd_a =math.gcd(gcd_a,a)

    #判定
    ans ="setwise coprime"

    #not coprimeの判定
    if gcd_a !=1:
        ans ="not coprime"

    #pairwise coprimeの判定
    elif 1 in pair_w and 0 not in pair_w :
        ans ="pairwise coprime"



print(ans)

Submission status: Wrong Answer

Solution code:
def is_prime(p):
    d = 2
    while d*d <= p:
        if p % d == 0:
            return False
        d += 1
    return True

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

primes = []
for i in range(2,1000):
    if is_prime(i):
        primes.append(i)

cnt = [0] * len(primes)
for i in range(len(primes)):
    for a in A:
        if a % primes[i] == 0:
            cnt[i] += 1
    
if N in cnt:
    print("not coprime")
    exit()

for c in cnt:
    if c > 1:
        print("setwise coprime")
        exit()

print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import math

def divisors(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table


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

fd = set([1])
flag = 'pairwise coprime'

mimm = min(ab)


for a in ab:
    if fd & set(divisors(a)) != {1}:
        flag = 'setwise coprime'
        break
    fd = fd | set(divisors(a))
    mimm = math.gcd(mimm,a)

if mimm > 1:
  flag =  "not coprime"
        
print(flag)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd, ceil, sqrt
n = int(input())
aa = list(map(int, input().split()))
ma = max(aa)
cnt = [0] * (ma+1)

for a in aa:
    cnt[a] += 1

if reduce(gcd, aa) != 1:
    print('not coprime')
elif all(c <= 1 for c in cnt) and all(sum(cnt[i::i]) <= 1 for i in range(2, ceil(sqrt(ma)) + 1)):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd, ceil, sqrt
n = int(input())
aa = list(map(int, input().split()))
ma = max(aa)
cnt = [0] * (ma+1)

for a in aa:
    cnt[a] += 1

if reduce(gcd, aa) != 1:
    print('not coprime')
elif all(sum(cnt[i::i]) <= 1 for i in range(2, ceil(sqrt(ma)) + 1)):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
INF = float('inf')
N = int(input())
A = list(map(int,input().split()))
flg = True
lis = [INF] * (10**6+5)
for i in range(2,int((10**6)**0.5)+1):
    if lis[i] == INF:
        for j in range(i*2,10**6+1,i):
            lis[j] = i
st = set()
for i in range(N):
    p = A[i]
    d  =[]
    while lis[p] != INF:
        d.append(lis[p])
        p //= lis[p]
    #if p > 1:
    d.append(p)
    for i in range(len(d)):
        if d[i] in st:
            flg = False
    for i in range(len(d)):
        st.add(d[i]) 
#print(lis[:15])

if flg == True:
    print('pairwise coprime')
    exit()



val = A[0]
for i in range(1,N):
    val = gcd(val,A[i])
if val == 1:
    print('setwise coprime')
    exit()
print('not 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]]

def factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

Ps = primes(10 ** 6)
n = int(input())
As = list(map(int, input().split()))
Aset = set(As)

# setwiseFlag
gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)

# pairwiseFlag
pairwiseFlag = True
for p in Ps:
  count = 0
  for _p in range(p, 10 ** 6 + p, p):
    if _p in Aset:
      count += 1
  if count > 1:
    pairwiseFlag = False

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not 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]]

def factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

Ps = primes(10 ** 6)
n = int(input())
As = list(map(int, input().split()))
Aset = set(As)

# setwiseFlag
gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)

# pairwiseFlag
pairwiseFlag = True
for p in Ps:
  count = 0
  for _p in range(p, 10 ** 6 + 1, p):
    if _p in Aset:
      count += 1
  if count > 1:
    pairwiseFlag = False
    
if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import gcd

class Prime:
    def __init__(self, N):
        smallestPrime = [1] * (N + 1)
        primes = []

        for i in range(2, N + 1):
            if smallestPrime[i] != 1:
                continue
            primes.append(i)
            for p in range(i * 2, N + 1, i):
                if smallestPrime[p] == 1:
                    smallestPrime[p] = i

        self.smallestPrime = smallestPrime
        self.primes = primes

    def isPrime(self, n):
        return n > 1 and self.smallestPrime[n] == 1

    def factorization(self, n):
        ret = Counter()
        while (p := self.smallestPrime[n]) != 1:
            ret[p] += 1
            n //= p
        return ret

N = int(input())
A = list(map(int, input().split()))
prime = Prime(max(A) + 100)

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1

def isPairwise(A):
    cnt = Counter()
    for a in A:
        for p in prime.factorization(a).keys():
            if cnt[p] >= 1:
                return False
            cnt[p] += 1
    return True

if not isSetwise(A):
    print('not coprime')
elif isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
aa = np.array(input().split(), dtype='int')
ma = np.max(aa)
cnt = np.zeros(max(aa)+1, dtype='int')

for a in aa:
    cnt[a] += 1

if np.gcd.reduce(aa) != 1:
    print('not coprime')
elif np.all([cnt[i::i].sum() <= 1 for i in range(2, np.sqrt(ma+1).astype(int)+1)]):
    print('pairwise coprime')
else:
    print('setwise coprime')

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

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]

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

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

if n>=78492:
    print("setwise coprime")
    sys.exit()

ptype="pairwise coprime"
for pp in p:
    lap=0
    for ai in ap:
        if  ai%pp==0:
            lap+=1
        if lap>=2:
            ptype="setwise coprime"
            print(ptype)    
            sys.exit()
#    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:
# 自然数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:
        while m%i==0:
            pf.add(i)
            m//=i
    if m>1:
        pf.add(1)
    return pf


# 初期入力
import sys
from collections import Counter
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)

#素因数分解しながら判定の下準備
pair_w =set()
set_w =set()
not_judg =[]

prim_list_dic =dict()
gcd_a =math.gcd(A[0],A[1])

ans =""
if N==2:
    if gcd_a ==1:
        ans ="pairwise coprime"
    else:
        ans ="not coprime"
else:
    intersect =set()
    a_0 =soinsu_bunkai(A[0])
    a_1 =soinsu_bunkai(A[1])
    intersect |= a_0 
    intersect |= a_1
    if gcd_a !=1:
        pair_w.add(0)
    else:
        pair_w.add(1)
    for a in A[2:]:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            pair_w.add(0)
        else:
            pair_w.add(1)
        intersect |=aa
        gcd_a =math.gcd(gcd_a,a)

    #判定
    ans ="setwise coprime"

    #not coprimeの判定
    if gcd_a !=1:
        ans ="not coprime"

    #pairwise coprimeの判定
    elif 1 in pair_w and 0 not in pair_w :
        ans ="pairwise coprime"



print(ans)

Submission status: Wrong Answer

Solution code:
import math

def pf(n):
  s = set()
  i = 2
  while i * i <= n:
    if n % i == 0:
      s.add(i)
    i += 1
  if n > 1:
    s.add(n)
  return s

input()
d = None
u = set()
r = 'pairwise'
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  s = pf(x)
  if not s.isdisjoint(u):
    r = 'setwise'
  u |= s
print((r, 'not')[d > 1], 'coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
from functools import reduce
import numpy as np

PC = True

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

MAX = A[0]+1
mp = [0]*MAX

for i in A:
  mp[i] += 1

for i in range(2,int(np.sqrt(MAX))+1):
  if sum(mp[i::i])>1:
    PC = False
    break

if PC:
  print('pairwise coprime')
else:
  if reduce(gcd, A) == 1:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
from functools import reduce
import numpy as np

PC = True

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

MAX = A[0]+1
mp = [0]*MAX

for i in A:
  mp[i] += 1
print(mp)
for i in range(2,int(np.sqrt(MAX))+1):
  if sum(mp[i::i])>1:
    PC = False
    break

if PC:
  print('pairwise coprime')
else:
  if reduce(gcd, A) == 1:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math

INF = 10 ** 6 + 1
is_prime = [1] * INF

def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return

def f(n):
    yakusu = []
    if is_prime[n]:
        yakusu.append(n)
    else:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                yakusu.append(i)
                yakusu.append(n // i)
                break

    for i in yakusu:
        if i != 1:
            d[i] += 1

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

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

if tmp != 1:
    print('not coprime')
    exit()
eratorasu()
f(A[0])

for i, v in d.items():
    if v != 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math


def get_pseudo_input():
    N = 3
    A = [6, 10, 16]
    return N, A


def get_input():
    N = int(input())
    A = [int(x) for x in input().split()]
    return N, A


def sieve_of_eratosthenes(x: int):
    ret = [-1] * (x + 1)
    for i in range(1, x + 1):
        ret[i] = i
    p_max = int(math.sqrt(x))
    for p in range(2, p_max + 1):
        if ret[p] < p:  # p is not a prime number
            continue
        for i in range(p, x + 1, p):
            if ret[i] > p:
                ret[i] = p
    return ret


A_max = 10 ** 6
p_table = sieve_of_eratosthenes(A_max)

N, A = get_input()
# Store a number of unique Ais using the prime number
p_nums = [0] * (A_max + 1)
max_p_nums = 0
for a in A:
    # print(f"a={a}")
    while a > 1:
        p = p_table[a]
        while a % p == 0:
            a = a // p
        # print(f"  a={a}")
        p_nums[p] += 1
        if max_p_nums < p_nums[p]:
            max_p_nums = p_nums[p]
# print(max_p_nums)
if max_p_nums == 1:
    print('pairwise coprime')
elif max_p_nums < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [*map(int, input().split())]
# print(n)
# print(A)

# 素数と個数を求める
def factorize(n):
    res = []
    for i in range(2,n):
        if i*i > n: break
        if n%i: continue
        res += [[i,0]]
        while n%i == 0:
            n //= i
            res[-1][1] += 1
    if n != 1: res += [[n,1]]
    return res

from math import gcd
gcd_all = A[0]
for a in A: gcd_all = gcd(gcd_all, a)
# print(gcd_all)

if gcd_all != 1:
    print('not coprime')
    exit()

PC = [False] * (10**6+1) # [0, 10**6]
max_A = 0
for a in A:
    max_A = max(max_A, a)
    PC[a] = True

# print(PC[:max_A+1])
# for i in range(max_A+1):
#     if PC[i]:
#         print(i, end=' ')
#     else:
#         print('-', end=' ')
# print()

g = A[0]
for a in A:
    pc = factorize(a)
    # print('pc {}'.format(pc))
    for p,c in pc:
        i = a // p + 1
        # print('a {} p {} c {} i {}'.format(a,p,c,i))
        while i*p <= max_A:
            PC[i*p] = False
            i += 1
            # print('i {}'.format(i))

# print(PC[:max_A+1])
# for i in range(max_A+1):
#     if PC[i]:
#         print(i, end=' ')
#     else:
#         print('-', end=' ')
# print()

num_true = 0
for f in PC:
    if f: num_true += 1

# print(num_true)

if num_true == len(A):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
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)
    return set(r)


j = 0
a1 = set()
a2 = set(prime_factorize(A[0]))
for a in A:
    tmp = prime_factorize(a)
    if a1 & tmp:
        j = 1
    a1 |= tmp
    a2 &= tmp
if a2:
    print('not coprime')
elif j:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
from functools import reduce


def facs(n):
    """試し割り法における割る数を生成する。"""
    yield 2
    max_prime = int(pow(n, 0.5)) + 1
    for x in range(3, max_prime, 2):
        yield x


def main():
    input()  # N
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 1
    histogram = [0] * MAX_A
    for x in array:
        histogram[int(x)] += 1

    for divider in facs(MAX_A):
        count = sum(histogram[divider::divider])
        if count > 1:
            break
    else:
        return 'pairwise coprime'

    gcd_total = reduce(gcd, array)
    if gcd_total == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


if __name__ == '__main__':
    print(main())