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:
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

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

#print(judge[:10])
def solve(f):
    #重複時
    if f:
        return "not coprime"
    flag = True
    #エラトステネスの篩 O(N log N)
    for i in range(2,T+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:
        return "pairwise coprime"
    ans = A[0]
    #線形探索 O(N)
    for i in range(N):
        ans = math.gcd(ans,A[i])
    if ans == 1:
        return "setwise coprime"
    return "not coprime"

print(solve(f))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

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

#print(judge[:10])
def solve(f):
    #重複時
    if f:
        return "not coprime"
    flag = True
    #エラトステネスの篩 O(N log N)
    for i in range(2,T+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:
        return "pairwise coprime"
    ans = A[0]
    #線形探索 O(N)
    for i in range(N):
        ans = math.gcd(ans,A[i])
    if ans == 1:
        return "setwise coprime"
    return "not coprime"

print(solve(f))

Submission status: Wrong Answer

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 i in range(0,max(A)):
		count_list.append(0)

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

		for p in tmp:
			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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

import math
C = 10**6
T = 10**3
N = int(input())
judge = [0]+[False]*C
A =list()
f = False
for a in input().split():
    if judge[int(a)] == True and int(a) != 1:
        f = True
    judge[int(a)]=True
    A.append(int(a))
d = [False]+[True]*C

#print(judge[:10])
def solve(f):
    #重複時
    if f:
        return "not coprime"
    flag = True
    #エラトステネスの篩 O(N log N)
    for i in range(2,T+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:
        return "pairwise coprime"
    ans = A[0]
    #線形探索 O(N)
    for i in range(N):
        ans = math.gcd(ans,A[i])
    if ans == 1:
        return "setwise coprime"
    return "not coprime"

print(solve(f))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

import math
C = 10**6
T = 10**3
N = int(input())
judge = [0]+[False]*C
A =list()
f = False
for a in input().split():
    if judge[int(a)] == True:
        f = True
    judge[int(a)]=True
    A.append(int(a))
d = [False]+[True]*C

#print(judge[:10])
def solve():
    #重複時
    #if f:
    #    return "not coprime"
    flag = True
    #エラトステネスの篩 O(N log N)
    for i in range(2,T+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:
        return "pairwise coprime"
    ans = A[0]
    #線形探索 O(N)
    for i in range(N):
        ans = math.gcd(ans,A[i])
    if ans == 1:
        return "setwise coprime"
    return "not coprime"

print(solve())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

import math
C = 10**6
T = 10**3
N = int(input())
judge = [0]+[False]*C
A =list()
f = False
for a in input().split():
    if judge[int(a)] == True:
        f = True
    judge[int(a)]=True
    A.append(int(a))
d = [False]+[True]*C

#print(judge[:10])
def solve(f):
    #重複時
    if f:
        return "not coprime"
    flag = True
    #エラトステネスの篩 O(N log N)
    for i in range(2,T+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:
        return "pairwise coprime"
    ans = A[0]
    #線形探索 O(N)
    for i in range(N):
        ans = math.gcd(ans,A[i])
    if ans == 1:
        return "setwise coprime"
    return "not coprime"

print(solve(f))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

import math
C = 10**6
T = 10**3
N = int(input())
judge = [0]+[False]*C
A =list()
f = False
for a in input().split():
    if judge[int(a)] == True:
        f = True
    judge[int(a)]=True
    A.append(int(a))
d = [False]+[True]*C

#print(judge[:10])
def solve(f):
    #重複時
    if f:
        return "not coprime"
    flag = True
    #エラトステネスの篩 O(N log N)
    for i in range(2,T+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:
        return "pairwise coprime"
    ans = A[0]
    #線形探索 O(N)
    for i in range(0,N):
        ans = math.gcd(ans,A[i])
    if ans == 1:
        return "setwise coprime"
    return "not coprime"

print(solve(f))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

import math
C = 10**6
T = 10**3
N = int(input())
judge = [0]+[False]*C
A =list()
for a in input().split():
    judge[int(a)]=True
    A.append(int(a))
d = [False]+[True]*C

#print(judge[:10])
def solve():    
    flag = True
    #エラトステネスの篩 O(N log N)
    for i in range(2,T+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:
        return "pairwise coprime"
    ans = A[0]
    #線形探索 O(N)
    for i in range(0,N):
        ans = math.gcd(ans,A[i])
    if ans == 1:
        return "setwise coprime"
    return "not coprime"

print(solve())

Submission status: Wrong Answer

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(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)

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

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

    return arr


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

	d = dict()

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

	for a in A:
		for p in ((set(factorization(a)))):
			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: Wrong Answer

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(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)

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

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

    return arr


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 ((set(factorization(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: Wrong Answer

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()
	
	if(P.count != list(set(P)).count):
		print("pairwise coprime")
	elif(gcd_list(A) ==1):
		print("setwise coprime")
	else:
		print("not coprime")


	return

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

import math
G = A[0]

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

if G > 1:
	print('not coprime')
	exit()
    
import collections as col
chinbi = col.deque(A)

while chinbi:
	q = chinbi.popleft()
	count = 0
	for i in range (0, len(chinbi)):
		if chinbi[i]%q == 0:
			count+=1
	if count > 1:
		print('setwise coprime')
		exit()
        
print('pairwise coprime')

Submission status: Wrong Answer

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

import math
G = A[0]

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

Submission status: Wrong Answer

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

import math
G = A[0]

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

if G > 1:
	print('not coprime')
	exit()
    
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]

for i in range (0, len(Primes)):
	count = 0
	for j in range (0, len(A)):
		if A[j]%Primes[i] == 0:
			count+=1
	if count > 1:
		print('setwise coprime')
		exit()

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
a = list(map(int,input().split()))
m = max(a)
c = [0] * (m+1)

for i in a:
  c[i] += 1

pairwise = True
for i in range(2, m, 1):
  cnt = 0
  for j in range(i, m, i):
    cnt += c[j]
    if cnt > 1:
      pairwise = False
      break
if pairwise:
  print("pairwise coprime")
  exit()

g = 0
for i in range(N):
  g = math.gcd(g, a[i])
if g == 1:
  print("setwise coprime")
  exit()

print("not coprime")

Submission status: Wrong Answer

Solution code:
def get_sieve_of_eratosthenes(n):
    table = [i if i % 2 else 2 for i in range(n + 1)]
    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 table, prime + data
        prime.append(p)
        next_data = []
        for e in data:
            if e % p != 0:
                next_data.append(e)
            else:
                table[e] = p
        data = next_data


N = int(input())
A = [int(i) for i in input().split()]
M = max(A)
if M > 2:
    table, primes = get_sieve_of_eratosthenes(M)
    Divisor = [0 for i in range(M + 1)]
    result = "pairwise coprime"
    for a in A:
        aa = a
        while True:
            Divisor[table[aa]] += 1
            if Divisor[table[aa]] == N:
                result = "not coprime"
            if 1 < Divisor[table[aa]] < N:
                result = "setwise coprime"


            div = table[aa]
            while not aa % div:
                aa = aa // div
            if aa == 1:
                break

    Max_div = max(Divisor)
    #print(Max_div)
    print(result)


else:
    n = A.count(2)
    if n <= 1:
        print("pairwise coprime")
    elif n == N:
        print("not coprime")
    else:
        print("setwise coprime")

Submission status: Wrong Answer

Solution code:
M=int(input())
B=list(map(int,input().split()))
B=sorted(B)
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(A[N-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: Wrong Answer

Solution code:
M=int(input())
B=list(map(int,input().split()))
B=sorted(B)
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(A[N-1]):
        if i>=2:
            X[i::i]=1
            print(i)
        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: Wrong Answer

Solution code:
M=int(input())
B=list(map(int,input().split()))
B=sorted(B)
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: Wrong Answer

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

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

primes = [p for p in range(1100) if is_prime[p]]
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 == 0:
            a //= p

print("pairwise coprime")

Submission status: Wrong Answer

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

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

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

primes = [p for p in range(1100) if is_prime[p]]
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

    if a > 1:
        if used[a]:
            print("setwise coprime")
            exit()
        used[a] = True


print("pairwise coprime")

Submission status: Wrong Answer

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: Wrong Answer

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()

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 = [p for p in range(1100) if is_prime[p]]

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: Wrong Answer

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()

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 = [p for p in range(1100) if is_prime[p]]

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: Wrong Answer

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

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

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

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 = [p for p in range(1100) if is_prime[p]]

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: Wrong Answer

Solution code:
from numba import njit

@njit
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

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

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

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 = [p for p in range(1100) if is_prime[p]]

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 % 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: Wrong Answer

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
    for i,a in enumerate(As):

        primes = get_primes(a, 2, 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(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


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
3 4 5"""
        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()

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
ans1 = "pairwise coprime"
ans2 = "setwise coprime"
ans3 = "not coprime"

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

if a==1:
    b = True
    l = [0]*(10**6+1)
    x = [0]*(10**6+1)
    x[0]=1
    x[1]=1
    for i in range(2, 10**6+1):
        if x[i]==0:
            for j in range(i, 10**6+1, i):
                x[j]=i

    #print(a)
    for y in A:
        s=set()
        if y==x[y]:
            s |= {y}        #素因数のリスト
        else:
            while y!=x[y]: #素数になるまで
                s|={x[y]}  
                y//=x[y]
                if y==x[y]:
                    s|={x[y]}
                    break
        for i in s:
            l[i]+=1
            if l[i]>=2:
                b=False
                break
                
        
    if b:
        print(ans1)
    else:
        print(ans2)
        
        
    
else:
    print(ans3)