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:
n=int(input())

A=list(map(int,input().split()))
from math import sqrt
def eratosu(n):
  if not isinstance(n,int):
    raise TypeError("nがint型になってねえぞ")
  if n<2:
    raise ValueError('nが2よりちっちぇえぞ')
  prime = []
  limit = sqrt(n)
  data = [i+1 for i in range(1, n)]  #2,3,4,...,n
  while True:
    p = data[0]
    if limit <= p:
        return prime + data
    prime.append(p)
    data = [e  for e in data if e % p != 0]
PRIME=eratosu(10**6)
def bunkai(n):
    ans=[]
    temp=n
    #そんな早くしなくてよかったり、何回もするわけじゃないなら、
    #for i in range(2,int(sqrt(n))+1): とかで
    primelist= PRIME
    for i in primelist:
        if i>sqrt(n):break
        if temp % i ==0:
            ji=0
            while temp%i==0:
                ji+=1
                temp//=i
            ans.append([i,ji])
    if ans==[]:return([[n,1]])  #素数のとき
    if temp!=1:
        ans.append([temp,1])  #4*5882353とか
    return ans

flag=1
seen=[0]*(10**6+1)
#print(bunkai(3))
for i in A:
    for l in bunkai(i):
        now=l[0] 
        if seen[now]!=0:
            flag=0
        seen[now]+=1
if flag:
    print("pairwise coprime")
elif max(seen)!=n:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
from math import gcd
M = 10**6
def main(N, A):
    g = 0
    for a in A:
        g = gcd(g, a)
    if g > 1:
        print('not coprime')
        return

    u = [False] * (M + 1)
    for n in range(2, int(M**0.5) + 1):
        if u[n]: continue
        for nn in range(n, M + 1, n):
            u[nn] = True
        c = 0
        for a in A:
            if a % n == 0:
                c += 1
                if c >= 2:
                    print('setwise coprime')
                    return
    print('pairwise coprime')

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)

Submission status: Wrong Answer

Solution code:
import math
def makePrimes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

primes = makePrimes(10**6)
prime_set = set()
def prime_factorization(n):
    tmp = n
    ret = True
    m = int(-(-n**0.5//1))+1
    for p in primes:
        if m < p:
            break
        if tmp%p==0:
            if p in prime_set:
                ret = False
            while tmp%p==0:
                tmp//=p
            prime_set.add(p)
    if tmp!=1:
        prime_set.add(tmp)
    return ret

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

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

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

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
lis = list(map(int,input().split()))
lis.sort(reverse=True)
for i in range(n-1):
    if lis[i] == lis[i+1] and lis[i] != 1:
        print("not coprime")
        exit()
num = lis[0]
for nu in lis:
    num = math.gcd(num,nu)
exist = [0 for i in range(max(lis)+1)]
if num != 1:
    print("not coprime")
    exit()
for nu in lis:
    if nu != 1:
        for i in range(2,math.ceil(math.sqrt(nu))+1):
            if nu % i == 0:
                if exist[i] == 1:
                    print("setwise coprime")
                    exit()
                else:
                    exist[i] = 1
                    while nu % i == 0:
                        nu //= i
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
prime = []

for i in range(2,1001):
    det = 0
    for j in range(2,int(i**(1/2))+1):
        if i%j==0:
            det = -1
            break
    if det == 0:
        prime.append(i)

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

m = 1

for p in prime:
    count = 0
    for i in range(N):
        if A[i]%p==0:
            count += 1
    m = max(m,count)

if m == 1:
    print('pairwise coprime')
elif m < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import bisect
import sys,io
import math
from collections import deque
from heapq import heappush, heappop
import functools
input = sys.stdin.buffer.readline

def sRaw():
    return input().decode("utf-8").rstrip("\n").rstrip("\r")


def iRaw():
    return int(input())

def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7
#DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost

def gcd_list(As):
    return functools.reduce(math.gcd, As)

def lcm_div(x, y):
    return ((x * y) // math.gcd(x, y))%DIV

def lcm_div_list(numbers):
    return functools.reduce(lcm_div, numbers, 1)


def main():
    N = iRaw()
    As = isRaw()
    gcds = gcd_list(As)
    if gcds!=1:
        print("not coprime")
        return
    lcms = lcm_div_list(As)
    mul_div = 1
    for a in As:
        mul_div = (mul_div*a)%DIV
    if lcms == mul_div:
        print("pairwise coprime")
        return
    else:
        print("setwise coprime")
        return
    
main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

class factorials:
    '''
    args:
      n : max val when exploring factorials
    '''
    def __init__(self, n):
        self.n = 1# factorials to be searched
        self.factorials = set()
        self.update_factorials(n)

    def update_factorials(self, n):
        if self.n >= n:
            return None
        for i in range(self.n+1, n+1):
            done = False
            limit = int(i ** 0.5)
            for j in self.factorials:
                if j > limit: break
                if not i % j:
                    done = True
                    break
            if not done:
                self.factorials.add(i)
        self.n = n
        return None

    def factorials_set(self):
        return self.factorials

    def check_fact(self, x):
        if x > self.n**2:
            self.update_factorials(int(x ** 0.5)+1)
        MAX = int(math.sqrt(x))
        for f in self.factorials:
            if f > MAX:break
            if not x % f:
                return False
        return True

    def prime_factorization(self, val, divisors=None):
        # divisors : default-dict of divisors. Should be specified only if appended vals are required
        max_n = int(math.sqrt(val))
        if self.n < max_n:
            self.update_factorials(max_n)
        if divisors == None:
            divisors = defaultdict(lambda: 0)
        for f in self.factorials:
            if f > val: break
            while True:
                if not val % f:
                    divisors[f] += 1
                    val //= f
                else:
                    break
        if val > 1:
            divisors[val] += 1
        return divisors

def run():
    N, *A = map(int, read().split())
    MAX = max(A)
    nn = int(MAX ** 0.5)
    FACT = factorials(nn)
    FACT_SET = FACT.factorials_set()
    #print(FACT_SET)
    fact_get = set()
    done = False
    for a in A:
        #print(a, fact_get)
        if done: break
        for f in FACT_SET:
            if not a % f:
                if f in fact_get:
                    done = True
                    break
                fact_get.add(f)
                while not a % f:
                    a //= f
        if a > 1:
            fact_get.add(a)
    if not done:
        print('pairwise coprime')
        return

    SETWISE = False
    for f in FACT_SET:
        done = True
        for a in A:
            if a % f:
                done = False
                break
        if done:
            SETWISE = True
            break
    if not SETWISE:
        print('setwise coprime')
        return
    else:
        print('not coprime')


if __name__ == "__main__":
    run()

Submission status: Wrong Answer

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

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

# pool = set()
pairwize = True
wize = None

for i in range(N):
    f = factorize(A[i])
    fs = set(f)
    # print(fs)

    if i == 0:
        wize = fs
    else:
        wize = wize & fs
        if wize:
            # print(wize)
            pairwize = False

if pairwize:
    print("pairwise coprime")
else:
    if wize:
        print("not coprime")
    else:
        print("setwise coprime")

Submission status: Wrong Answer

Solution code:

from math import gcd
from functools import reduce


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

lim = 10 ** 6 + 10
is_prime = [True] * (lim + 1)
is_prime[0] = False
is_prime[1] = False
min_factor = list(range(lim + 1))

for i in range(2, lim + 1):
    if is_prime[i]:
        for j in range(2 * i, lim + 1, i):
            is_prime[j] = False
            min_factor[j] = i

pairwise = True
appeared = set()
for v in X:
    if v == 1:
        pairwise = False
        break

    while v > 1:
        if v in appeared:
            pairwise = False
            break
        appeared.add(v)

        if v % min_factor[v] == 0:
            v //= min_factor[v]
        else:
            break

if pairwise:
    print("pairwise coprime")
elif reduce(gcd, X) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

#約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

#n = ni()
#a = na()
n = 1000000
a = range(1000000)
wa = set()
seki = set()
s = 0

for i in a:
    ii = set(make_divisors(i)[1:])
    s += len(ii)
    wa = wa | ii
    seki = seki & ii
    if len(seki) == 0:
        print('not coprime')
        exit()

if len(wa) == s:
    print('pairwise coprime')
elif len(seki) > 0:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr

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

B = set()
count = 0
sc = 1
flag = 0

for i in range(N):
    f = factorization(A[i])

    if f[0][0] != 1:
        if flag == 0:
            C = set()
            for ff in f:
                C.add(ff[0])
            flag = 1
        for ff in f:
            B.add(ff[0])
            if ff[0] in C:
                sc = 0
            count += 1

if count == len(B):
    print("pairwise coprime")
elif sc == 1 or (1 in A):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
def main():

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


    def isprime(a):
        if a == 1: return False
        for i in range(2, int(math.sqrt(a))+1):
            if a % i == 0: return False
        return True

    primes = []
    for v in range(1, int(math.sqrt(max(A)))+1):
        if isprime(v):  primes.append(v)

    # for v in range(1, pow(10, 6)+1):
    #     if isprime(v):  primes.append(v)

    # print(primes)

    d = dict()
    ispair = True
    isset = True
    for v in A:
        for p in primes:
            if v % p == 0:
                d[p] = d.get(p, 0) + 1
    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"
    return "not coprime"

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

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

next=[]

f=False
MIN_A=INF
for x in A:
    if x==1:
        f=True
    else:
        next.append(x)
        MIN_A=min(MIN_A,x)
A=next
next=[]

while A:
    prime=prime_factorize(MIN_A)
    MIN_A=INF
    for p in prime:
        cnt=0
        for i,x in enumerate(A):
            if x%p==0:
                cnt+=1
                while x%p==0:
                    x//=p
                if x!=1:
                    next.append(x)
                    MIN_A=min(MIN_A,x)
        if cnt>=2:
            ans=False
        if cnt==N and not f:
            print('not coprime')
            exit()
        A=next
        next=[]

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

Submission status: Wrong Answer

Solution code:
def  gcd( a,  b): 
    while a != 0: 
        a, b = b % a, a
    return b
N = int(input())
A = [int(s) for s in input().split()]

def is_pw(N, A):
    prod = 1
    for a in A:
        if gcd(a, prod) == 1:
            prod *= a
        else:
            return False
    return True

def is_sw(N,A):
    n = A[0]
    for a in A:
        n = gcd(a, n) 
        if n == 1:
            return True
    return False

def main(N, A):
    if N < 20000:
        if is_pw(N, A):
            print('pairwise coprime')
            return

    if is_sw(N, A):
        print('setwise coprime')
        return 
    print('not coprime')
main(N, A)

Submission status: Wrong Answer

Solution code:
# Python3 implementation of the approach 
MAXN = 1000001

# Stores smallest prime factor for 
# every number 
spf = [i for i in range(MAXN)] 

# Hash to store prime factors count 
hash1 = [0 for i in range(MAXN)] 

# Function to calculate SPF (Smallest 
# Prime Factor) for every number till MAXN 
def sieve(): 

	# Separately marking spf for 
	# every even number as 2 
	for i in range(4, MAXN, 2): 
		spf[i] = 2

	# Checking if i is prime 
	for i in range(3, MAXN): 

		if i * i < MAXN: 
			break

		# Marking SPF for all numbers 
		# divisible by i 
		if (spf[i] == i): 
			for j in range(i * i, MAXN, i): 

				# Marking spf[j] if it is not 
				# previously marked 
				if (spf[j] == j): 
					spf[j] = i 

# Function to store the prime factors 
# after dividing by the smallest prime 
# factor at every step 
def getFactorization(x): 

	while (x != 1): 
		temp = spf[x] 
		if (x % temp == 0): 

			# Storing the count of 
			# prime factors in hash 
			hash1[spf[x]] += 1
			x = x // spf[x] 

		while (x % temp == 0): 
			x = x // temp 

# Function that returns true if there 
# are no common prime factors between x 
# and other numbers of the array 
def check(x): 

	while (x != 1): 
		temp = spf[x] 

		# Checking whether it common 
		# prime factor with other numbers 
		if (x % temp == 0 and hash1[temp] > 1): 
			return False
		while (x % temp == 0): 
			x = x //temp 
	
	return True

# Function that returns true if there is 
# an element in the array which is coprime 
# with all the other elements of the array 
def hasValidNum(arr, n): 

	# Using sieve for generating 
	# prime factors 
	sieve() 

	for i in range(n): 
		getFactorization(arr[i]) 

	# Checking the common prime factors 
	# with other numbers 
	for i in range(n): 
		if (not check(arr[i])): 
			return False

	return True

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

n=int(input())
arr=list(map(int,input().split()))
if (hasValidNum(arr, n)): 
	print("pairwise coprime") 
else: 
	g=arr[0]
	for i in range(1,n):
		g=gcd(g,arr[i])
	if(g==1):
		print("setwise coprime") 
	else:
		print("not coprime")

Submission status: Wrong Answer

Solution code:
def pair (inp):
    from collections import Counter
    z=max(inp)
    arr=[1]*(z+1)
    c=Counter(inp)
    if max(c.values())>=2:
        return -1
    for i in range(2,int(pow(z,0.5))+1):
        if arr[i]==1:
            k=2
            f=0
            while k*i<len(arr):
                arr[k*i]=0
                if c[k*i]!=0:
                    f+=c[k*i]
                k+=1
            if f>=2:
                return -1
    return 1
def gcd (a,b):
    if a%b==0:
        return b
    if b%a==0:
        return a
    if a>b:
        return gcd(b,a%b)
    if b>a:
        return gcd(a,b%a)
n=int(input())
arr=list(map(int,input().split()))
if pair(arr)==1:
    print ('pairwise coprime')
else:
    k=arr[0]
    for i in range(1,len(arr)):
        k=gcd(k,arr[i])
        if k==1:
            break
    if k==1:
        print ('setwise coprime')
    else:
        print ('not coprime')

Submission status: Wrong Answer

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

N=int(input())

A=list(map(int,input().split()))
primes=[];
isprime=[1 for i in range(0,1001)];
s=[0 for i in range(0,1001)];
for i in range(2,1001):
  if isprime[i]:
    primes.append(i)
    j=2;
    while i*j<=1000:
      isprime[i*j]=0;
      j+=1
#s=set();
pc=1
s2=set();
for i in range(N):
  a=A[i];
  
  for p in primes:
    if a==1:
      break
    if(a%p==0):
      while(a%p==0):
        a//=p;
      #if p in s:
      if s[p]:
        pc=0
      #s.add(p)
      s[p]=1
    if a>1000:
      if a in s2:
        pc=0
      s2.add(a)

g=A[0];
for i in range(1,N):
  g=gcd(g,A[i])
print("pairwise coprime"if pc else("setwise coprime"if g==1 else "not coprime"))

Submission status: Wrong Answer

Solution code:

from math import gcd
from functools import reduce


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

lim = 10 ** 6 + 10
is_prime = [True] * (lim + 1)
is_prime[0] = False
is_prime[1] = False
min_factor = list(range(lim + 1))

for i in range(2, lim + 1):
    if is_prime[i]:
        for j in range(2 * i, lim + 1, i):
            is_prime[j] = False
            min_factor[j] = i

pairwise = True
appeared = set()
for v in X:
    if v == 1:
        pairwise = False
        break

    while v > 1:
        if v in appeared:
            pairwise = False
            break
        appeared.add(v)
        v //= min_factor[v]

if pairwise:
    print("pairwise coprime")
elif reduce(gcd, X) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
p = primes(1000)
c = [0]*1001
# print(len(p))

n = int(input())
a = list(map(int,input().split()))
# a = [10**6]*10**6
g = 0
f = 1
for i in a:
    g = gcd(g,i)
    if f == 1:
        for j in p:
            if i%j == 0:
                c[j] += 1
                if c[j] > 1:
                    f = 0
if len(set(a)) != n:
    f = 0
# print(g,f)
if g == 1:
    if f == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = list(map(int, input().split()))
A_max = max(A)
if A_max == 1:
    print("pairwise coprime")
    sys.exit()
dp = [0]*(A_max+1)
p = 0
s = 0
for i in range(2, A_max+1):
    c = 0
    if dp[i] == 0:
        dp[i] = 1
        for j in range(i, A_max+1, 2):
            dp[j] = 1
        for j in range(N):
            if A[j] % i == 0:
                c += 1
        if c >= 2:
            p = 1
        if c == N:
            s = 1
if p == 0:
    print("pairwise coprime")
elif s == 0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

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

next=[]

f=False
MIN_A=INF
for x in A:
    if x==1:
        f=True
    else:
        next.append(x)
        MIN_A=min(MIN_A,x)
A=next
next=[]

while A:
    prime=prime_factorize(MIN_A)
    MIN_A=INF
    for p in prime:
        cnt=0
        for i,x in enumerate(A):
            MIN_A=min(MIN_A,x)
            if x%p==0:
                cnt+=1
                while x%p==0:
                    x//=p
                if x!=1:
                    next.append(x)
        if cnt>=2:
            ans=False
        if cnt==N and not f:
            print('not coprime')
            exit()
        A=next
        next=[]

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

Submission status: Wrong Answer

Solution code:
import math
import functools

N = int(input())
A = [int(_) for _ in input().split()]

p = set([])

pairwise = True
for a in A:
    # print(a)
    for k in range(2, int(math.sqrt(a) + 1)):
        if a % k == 0:
            if k in p:
                pairwise = False
                break
            p.add(k)
            while a % k == 0:
                a //= k
    if pairwise and a > 1:
        p.add(a)
    # print(p)
    #for j in range(i+1, N):
    #    x = math.gcd(A[i], A[j])
    #    print(i, j, x)
    #    if x != 1:
    #        pairwise = False

y = functools.reduce(math.gcd, A)
# print(y)

if pairwise:
    print("pairwise coprime")
elif y == 1:
    print("setwize coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
def generate_primes(n):
    p = 2
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    return prime

prime = [True for i in range(10**6 + 1)]
generate_primes(10**6)
primenumbers = [ind for ind,val in enumerate(prime[2:],2) if val]
n = int(input())
ls = list(map(int,input().strip().split()))

flag = 0
ans = "pairwise coprime"
for prime_no in primenumbers:
    f = 1
    c = 0
    for val in ls:
        if val%prime_no!=0:
            f = 0
        else:
            c += 1
    if f:
        ans = "not coprime"
        break
    if c>1:
        flag = 1
if flag:
    ans = "setwise coprime"
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from math import gcd

import math

# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
prime_list = callIsPrime(10**3)

N=int(input())
A=list(map(int,input().split()))
prime_flg = [True for i in range(10**3)]
pc_flg=True

if len(A)!=len(set(A)):
    pc_flg=False


for i in range(N):
    for j in range(len(prime_list)):
        p=prime_list[j]
        if A[i]%p == 0:
            if prime_flg[p]:
                prime_flg[p]=False
            else:
                pc_flg=False

x = A[-1]

for i in range(N):
    x=gcd(x,A[i])


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

Submission status: Wrong Answer

Solution code:
import math

def main():
    N = int(input())
    As = list(map(int, input().split()))
    
    L = 1000 + 1
    isPrime = [True] * L
    isPrime[0] = isPrime[1] = False
    primes = []
    for n in range(2, L):
        if isPrime[n]:
            primes.append(n)
            isPrime[2*n::n] = [False] * ((L-n-1) // n)

    common_divs = None
    pairwise_flag = True
    for i, a in enumerate(As):
        divs = set()
        for p in primes:
            while a % p == 0:
                divs.add(p)
                a //= p
        if a > 1:
            divs.add(a)
        if i > 0:
            common_divs &= divs
            if common_divs:
                pairwise_flag = False
        else:
            common_divs = divs
    if pairwise_flag:
        print('pairwise coprime')
    elif common_divs:
        print('not coprime')
    else:
        print('setwise coprime')

main()

Submission status: Wrong Answer

Solution code:
from math import gcd
from functools import reduce


def calc_ggcd(arr):
    return reduce(gcd, arr)


def decomposition(n):
    i = 2
    is_coprime = True
    while i * i <= n:
        if n % i == 0:
            if appear[i]:
                is_coprime = False
            else:
                appear[i] = True
        i += 1
    return is_coprime


n = int(input())
a = list(map(int, input().split()))
appear = [False] * (max(a) + 1)
keep_pair_coprime = True
for aa in a:
    if not decomposition(aa):
        keep_pair_coprime = False

        # 素因数分解 O(√N)
global_gcd = calc_ggcd(a)
if keep_pair_coprime:
    print('pairwise coprime')
elif global_gcd == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr


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

a.sort()

jd=[True]*(a[-1]+10)

pairwise=True

for i in a:
    xxx=factorization(i)
    for j in xxx:
        if jd[j[0]]==True:
          jd[j[0]]=False
        else:
            pairwise=False
            break
    
    if pairwise==False:
        break

if pairwise:
    print('pairwise coprime')
    exit()


zzz=factorization(a[0])

for i in zzz:
    pin=i[0]
    flag=True
    cnt=0
    for j in a:
      if j%pin==0:
          cnt+=1
    
    if cnt==n:
        print('not coprime')
        exit()


print('setwise coprime')

Submission status: Wrong Answer

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

import math 

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

if ans!=1:
    #print(ans)
    print("not coprime")
    exit()
else:
    checked=[0]*(int(max(a)**(0.5))+100)

    for item in a:

        for j in range(2,int(item**0.5)+1):
            if item%j==0 and j*j<=item:
                if checked[j]==0:
                    checked[j]+=1
                else:
                    #print(item,j,checked)
                    print("setwise coprime")
                    exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
m=list(map(int,input().split()))
import math
mod=10**9+7
s=m[n-1]
d=m[n-1]
k=m[n-1]
for i in range(n-2,-1,-1):
    d=math.gcd(m[i],d)
    s*=m[i]
    k=m[i]*k//d
    k%=mod
    s%=mod
if d>1:
    print('not coprime')
elif s!=k:
    print('setwise coprime')
else:
    print('pairwise coprime')