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 math
from functools import reduce

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

cut = [0 for _ in range(MAX+1)]
for i in range(MAX, 1, -1):
    for j in range(i, MAX+1, i):
        cut[j] = i

if reduce(math.gcd, A) != 1:
    print('not coprime')
    exit()

already = set()
for a in A:
    now = set()
    while a != 1:
        if cut[a] in already:
            print('setwise coprime')
            exit()
        a //= cut[a]
        now.add(cut[a])
    already |= now

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
primeset = {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}

def gcd(n,m):
    while n:
        m,n = n,m%n
    return m

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

a = 0

def setwise():
    global N,A,a
    a = A[0]
    for i in range(1,N):
        a = gcd(a,A[i])
    return (a == 1)

def pairwise():
    global N,A,a,primeset
    for p in primeset:
        a = 0
        for i in range(N):
            a += (A[i] % p == 0)
        if a > 1:
            return False
    return True

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

Submission status: Wrong Answer

Solution code:
from math import gcd
from functools import reduce

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

def primes(n):
    is_prime = [False] * 2 + [True] * (n - 1)
    for i in range(2, int(n ** 0.5) + 1): # 素数候補
        if not is_prime[i]: continue
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def pairwise_coprime(a):
    max_a = max(a)
    in_a = [False] * (max_a + 1)
    for num in a:
        if in_a[num]:
            return False
        in_a[num] = True

    ps = primes(max_a)  # max(a)以下の素数

    for p in ps:
        cnt = 0
        for i in range(p, max_a + 1, p):
            if in_a[i]:
                cnt += 1
            if cnt > 1:
                return False

    return True



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

if gcd_list(a) == 1:  # setwise coprime or pairwise coprime
    if pairwise_coprime(a):
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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

cut = [0 for _ in range(MAX+1)]
for i in range(MAX+1, 1, -1):
    for j in range(i, MAX+1, i):
        cut[j] = i

if reduce(math.gcd, A) != 1:
    print('not coprime')
    exit()

already = set()
for a in A:
    now = set()
    while a != 1:
        if cut[a] in already:
            print('setwise coprime')
            exit()
        a //= cut[a]
        now.add(cut[a])
    already |= now

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
#ceilevenoddformula
import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations
#map(int,input().split())
#int(x) for x in input().split()
def gcd(a, b) : 
    if (a == 0) : 
        return b 
      
    if (b == 0) : 
        return a   
    k = 0
      
    while(((a | b) & 1) == 0) : 
        a = a >> 1
        b = b >> 1
        k = k + 1
          
 
    while ((a & 1) == 0) : 
        a = a >> 1
  
    # From here on, 'a' is always odd.  
    while(b != 0) : 
          
        # If b is even, remove all  
        # factor of 2 in b  
        while ((b & 1) == 0) : 
            b = b >> 1
  
        # Now a and b are both odd. Swap if 
        # necessary so a <= b, then set  
        # b = b - a (which is even). 
        if (a > b) : 
          
            # Swap u and v. 
            temp = a 
            a = b 
            b = temp 
  
        b = (b - a) 
      
    # restore common factors of 2  
    return (a << k) 


def primeFactors(n,l): 
    q=set()    
    f=0
    while n % 2 == 0: 
    	if l[2] and f==0:
    		return False
    	l[2]=True
    	n = n / 2     
    	f=1 

    for i in range(3,int(math.sqrt(n))+1,2): 
        while n % i== 0:
        	if l[i]:
        		return False
        	l[i]=True
        	n = n / i 
              
    if n > 2: 
    	if l[n]:
    		return False
    	l[n]=True

    #l=l.union(q)
    return True

n=int(input())
l=[int(x) for x in input().split()]
#l.sort()
d={i:False for i in range(1,max(l)+1)}
ans=1
for i in range(n):
	f=primeFactors(l[i],d)
	if not f:
		ans=0
		break



if ans:
	print('pairwise coprime')
else:
	a=l[0]
	b=l[1]
	gc=gcd(a,b)
	for i in range(2,n):
		gc=gcd(gc,l[i])
		if gc==1:
			break
	if gc==1:
		print('setwise coprime')
	else:
		print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

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

def eratosthenes(n):
    checker = [0] * (n+1)
    checker[0] = 1 #素数でない
    checker[1] = 0 #素数でない
    for i in range(2, n):
        if checker[i] == 0:
            for j in range(2, n // i + 1):
                checker[i * j] = i
    return checker

def check_by_eratosthenes(x, checker):
    if checker[x] == 0:
        checker[x] = -1
        return True
    if checker[x] < 0 or checker[checker[x]] < 0:
        return False
    else:
        y = x // checker[x]
        if checker[y] != checker[x] and y != checker[x]:
            checker[checker[x]] = -1
        checker[x] = -1
        return check_by_eratosthenes(y, checker)

n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n):
    if a[i] != 1:
        break
a = a[i:]
n -= i
if n == 1:
    print("pairwise coprime")
    quit()

checker = eratosthenes(a[-1])
x = a[0]

pairwise = True
setwise = True
for i in range(n):
    if x != 1:
        x = gcd(x, a[i])
    if pairwise:
        pairwise = check_by_eratosthenes(a[i], checker)

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

Submission status: Wrong Answer

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

N = INT()
A = LIST()

if reduce(gcd, A) != 1:
    print("not coprime")
    exit()
ma = max(A)
p = list(range(ma+1))
for x in range(2, int(ma ** 0.5) + 1):
    if p[x]:
        for i in range(x + x, ma+1, x):
            p[i] = x

s = [set() for _ in range(N)]

for i, x in enumerate(A):
    while x != 1:
        s[i].add(p[x])
        x //= p[x]

# l = sum(len(x) for x in s)
# merge = lambda x, y: x|y
# print("pairwise coprime" if l == len(reduce(merge, s)) else "setwise coprime")

Submission status: Wrong Answer

Solution code:
def max(a,b):
    if a>b:
        return a
    else:
        return b
 
def min(a,b):
    if a>b:
        return b
    else:
        return a
 
def gcd(a,b):
    a,b = max(a,b),min(a,b)
    while a%b!=0:
        a,b = b,a%b
    return b
 
 
def gcdl(A):
    if len(A)==2:
        return gcd(A[0],A[1])
    elif len(A)==1:
        return A[0]
    else:
        return gcd(gcdl(A[:len(A)//2]),gcdl(A[len(A)//2:]))


def sieve_of_eratosthenes(n):
    p = 2
    D = [0]*(n+1)
    while p**2<=n:
        if D[p]==0:
            k = p*p
            while k <= n:
                if D[k] == 0:
                    D[k] = p
                k += p
        p+=1
    return D

import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    D = sieve_of_eratosthenes(1000000)
    #print(D)
    N = int(input())
    A = list(map(int,input().split()))

    F = set([])
    flag = True
    for a in A:
        b = a
        fact = set([])
        while D[b]>0:
            fact.add(D[b])
            b//=D[b]
        fact.add(b)
        if len(F & fact)>0:
            flag=False
            break
        F = F | fact

    if flag:
        print("pairwise coprime")
    else:
        if gcdl(A)==1:
            print("setwise coprime")
        else:
            print("not coprime")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#ceilevenoddformula
import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations
#map(int,input().split())
#int(x) for x in input().split()
def gcd(a, b) : 
    if (a == 0) : 
        return b 
      
    if (b == 0) : 
        return a   
    k = 0
      
    while(((a | b) & 1) == 0) : 
        a = a >> 1
        b = b >> 1
        k = k + 1
          
 
    while ((a & 1) == 0) : 
        a = a >> 1
  
    # From here on, 'a' is always odd.  
    while(b != 0) : 
          
        # If b is even, remove all  
        # factor of 2 in b  
        while ((b & 1) == 0) : 
            b = b >> 1
  
        # Now a and b are both odd. Swap if 
        # necessary so a <= b, then set  
        # b = b - a (which is even). 
        if (a > b) : 
          
            # Swap u and v. 
            temp = a 
            a = b 
            b = temp 
  
        b = (b - a) 
      
    # restore common factors of 2  
    return (a << k) 


def primeFactors(n,l): 
    q=set()    
    while n % 2 == 0: 
    	if l[2]:
    		return False
    	l[2]=True
    	n = n / 2      

    for i in range(3,int(math.sqrt(n))+1,2): 
        while n % i== 0:
        	if l[i]:
        		return False
        	l[i]=True
        	n = n / i 
              
    if n > 2: 
    	if l[n]:
    		return False
    	l[n]=True

    #l=l.union(q)
    return True

n=int(input())
l=[int(x) for x in input().split()]
l.sort()
d={i:False for i in range(1,max(l)+1)}
ans=1
for i in range(n):
	f=primeFactors(l[i],d)
	if not f:
		ans=0
		break



if ans:
	print('pairwise coprime')
else:
	a=l[0]
	b=l[1]
	gc=gcd(a,b)
	for i in range(2,n):
		gc=gcd(gc,l[i])
		if gc==1:
			break
	if gc==1:
		print('setwise coprime')
	else:
		print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
A = list(map(int, input().split()))
sieve = [1] * (10**6+1)
for i in range(2, 10**6 + 1):
	if sieve[i] == 1:
		sieve[i] = i
		j = 2
		while(j * i <= 10**6):
			sieve[j * i] = i
			j += 1

g = A[0]
a = 0
for i in range(1, N):
	g = gcd(g, A[i])
	if A[i] == 1:
		a += 1
	
if g != 1:
	print("not coprime")
else:
	if a > 1:
		print("setwise coprime")
		exit()
	s = set()
	for i in range(N):
		st = set()
		while(A[i] > 1):
			d = sieve[A[i]]
			st.add(d)
			A[i] //= d
		for p in st:
			if p in s:
				print("setwise coprime")
				exit()
			s.add(p)
	print("pairwise coprime")

Submission status: Wrong Answer

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

if 1 in A:
    print('not coprime')
    exit()

A.sort()
R = int(A[-1]**0.5)

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(R+2)
l = 0

for i in range(2, R+2):
    if checked[i]:
        continue
    
    # 調べる範囲を狭める
    while A[l] < i and l < N-1:
        l += 1
    if l == N-1:
        break
    
    # iで割り切れるAiの個数を数える
    tmp = 0
    for j in range(l, N):
        if A[j]%i == 0:
            tmp += 1
    # 2個以上あればnot pairwise coprime
    # N個あれば not setwise coprime
    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    
    if is_setwise_coprime == False:
        break
    
    # iの倍数はチェック済みにする
    n = i
    while n < R+2:
        checked[n] = 1
        n += i
    # print(checked, l)
if is_pairwise_coprime:
    print('pairwise coprime')
elif is_setwise_coprime:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
A = list(map(int, input().split()))
sieve = [1] * (10**6+1)
for i in range(2, 10**6 + 1):
	if sieve[i] == 1:
		sieve[i] = i
		j = 2
		while(j * i <= 10**6):
			sieve[j * i] = i
			j += 1
sieve[1] = 0

g = A[0]
a = 0
for i in range(1, N):
	g = gcd(g, A[i])
	if A[i] == 1:
		a = 1
	
if g != 1:
	print("not coprime")
else:
	if a == 1:
		print("setwise coprime")
		exit()
	s = set()
	for i in range(N):
		st = set()
		while(A[i] > 1):
			d = sieve[A[i]]
			st.add(d)
			A[i] //= d
		for p in st:
			if p in s:
				print("setwise coprime")
				exit()
			s.add(p)
	print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
def gcbd_list(numbers):
    return reduce(math.gcd, numbers)
N = int(input())
A = list(map(int, input().split()))
P = [False] * (10**6+1)
c = True
for i in range(N):
    if A[i]>10**3:
        if P[A[i]] == True:
            c = False
        P[A[i]] = True
    for j in range(2, 10**3+1):
        if A[i] % j == 0:
            if P[j] == True:
                c = False
            P[j] = True
if c == True:
    print('pairwise coprime')
    exit()
if gcbd_list(A) == 1:
    print('setwise coprime')
    exit()
print('not coprime')

Submission status: Wrong Answer

Solution code:
N = 1000001

spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
t = None, 'setwise', 'pairwise', 'not'
r = 0
input()
u = set()
i = None
for x in map(int, input().split()):
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r |= 1
    s.add(p)
    x //= p
  u |= s
  if i: i &= s
  else: i = s
if i:
  r |= 2
print(t[r], 'coprime')

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
def is_primes(n):
    primes = [1]*n
    primes[0] =0
    primes[1] =0
    for i in range(2,int(n**0.5)+1):
        if primes[i] ==1:
            for j in range(2*i,n,i):
                primes[j] = 0
    return primes

def factorize(n,prms):
    b = 2
    fct = []
    while b * b <= n:
        if not prms[b]:
            b+=1
            continue
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct

n =ni()
A = lma()
mx= 2*10**6
prms = is_primes(mx+1)
d=collections.Counter()
for a in A:
    fct = factorize(a,prms)
    #print(fct)
    for fc,cnt in fct:
        d[fc]+=1
        if d[fc]==n:
            break
f1=True # pp or sp
f2=True # sp or other
for num,cnt in d.items():
    if cnt==n:
        f2=False #other
        break
    else:
        if cnt==1:
            pass
        else:
            f1=False
            break
if f2==False:
    print("not coprime")
elif f1 and f2:
    print("pairwise coprime")
elif f1==False:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    mylist = LI()
    max_num = max(mylist)
    max_num2 = int(math.sqrt(max_num))
    D = [True]* (max_num+1)
    mylist = set(mylist)
    setwise = True
    pairwise = True

    for i in range(2, max_num2+1):
        temp = 0
        if D[i]:
            for j in range(i, max_num+1, i):
                D[j] = False
                if j in mylist:
                    temp+=1
        if temp == N:
            print("not coprime")
            sys.exit()
        if temp >= 2:
            pairwise = False
    
    if pairwise:
        print("pairwise coprime")
    else:
        print("setwise coprime")
                    

            
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
from collections import deque

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

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    a,b = b,a
while a % b != 0:
    a, b = b, a % b
    if n == 2 and b == 1:
        ans = "pairwise coprime"
        failed = True

for i in range(2, n):
    a = als[i]
    if a < b:
        a,b = b,a 
    while a % b != 0:
        a, b = b, a % b
if b == 1:
    ans = "setwise coprime"
    # break

existeven = False

failed = False

for i in range(n):
    if als[i] >= 2 and als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

maxa = max(als)

afterchecklist = deque([])


if not failed:
    for i in range(3, int(math.sqrt(maxa))+2, 2):
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                afterchecklist.append(als[j]/i)
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        for i in list(afterchecklist):
            existfactrial = False
            failed = False
            for j in range(n):
                if als[j] >= i and als[j]%i == 0:
                    if existfactrial:
                        failed = True
                        break
                    else:
                        existfactrial = True
            if failed:
                break
        if not failed:
            ans = "pairwise coprime"

print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
A = list(map(int, input().split()))
sieve = [1] * (10**6+1)
for i in range(2, 10**3):
	if sieve[i] == 1:
		sieve[i] = i
		j = 2
		while(j * i <= 10**6):
			sieve[j * i] = i
			j += 1
sieve[1] = 0

g = A[0]
a = 0
for i in range(1, N):
	g = gcd(g, A[i])
	if A[i] == 1:
		a = 1
	
if g != 1:
	print("not coprime")
else:
	if a == 1:
		print("setwise coprime")
		exit()
	s = set()
	for i in range(N):
		st = set()
		while(A[i] > 1):
			d = sieve[A[i]]
			if not(d in st) and d in s:
				print("setwise coprime")
				exit()
			s.add(d)
			st.add(d)
			A[i] //= d
	print("pairwise coprime")

Submission status: Wrong Answer

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


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


g = a[0]
for x in a[1:]:
    g = gcd(g, x)

if g > 1:
    print('not coprime')
    exit()


exist = [False] * (10**6+1)
for x in a:
    y = x
    if x % 2 == 0:
        if exist[2]:
            print('setwise coprime')
            exit()
        while y % 2 == 0:
            y //= 2
        exist[2] = True
    div = 3
    while div * div <= x:
        if x % div == 0:
            if exist[div]:
                print('setwise coprime')
                exit()
            while y % div == 0:
                y //= div
            exist[div] = True
        div += 2
    if y > 1:
        exist[y] = True
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    mylist = LI()
    max_num = max(mylist)
    max_num2 = int(math.sqrt(max_num))
    D = [True]* (max_num+1)
    mylist = set(mylist)
    setwise = True
    pairwise = True

    for i in range(2, max_num2+1):
        temp = 0
        if D[i]:
            for j in range(i, max_num+1, i):
                D[j] = False
                if j in mylist:
                    temp+=1
        if temp == N:
            print("not coprime")
            sys.exit()
        if temp >= 2:
            setwise = False
    
    if setwise:
        print("pairwise coprime")
    else:
        print("setwise coprime")
                    

            
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
from collections import deque

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

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    a,b = b,a
while a % b != 0:
    a, b = b, a % b
    if n == 2 and b == 1:
        ans = "pairwise coprime"
        failed = True

for i in range(2, n):
    a = als[i]
    if a < b:
        a,b = b,a 
    while a % b != 0:
        a, b = b, a % b
if b == 1:
    ans = "setwise coprime"
    # break

existeven = False

failed = False

for i in range(n):
    if als[i] >= 2 and als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

maxa = max(als)

afterchecklist = deque([])


if not failed:
    for i in range(3, int(math.sqrt(maxa))+2, 2):
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                afterchecklist.append(als[j]/i)
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        for i in list(afterchecklist):
            existfactrial = False
            failed = False
            for j in range(n):
                if als[j] >= i and als[j]%i == 0:
                    if existfactrial:
                        failed = True
                        break
                    else:
                        existfactrial = True
            if failed:
                break
        ans = "pairwise coprime"

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

if np.lcm.reduce(a)==np.prod(a):
    print("pairwise coprime")
elif np.gcd.reduce(a)==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math

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

def func():
    D = [x if x % 2 != 0 else 2 for x in range(Amax+1)]
    for i in range(3, Amax+1, 2):
        if i**2 > Amax:
            break
        elif D[i] != i:
            continue
        else:
            j = i
            while j < Amax:
                if D[j] == j:
                    D[j] = i
                j += i
    return D

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

if GCD > 1:
    print('not coprime')
else:
    D = func()
    pri = [0] * (Amax+1)
    for i in range(N):
        x, pri_set = A[i], set()
        while x != 1:
            pri_set.add(D[x])
            x //= D[x]
        for y in pri_set:
            if pri[y] > 0:
                print('setwise coprime')
                exit()
            else:
                pri[y] += 1

    print('pairwise coprime')

Submission status: Wrong Answer

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

pc = "pairwise coprime"
sc = "setwise coprime"
nc = "not coprime"

maxi=10**6
sumi=set()
safe=set()
for i in range(2,maxi+1):
    if i in sumi:
        pass
    else:
        safe.add(i)
        tmp=maxi//i
        for j in range(2,tmp+1):
            sumi.add(j*i)
    #print(i,safe,sumi)

cnt=0
for num in A:
    if num in sumi:
        cnt +=1
if cnt<=1:
    ans=pc
else:
    tmp2=A[0]
    for q in range(1,N):
        tmp2 = gcd(tmp2,A[q])
    if tmp2==1:
        ans=sc
    else:
        ans=nc

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
Alist = list(map(int, input().split()))
import math
import numpy as np
from functools import reduce
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
if not gcd_list(Alist) == 1:
  print("not coprime")
  exit()
else:
  flag = True
  Alist = np.array(Alist)
  for i in range(N):
    if not flag:
      exit()
    Alist2 = Alist
    Alist2[i] = 0
    if 1 in Alist2/Alist[i]:
      flag = False
      print("setwise coprime")

  if flag:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
N = 1000001

spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
t = 'pairwise', 'setwise', None, 'not'
r = 0
input()
u = set()
i = None
for x in map(int, input().split()):
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r |= 1
    s.add(p)
    x //= p
  u |= s
  if i: i &= s
  else: i = s
if i:
  r |= 2
print(t[r], 'coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
arr = np.array(list(map(int, input().split())))


n = 10**3 + 1
primes = set(range(3, n+1, 2))

for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)

used = [False] * 1002
ans1 = True
flg = False
for x in arr:
    for p in primes:
        while x % p == 0:
            if used[p] == True:
                ans1 = False
                flg = True
                break
            x //= p
            used[p] = True
        if flg:
            break
    if flg:
        break


ans2 = np.gcd.reduce(arr) == 1

if ans1 and ans2:
    print("pairwise coprime")
elif ans2:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from collections import deque

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

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    a,b = b,a
while a % b != 0:
    a, b = b, a % b
    if n == 2 and b == 1:
        ans = "pairwise coprime"
        failed = True

for i in range(2, n):
    a = als[i]
    if a < b:
        a,b = b,a 
    while a % b != 0:
        a, b = b, a % b
if b == 1:
    ans = "setwise coprime"
    # break

existeven = False

failed = False

for i in range(n):
    if als[i] >= 2 and als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

maxa = max(als)

checklist = deque([])

for i in range(3, int(math.sqrt(maxa))+1, 2):
    for j in range(n):
        if als[j] >= i and als[j]%i == 0:
            checklist.append(i)
            checklist.append(als[j]/i)

if not failed:
    for i in checklist:
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        ans = "pairwise coprime"

print(ans)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort(reverse=True)
primes = set()
flag = True
for i in range(n):
  if not flag:
    break
  num = lst[i]
  count = 0
  while num % 2 == 0:
    num //= 2
    count += 1
    if pow(2, count) in primes:
      flag = False
      break
    primes.add(pow(2, count))
  f = 3
  while f <= math.sqrt(lst[i]) and flag:
    count = 0
    while num % f == 0:
      num //= f
      count += 1
      if pow(f, count) in primes:
        flag = False
        break
      primes.add(pow(f, count))
    f += 2
  if num in primes:
    flag = False
    break
  primes.add(num)
if not flag:
  a = lst[0]
  for i in range(1, n):
    b = lst[i]
    c = math.gcd(a, b)
    a = c
  if a != 1:
    print('not coprime')
  else:
    print('setwise coprime')
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
r = max(a)+1
s = []
t = [0]*r
for i in range(r):
    s.append([])
for i in range(2,r):
    if(s[i] == []):
        for j in range(1,-(-r//i)):
            s[i*j].append(i)
for i in range(n):
    for j in range(len(s[a[i]])):
        t[s[a[i]][j]] += 1
if(max(t) == n):
    print('not coprime')
elif(max(t) == 1):
    print('pairwise coprime')
else:
    print('setwise coprime')