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: Runtime Error

Solution code:
def gcd(a, b):
    # c += 1
    # if c > 100:
    #     return 100;
    # print(c, a, b)
    if a < b:
        a, b = b, a
    if b == 0:
        return a;
    return gcd(b, a - b)

# test1 = gcd(40, 20, 1)
# test2 = gcd(60, 40, 1)
# test3 = gcd(50, 3, 1)

# print(test1, test2, test3)

def f(n, ais):
    common_divisor = ais[0]
    for (i, ai) in enumerate(ais):
        common_divisor = gcd(ai, common_divisor)
        for (j, aj) in enumerate(ais[i+1:]):
            if gcd(ai, aj) != 1:
                for aiu in ais[i+1:]:
                    common_divisor = gcd(aiu, common_divisor)
                if common_divisor == 1:
                    return 'setwise coprime'
                else:
                    return 'not coprime'
        # print(common_divisor)
    return 'pairwise coprime'

# def test(n, ais, r):
#     result = f(n, ais)
#     print('{} n={}, ais={}, result={}'.format(result == r, n, ais, result))

# r1 = 'pairwise coprime'
# r2 = 'setwise coprime'
# r3 = 'not coprime'

# test(2, [6, 6], r3)
# test(3, [4, 7, 3], r1)
# test(3, [2, 3, 4], r2)
# test(3, [2, 4, 6], r3)

# test(3, [3, 4, 5], r1)
# test(3, [6, 10, 15], r2)
# test(3, [6, 10, 16], r3)

# test(2, [100, 1], r1)
# test(3, [8, 1, 800], r2)
# test(3, [1, 1, 1], r1)
# test(4, [2, 3, 5, 7], r1)
# test(4, [2, 3, 5, 10], r2)

# test(3, [100, 10, 1], r2)

n = int(input())
ais = list(map(int, input().split(' ')))
print(f(n, ais))

Submission status: Runtime Error

Solution code:
def gcd(a, b):
    # c += 1
    # if c > 100:
    #     return 100;
    # print(c, a, b)
    if a < b:
        a, b = b, a
    if b == 0:
        return a;
    return gcd(b, a - b)

# test1 = gcd(40, 20, 1)
# test2 = gcd(60, 40, 1)
# test3 = gcd(50, 3, 1)

# print(test1, test2, test3)

def f(n, ais):
    common_divisor = ais[0]
    for (i, ai) in enumerate(ais):
        common_divisor = gcd(ai, common_divisor)
        for (j, aj) in enumerate(ais[i+1:]):
            if gcd(ai, aj) != 1:
                for ai in ais[i+1:]:
                    common_divisor = gcd(ai, common_divisor)
                if common_divisor == 1:
                    return 'setwise coprime'
                else:
                    return 'not coprime'
        # print(common_divisor)
    return 'pairwise coprime'

# def test(n, ais):
#     print('n={}, ais={}, result={}'.format(n, ais, f(n, ais)))

# test(2, [6, 6])
# test(3, [4, 7, 3])
# test(3, [2, 3, 4])
# test(3, [2, 4, 6])

# test(3, [3, 4, 5])
# test(3, [6, 10, 15])
# test(3, [6, 10, 16])

# test(2, [100, 1])
# test(3, [8, 1, 800])
n = int(input())
ais = list(map(int, input().split(' ')))
print(f(n, ais))

Submission status: Runtime Error

Solution code:
from math import sqrt
from math import ceil
def mpfli(N): #minimum prime factor listのこと
    li = [i for i in range(N+1)]
    li2 = [i for i in range(N+1)]
    for i in range(2,ceil(sqrt(N+1))):
        for j in range(2*i, N + 1):
            if li[j]== li2[j]:
                if li[j] % li[i] == 0:
                    li[j] = li[i]
    return li


def pfac(n): #mpf = mpfli(N+1)
    S = set()
    while n != 1:
        m = mpf[n]
        S = S.union({m})
        n = n // m
    return S


def paerwise_coprime(A):
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            if pfac(A[i]) & pfac(A[j]) != {}:
                return False
            else:
                return True


def setwise_coprime(A):
    S = pfac(A[0])
    for i in range(1, len(A)):
        S = S & pfac(A[i])
    if S != {}:
        return False
    else:
        return True


def main():
    N = input()
    mpf = mpfli(N+1)
    A = list(map(int, input().split()))
    if pairwise_coprime(A):
        print('pairwise coprime')
    elif setwise_coprime(A):
        print('setwise coprime')
    else:
        print('not coprime')


main()

Submission status: Runtime Error

Solution code:

@author: liang
"""

"""
コーナーケース１:
    重複があるとき　not coprime(※これが誤り)
    ただし、1の重複は除く

コーナーケース:
    重複があるとき　pairwise coprime ではない
    setwise coprimeの可能性はある
    ただし、１の重複は
"""
import math
C = 10**6
#T = int(math.sqrt(C)*10**3)+1
N = int(input())
judge = [0]+[False]*C
A =list()
f = True
for a in input().split():
    if judge[int(a)] == True and int(a) != 1:
        f = False
    judge[int(a)]=True
    A.append(int(a))
d = [False]+[True]*C

#print(judge[:10])
def solve(f):
    flag = True
    #エラトステネスの篩 O(N log N)
    for i in range(2,C+1):
        count = 0
        if d[i] == True:
            for j in range(i,C+1,i):
                if judge[j] == True:
                    count += 1
                if count == 2:
                    flag = False
                    break
                d[j] = False
        if not flag:
            break
    
    if flag == True and f == True:
        return "pairwise coprime"
    ans = A[0]
    #線形探索 O(N)
    for i in range(N):
        ans = math.gcd(ans,A[i])
    #print("ans",a)
    if ans == 1:
        return "setwise coprime"
    return "not coprime"

print(solve(f))
#print(len(A))

Submission status: Runtime Error

Solution code:
import sys
import re
import queue
import collections
import math
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def gcd_list(numbers):
    return reduce(gcd, numbers)

def main():
	N = i_input()
	A = i_list()

	d = dict()

	max_A = max(A)
	count_list = []

	MAXN = 10**6+10
	sieve = [i for i in range(MAXN+1)]
	p = 2
	while p*p <= MAXN:
		if sieve[p] == p:
			for q in range(2*p,MAXN+1,p):
				if sieve[q] == q:
					sieve[q] = p
		p += 1



	for a in A:
		tmp = set()
		while a > 1:
			tmp.add(sieve[a])
			a //= sieve[a]

		for p in tmp:
			if(d.get(p,-1)==-1):
				d[p] = 1
			else:
				d[p] +=1


	if (max(d.values())==1):
		print("pairwise coprime")
	elif(gcd_list(A)==1):
		print("setwise coprime")
	else:
		print("not coprime")

	return

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
import re
import queue
import collections
import math
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def gcd_list(numbers):
    return reduce(gcd, numbers)

def factorization(a):


	return tmp


def main():
	N = i_input()
	A = i_list()

	d = dict()

	max_A = max(A)
	count_list = []

	MAXN = 10**6+10
	sieve = [i for i in range(MAXN+1)]
	p = 2
	while p*p <= MAXN:
		if sieve[p] == p:
			for q in range(2*p,MAXN+1,p):
				if sieve[q] == q:
					sieve[q] = p
		p += 1



	for a in A:
		tmp = set()
		while a > 1:
			tmp.add(sieve[a])
			a //= sieve[a]

		for p in tmp:
			if(d.get(p,-1)==-1):
				d[p] = 1
			else:
				d[p] +=1


	if (max(d.values())==1):
		print("pairwise coprime")
	elif(gcd_list(A)==1):
		print("setwise coprime")
	else:
		print("not coprime")

	return

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
import re
import queue
import collections
import math
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def gcd_list(numbers):
    return reduce(gcd, numbers)

def factorization(a):
	MAXN = 10**6+10
	sieve = [i for i in range(MAXN+1)]
	p = 2
	while p*p <= a*a:
		if sieve[p] == p:
			for q in range(2*p,a*a+1,p):
				if sieve[q] == q:
					sieve[q] = p
		p += 1

	tmp = set()
	while a > 1:
		tmp.add(sieve[a])
		a //= sieve[a]

	return tmp


def main():
	N = i_input()
	A = i_list()

	d = dict()

	max_A = max(A)
	count_list = []

	for a in A:
		tmp = set(factorization(a))
		for p in tmp:
			if(d.get(p,-1)==-1):
				d[p] = 1
			else:
				d[p] +=1


	if (max(d.values())==1):
		print("pairwise coprime")
	elif(gcd_list(A)==1):
		print("setwise coprime")
	else:
		print("not coprime")

	return

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
import re
import queue
import collections
import math
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def gcd_list(numbers):
    return reduce(gcd, numbers)

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の倍数を除去
        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 main():
	N = i_input()
	A = i_list()

	max_A = max(A)
	count_list = []
	for i in range(0,max_A):
		count_list.append(0)

	for a in A:
		for p in (list(set(get_primenumber(a)))):
			count_list[p-1] +=1

	if (max(count_list) <=1 ):
		print("pairwise coprime")
	elif(gcd_list(A)==1):
		print("setwise coprime")
	else:
		print("not coprime")

	return

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
import re
import queue
import collections
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def gcd_list(numbers):
    return reduce(gcd, numbers)

def prime_decomposition(n):
	i = 2
	table = []
	while i * i <= n:
		while n % i == 0:
			n //= i
			table.append(i)
		i += 1
	if n > 1:
		table.append(n)
	return table


def main():
	N = i_input()
	A = i_list()

	max_A = max(A)
	count_list = []
	for i in range(0,max_A):
		count_list.append(0)

	for a in range(A):
		for p in range(list(set(prime_decomposition(a)))):
			count_list[p-1] +=1

	if (max(count_list) <=1 ):
		print("pairwise coprime")
	elif(gcd_list(A)==1):
		print("setwise coprime")
	else:
		print("not coprime")

	return

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
import re
import queue
import collections
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def myGcd(X):
	if(X.length <=2):
		return gcd(X[0],X[1])
	else:
		return gcd(X[X.length-1],myGcd(X[0:X.length-2]))

def prime_decomposition(n):
	i = 2
	table = []
	while i * i <= n:
		while n % i == 0:
			n //= i
			table.append(i)
		i += 1
	if n > 1:
		table.append(n)
	return table


def main():
	N = i_input()
	A = i_list()

	tmpP = []
	P = []
	for a in A:
		for p in prime_decomposition(a):
			tmpP.append(p)
		P.extend(list(set(tmpP)))
		tmpP.clear()

	c = collections.Counter(P)
	
	if(c.most_common()[0][1]<=1):
		print("pairwise coprime")
	elif(myGcd(A) ==1):
		print("setwise coprime")
	else:
		print("not coprime")


	return

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
import re
import queue
import collections
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def gcd_list(numbers):
    return reduce(gcd, numbers)

def prime_decomposition(n):
	i = 2
	table = []
	while i * i <= n:
		while n % i == 0:
			n //= i
			table.append(i)
		i += 1
	if n > 1:
		table.append(n)
	return table


def main():
	N = i_input()
	A = i_list()

	tmpP = []
	P = []
	for a in A:
		for p in prime_decomposition(a):
			tmpP.append(p)
		P.extend(list(set(tmpP)))
		tmpP.clear()

	c = collections.Counter(P)
	
	if(c.most_common()[0][1]<=1):
		print("pairwise coprime")
	elif(gcd_list(A) ==1):
		print("setwise coprime")
	else:
		print("not coprime")


	return

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
M=int(input())
B=list(map(int,input().split()))
import numpy as np
import math
import sys
sys.setrecursionlimit(10**7)
def coprime(A,N):
    X=np.zeros(A[N-1]+1)
    for i in range(int(math.sqrt(A[N-1]))+1):
        if i>=2:
            X[i::i]=1
        sumx=sum(X[A[j]] for j in range(N))
        if sumx==N:
            print('not coprime')
            return
        elif sumx>=2:
            print('setwise coprime')
            return
    print("pairwise coprime")
    return

coprime(B,M)

Submission status: Runtime Error

Solution code:
M=int(input())
B=list(map(int,input().split()))
import numpy as np
import math
import sys
sys.setrecursionlimit(10**7)
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))
def coprime(A,N):
    X=np.zeros(A[N-1]+1)
    for i in range(int(math.sqrt(A[N-1]))+1):
        if i>=2:
            X[i::i]=1
        sumx=sum(X[A[j]] for j in range(N))
        if sumx==N:
            print('not coprime')
            return
        elif sumx>=2:
            print('setwise coprime')
            return
    print("pairwise coprime")
    return

coprime(B,M)

Submission status: Runtime Error

Solution code:
M=int(input())
B=list(map(int,input().split()))
import numpy as np
import math
def coprime(A,N):
    X=np.zeros(A[N-1]+1)
    for i in range(int(math.sqrt(A[N-1]))+1):
        if i>=2:
            X[i::i]=1
        sumx=sum(X[A[j]] for j in range(N))
        if sumx==N:
            print('not coprime')
            return
        elif sumx>=2:
            print('setwise coprime')
            return
    print("pairwise coprime")
    return

coprime(B,M)

Submission status: Runtime Error

Solution code:
M=int(input())
B=list(map(int,input().split()))
import numpy as np
import math
def coprime(A,N):
    X=np.zeros(A[N-1]+1)
    for i in range(int(math.sqrt(A[N-1]))+1):
        if i>=2:
            X[i::i]=1
        sumx=sum(X[A[j]] for j in range(N))
        if sumx==N:
            print('not coprime')
            return
        elif sumx>=2:
            print('setwise coprime')
    print("pairwise coprime")
    return

coprime(B,M)

Submission status: Runtime Error

Solution code:
M=int(input())
B=list(map(int,input().split()))
import numpy as np
import math
import sys

def coprime(A,N):
    X=np.zeros(A[N-1]+1)
    for i in range(int(math.sqrt(A[N-1]))+1):
        if i>=2:
            X[i::i]=1
        sumx=sum(X[A[j]] for j in range(N))
        if sumx==N:
            print('not coprime')
            return
        elif sumx>=2:
            print('setwise coprime')
    print("pairwise coprime")
    return

coprime(B,M)

Submission status: Runtime Error

Solution code:
N=int(input())
B=list(map(int,input().split()))
import numpy as np
import math
import sys

def coprime(A):
    X=np.zeros(A[N-1]+1)
    count=0
    for i in range(int(math.sqrt(A[N-1]))+1):
        if i>=2:
            X[i::i]=1
        sumx=sum(X[A[j]] for j in range(N))
        if sumx==N:
            print('not coprime')
            return
        elif sumx>=2:
            print('setwise coprime')
            return
    print('pairwise coprime')
    return

coprime(B)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
import numpy as np
X=np.zeros(A[N-1]+1)
import math
import sys
count=0
def coprime(X):
    for i in range(int(math.sqrt(A[N-1]))+1):
        if i>=2:
            X[i::i]=1
        sumx=sum(X[A[j]] for j in range(N))
        if sumx==N:
            print('not coprime')
            return
        elif sumx>=2:
            print('setwise coprime')
            return
    print('pairwise coprime')
    return

coprime(X)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
import numpy as np
X=np.zeros(A[N-1]+1)
import math
import sys
count=0
for i in range(int(math.sqrt(A[N-1]))+1):
    if i>=2:
        X[i::i]=1
    sumx=sum(X[A[j]] for j in range(N))
    if sumx==N:
        print('not coprime')
        sys.exit([0])
    elif sumx>=2:
        print('setwise coprime')
        sys.exit([0])
print('pairwise coprime')

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
import numpy as np
X=np.zeros(A[N-1]+1)
import math
import sys
count=0
for i in range(int(math.sqrt(A[N-1]))+1):
    if i>=2:
        X[i::i]=1
    sumx=sum(X[A[j]] for j in range(N))
    if sumx==N:
        print('not coprime')
        sys.exit()
    elif sumx>=2:
        print('setwise coprime')
        sys.exit()
print('pairwise coprime')

Submission status: Runtime Error

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

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

g = 0

A.sort()

for item in A:
    g = gcc(g, item)

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

primes = []

is_prime = [True] * 1100000
primes = []

is_prime[0] = is_prime[1] = False

for i in range(2, 1100000):
    if not is_prime[i]:continue
    for j in range(i*i, 1100000, i):
        is_prime[j] = False
    primes.append[i]

A_prime = [item for item in A if is_prime[item]]
A_notprime = [item for item in A if not is_prime[item]]

used = [False] * 1100000

for item in A_prime:
    used[item] = True

for a in A_notprime:
    for p in primes:
        if a == 1:break
        if a % p != 0:continue

        if used[p]:
            print("setwise coprime")
            #互いに素でない（共通素因数pで割れる）ペアがAの中にあると，それはsetwise_coprime
            exit()

        used[p] = True

        while a > p:
            a //= p

print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import sys
import math
from io import StringIO
import unittest


def resolve():
    N, = map(int, input().split())
    As = list(map(int, input().split()))
    # allprimes = []
    common_primes = None
    all_primes = set()
    all_uniq_primes_n = 0
    d = get_d(1100000)
    for i, a in enumerate(As):

        primes = get_primes_fast(a, d, set())
        # print(f'a {a} primes:{primes}')
        all_uniq_primes_n += len(primes)
        all_primes = all_primes | primes
        if i == 0:
            common_primes = primes
        else:
            # print(f'bef {common_primes} primes:{primes}')
            common_primes = primes & common_primes
            # print(f'aft {common_primes}')

    if len(common_primes) > 0:

        print('not coprime')

    elif all_uniq_primes_n == len(all_primes):
        print('pairwise coprime')
    else:
        print('setwise coprime')


def get_primes_fast(a, d, primes):
    is_div = False
    if a==1:
        return primes
    if d[a] != a:
        is_div = True
        primes.add(d[a])
        primes = get_primes_fast(int(a / d[a]), d, primes)
    if not is_div:
        primes.add(a)
    return primes


def get_primes(a, start_n, primes):
    is_div = False
    for i in range(start_n, math.floor(math.sqrt(a) + 1)):
        if a % i == 0:
            is_div = True
            primes.add(i)
            get_primes(int(a / i), i, primes)
    if not is_div:
        primes.add(a)
    return primes


def get_d(A):
    d = [0] * (A + 1)
    d[1]=1
    for i in range(2, A + 1):
        for k in range(1, int(A / i)):
            if d[i * k] == 0:
                d[i * k] = i
    return d


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(output, out)

    def test_入力例_1(self):
        input = """3
1 4 49"""
        output = """pairwise coprime"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
6 10 15"""
        output = """setwise coprime"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """3
6 10 16"""
        output = """not coprime"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()
    # unittest.main()

Submission status: Runtime Error

Solution code:
import sys
import math
from io import StringIO
import unittest


def resolve():
    N, = map(int, input().split())
    As = list(map(int, input().split()))
    # allprimes = []
    common_primes = None
    all_primes = set()
    all_uniq_primes_n = 0
    d = get_d(1100000)
    for i, a in enumerate(As):

        primes = get_primes_fast(a, d, set())
        # print(f'a {a} primes:{primes}')
        all_uniq_primes_n += len(primes)
        all_primes = all_primes | primes
        if i == 0:
            common_primes = primes
        else:
            # print(f'bef {common_primes} primes:{primes}')
            common_primes = primes & common_primes
            # print(f'aft {common_primes}')

    if len(common_primes) > 0:

        print('not coprime')

    elif all_uniq_primes_n == len(all_primes):
        print('pairwise coprime')
    else:
        print('setwise coprime')


def get_primes_fast(a, d, primes):
    is_div = False
    if a==1:
        return primes
    if d[a] != a:
        is_div = True
        primes.add(d[a])
        get_primes_fast(int(a / d[a]), d, primes)
    if not is_div:
        primes.add(a)
    return primes


def get_primes(a, start_n, primes):
    is_div = False
    for i in range(start_n, math.floor(math.sqrt(a) + 1)):
        if a % i == 0:
            is_div = True
            primes.add(i)
            get_primes(int(a / i), i, primes)
    if not is_div:
        primes.add(a)
    return primes


def get_d(A):
    d = [0] * (A + 1)
    d[1]=1
    for i in range(2, A + 1):
        for k in range(1, int(A / i)):
            if d[i * k] == 0:
                d[i * k] = i
    return d


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(output, out)

    def test_入力例_1(self):
        input = """3
1 4 49"""
        output = """pairwise coprime"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
6 10 15"""
        output = """setwise coprime"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """3
6 10 16"""
        output = """not coprime"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()
    # unittest.main()