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
import sys
import collections
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

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 
    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]

n=int(input())
alist=list(map(int, input().split()))
amax=max(alist)
if n<=len(primes(amax+1)):
  nums=[]
  for i in alist:
    for j in factorization(i):
      nums.append(j[0])
  if len(nums)<=len(primes(amax+1)):
    c = collections.Counter(nums)
    cnt=max(c.values())
    if cnt==1:
      print('pairwise coprime')
      sys.exit()
num=alist[0]
for i in range(n):
  num=math.gcd(num,alist[i])
if num==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys, math

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, sys.stdin.readline().rsplit()))

ok = True
S = set()
for a in A:
    arr = factorization(a)
    for b, _ in arr:
        if b in S:
            ok = False
            break
        else:
            S.add(b)
    if ok is False:
        break
if ok:
    print("pairwise coprime")
else:
    tmp = A[0]
    for a in A[1:]:
        tmp = math.gcd(a, tmp)
    if tmp != 1:
        print("not coprime")
    else:
        print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math

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)

if not failed:
    for i in range(3, int(math.sqrt(maxa))+2):
        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

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:
        return False
    else:
        y = x // checker[x]
        if checker[y] != checker[x] and y != checker[x]:
            checker[checker[x]] = -1
        if y < checker[x]:
            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
x = 1 if i != 0 else a[0]    
a = a[i:]
n -= i
if n == 1:
    print("pairwise coprime")
    quit()

checker = eratosthenes(a[-1])


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 numpy as np
from numba import njit

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


@njit
def solve(arr):
    for i in range(arr.shape[0] - 1):
        if np.gcd(arr[i], arr[i + 1]) != 1:
            ans = False
            break
    else:
        ans = True
    return ans


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

    return arr

N = int(input())
A = list(map(int,input().split()))
    
check = [0] * 1000000
flag = False

ans = "pairwise coprime"

for i in range(N - 1):
    temp = cal(A[i])
    for j in (temp):
        if check[j - 1] != 0:
            ans = "setwise coprime"
        check[j - 1] += 1
            

temp = cal(A[-1])

for j in (temp):
    if check[j - 1] == 0:
        pass
    elif check[j - 1] == N - 1:
        print("not coprime")
        break
else:
    print(ans)

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 P[A[i]] == True:
        c = False
    P[A[i]] = True
    for j in range(2, math.floor(A[i]**0.5)+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:
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):

    fct = []
    idx=0
    b = prms[idx]
    while b * b <= n :
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        idx+=1

        b = prms[idx]
    if n > 1:
        fct.append((n,1))
    return fct

n =ni()
A = lma()
mx= 2*10**6
prms = is_primes(mx+1)
prms2 = [i for i in range(mx+1) if prms[i]==1]
#print(prms,prms2)
d=collections.Counter()
for a in A:
    fct = factorize(a,prms2)
    #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 numpy as np
from numba import njit

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


@njit
def solve(arr):
    for i in range(arr.shape[0] - 1):
        if np.gcd(arr[i], arr[i + 1]) != 1:
            ans1 = False
            break
    else:
        ans = True
    return ans


ans1 = solve(arr)
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:
N = int(input())
Alist = list(map(int, input().split()))
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

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

if not gcd_list(Alist) == 1:
  print("not coprime")
  exit()
else:
  flag = True
  for i in range(N):
    for j in range(N-1+1):
      if flag and (not gcd(i, j) == 1):
        print("setwise coprime")
        flag = False
  if flag:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce


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


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


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

    primes = set({})
    is_pairwise_coprime = True

    for i in range(N):
        for p, _ in factorization(A[i]):
            if p in primes:
                is_pairwise_coprime = False
                break
            else:
                primes.add(p)

    gcd_ = reduce(math.gcd, A)

    if is_pairwise_coprime:
        print('pairwise coprime')
    elif gcd_ == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
mxa=max(a)

            
def fact(num):
    arr = []
    temp = num
    for i in range(2, int(-(-num**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(num)
    return arr

flg=True
flg2=True
table=[0]*(mxa+1)
for (i,x) in zip(a,range(len(a))):
  fc=fact(i)
  for j in fc:
    table[1]=0
    if table[j]==1:
      flg=False
      break
    table[j]+=1
g=1
for i in a:
  g=math.gcd(i,g)
if flg:
  print("pairwise coprime")
elif g==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
    
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a 
def multiple_gcd(a):
    ans = a[0]
    for i in range(1, len(a)):
        ans = gcd(ans, a[i])
    return ans

def pairwise_coprime_gcd():
    for i in range(N-1):
        for j in range(i+1, N):
            if gcd(A[i], A[j]) != 1:
                return 0
    return 1
def pairwise_coprime(A):
    prime = set()
    for i in range(N):
        fact = factorization(A[i])
        for x in fact:
            if x[0] in prime:
                return 0
            prime.add(x[0])
    return 1

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

if pairwise_coprime(A) == 1:
    print('pairwise coprime')
elif multiple_gcd(A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
n=int(input())
A=set(map(int,input().split()))
ma=max(A)
data=[i for i in range(2,ma+1)]
pco=True
sco=True
while len(data)>1:
  d=data[0]
  if d>ma**0.5:break
  one=d in A
  new=[]
  if one:k=1
  else:k=0
  for e in data[1:]:
    if e%d==0:
      k+=1
      if e in A:
        if one:pco=False
        else:one=True
    else:
      new.append(e)
  if k==n:
    sco=False
    break
  data=new
if pco:
  print('pairwise coprime')
elif sco:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data
n = int(input())
a = list(map(int, input().split()))
b = a[0]
c = 0
d = [0]*(10**6+1)
for i in range(1, n):
    b = gcd(b, a[i])
for i in range(n):
    if a[i] != 1: d[a[i]] += 1
    if d[a[i]] == 2:
        c = 1
        break
if b != 1: print("not coprime")
elif c == 1: print("setwise coprime")
else:
    data = get_sieve_of_eratosthenes(1000)
    count = [0]*(len(data))
    d = 0
    for j in range(len(data)):
        for i in range(n):
            if a[i]%data[j] == 0:
                if count[j] == 1:
                    print("setwise coprime")
                    d = 1
                    break
                else:
                    count[j] = 1
        if d == 1:
            break
    else: print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys, math

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, sys.stdin.readline().rsplit()))

tmp = A[0]

for a in A[1:]:
    tmp = math.gcd(a, tmp)

if tmp != 1:
    print("not coprime")
else:
    ok = True
    S = set()
    for a in A:
        arr = factorization(a)
        for b, _ in arr:
            if b in S:
                ok = False
                break
            else:
                S.add(b)
        if ok is False:
            break
    if ok:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Wrong Answer

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

def prime(x):
    rtn = set()
    i = 2
    while i <= x:
        if (x % i == 0):
            rtn.add(i)
            while (x % i == 0):
                x /= i
        i += 1
    return rtn

is_pairwise = True
is_setwise = True

t = set()
s0 = set()
for s in (prime(i) for i in a):
    #print(s)
    if len(t & s) > 0:
        is_setwise = False
    if len(s0 & s) > 0:
        is_pairwise = False
    t |= s
    s0 = s

if is_pairwise:
    print("pairwise coprime")
elif is_setwise:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
temp=[0]*(10**3+2)
b=0
for i in range(2,10**3+2):
    if temp[i]==0:
        for j in range(n):
            if a[j]%i==0:
                k=2
                l=i
                while True:
                    temp[l]+=1
                    l*=k 
                    k+=1
                    if l>=10**3+2:
                        break
if max(temp)==1:
    print("pairwise coprime")
elif min(temp)>=2:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

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


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

setC = dict()

not_pairwise = False
fs = []
for a in A:
    f = factorization(a)

    vs = set()
    for v, n in f:
        if v in setC:
            not_pairwise = True
        setC.update({v:n})
        vs.add(v)


import math
from functools import reduce
def gcd_multi(numbers):
    return reduce(math.gcd, numbers)

g = gcd_multi(A)

if not not_pairwise:
    print('pairwise coprime')
elif g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

def erat():
    tmp = [False if i == 0 or i == 1 else True for i in range(10 ** 6)]
    t = []
    for i in range(2, 10 ** 6):
        if tmp[i]:
            for j in range(2 * i, 10 ** 6, i):
                tmp[j] = False
            t.append(i)
    return t

t = erat()
a = dict(iter([(i, 0) for i in t]))

for j in range(N):
    for i in t:
        if not A[j] % i:
            a[i] += 1
            while not A[j] % i:
                A[j] //= i

        if A[j] == 1:
            break

if max(a.values()) == 1:
    print('pairwise coprime')
elif max(a.values()) != N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import os
import heapq
import sys,threading
import math
import operator
from collections import defaultdict,deque
from io import BytesIO, IOBase
import math as mt
sys.setrecursionlimit(10 ** 5)
threading.stack_size(2**27)


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


"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""


def inpt():
    return [int(k) for k in input().split()]

def main():
    MAXN=1000001
    prime=[0]*MAXN
    prime[1] = 1
    for i in range(2, MAXN):
        prime[i] = i

    for i in range(4, MAXN, 2):
        prime[i] = 2

    for i in range(3, mt.ceil(mt.sqrt(MAXN))):
        if (prime[i] == i):
            for j in range(i * i, MAXN, i):
                if (prime[j] == j):
                    prime[j] = i
    n=int(input())
    ar=inpt()
    d=defaultdict(int)
    ok=True
    for i in ar:
        x=i
        while(x!=1):
            tp=prime[x]
            x=x//prime[x]
            if(tp in d and d[tp]!=i):
                ok=False
                break
            d[tp]=i

    if(ok):
        print('pairwise coprime')
    else:
        gcd=ar[0]
        for i in range(1,n):
            gcd=mt.gcd(gcd,ar[i])

        if(gcd==1):
            print('setwise coprime')
        else:
            print('not coprime')




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    #main()
    threading.Thread(target=main).start()

Submission status: Wrong Answer

Solution code:
import math
import collections
def main():

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


    def prime_factor(n):
        ans = []
        if n % 2 == 0: ans.append(2)
        while n % 2 == 0:
            n //= 2

        for i in range(3, int(math.sqrt(n))+1, 2):
            if n % i == 0:
                ans.append(i)
            while n % i == 0:
                n //= i
        if n > 0:
            ans.append(n)
        return ans

    ispair = True
    isset = True

    d = dict()
    for v in A:
        for u in prime_factor(v):
            d[u] = d.get(u, 0) + 1
    # print(d)

    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:
import math
n=int(input())
l=list(map(int,input().split()))
e=0
e1=0
e2=0
e3=0
e4=0
e5=0
e6=0
e7=0
e8=0
c=l[0]
aa=0
for i in range(1,n):
    c=math.gcd(l[i],c)
for i in range(n):
    if(l[i]%2==0):
        e+=1
    if(l[i]%3==0):
        e1+=1
    if(l[i]%5==0):
        e2+=1
    if(l[i]%7==0):
        e3+=1
    if(l[i]%11==0):
        e4+=1
    if(l[i]%13==0):
        e5+=1
    if(l[i]%17==0):
        e6+=1
    if(l[i]%19==0):
        e7+=1
    if(l[i]%23==0):
        e8+=1
    if(e1>=2 or e2>=2 or e3>=2 or e4>=2 or e5>=2 or e6>=2 or e7>=2 or e8>=2 or e>=2):
        aa=1
        break

    
if(aa==0 and c==1):
    print("pairwise coprime")
elif(c==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()))

def get_prime(n):
  res = [1]*(n+1)
  x = 2
  for i in range(2,x):
    if res[i]:
      for j in range(i*2,n+1,i):
        res[j] = 0
  return [i for i in range(2,n+1) if res[i]]

prime_list = {x:0 for x in get_prime(10**6+1)}
def check(i):
  x = 2
  m = i
  while x < math.sqrt(i):
    if m%x == 0:
      if prime_list[x]:
        return 0
      m //= x
      prime_list[x] = 1
      continue
    else:
      x += 1
  return 1

allwise = 1
if len([x for x in a if x > 1]) > len(prime_list.keys()):
  allwise = 0
else:
  allwise = check(a[0])
setwise = a[0]

for ai in a[1:]:
  if allwise:
    allwise = check(ai)
  setwise = math.gcd(setwise,ai)
  #print(ai,allwise,setwise)
if allwise:
  print('pairwise coprime')
elif setwise == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
#ここまでテンプレ
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))

import math

ans = a[0]
sosu = a[0]

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

an = make_divisors(a[0])
flag = True

for i in range(1, n):
    ans = math.gcd(ans, a[i])
    pri = make_divisors(a[i])
    for j in pri:
        if j in an:
            flag = False    
        else:
            an.add(j)
    
if ans == 1 and flag == True:
    print("pairwise coprime")
elif ans == 1:
    print("setwise coprime")
else:
    print("not 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=max(A)
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,sumi)

cnt=0
for num in A:
    if num in safe or num==1:
        cnt +=1
#print(safe,cnt)
if cnt>=N-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:
import math
n=int(input())
a=list(map(int,input().split()))
pflag=True
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

if len(set(a))!=n:
  pflag=False
sosu=[1]*(10**6+1)
sosu[0]=0

k=2
while k<(10**6+1)**0.5+1:
  for i in range(2*k,10**6+1,k):
    sosu[i]=0
  if k==2:
    k+=1
  else:
    k+=2
gu=0
import copy
ans=copy.deepcopy(sosu)

for i in range(n):
  if gu>1:
    pflag=False
  if ans[a[i]]==0:
    ai = set(prime_factorize(a[i]))
    for j in ai:
      if ans[j]==0:
        pflag=False
        break
      else:
        ans[j]=0
  else:
    ans[a[i]]=0
  if a[i]%2==0:
    gu+=1
  ans[a[i]]=0
    
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math

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

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    tmp = b
    b = a
    a = tmp 
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:
        tmp = b
        b = a
        a = tmp 
    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)

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:
                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:
N = int(input())
A = list(map(int, input().split()))

def erat():
    tmp = [False if i == 0 or i == 1 else True for i in range(10 ** 3)]
    t = []
    for i in range(2, 10 ** 3):
        if tmp[i]:
            for j in range(2 * i, 10 ** 3, i):
                tmp[j] = False
            t.append(i)
    return t

t = erat()
a = dict(iter([(i, 0) for i in t]))

for j in range(N):
    for i in t:
        if not A[j] % i:
            a[i] += 1
            while not A[j] % i:
                A[j] //= i

        if A[j] == 1:
            break

if max(a.values()) == 1:
    print('pairwise coprime')
elif max(a.values()) != N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd,sqrt
from sys import exit
N = int(input())
A = list(map(int,input().split()))
cnt = A[0]
for i in A:
    cnt = gcd(cnt,i)
if cnt == 1:
    if N > 78498: print("setwise coprime")
    else:
        fipn = []
        for i in range(N):
            for j in range(2,int(sqrt(A[i])) + 1):
                if A[i] % j == 0:
                    if j in fipn:
                        print("setwise coprime")
                        exit()
                    fipn.append(j)
                    while A[i] % j == 0:
                        A[i] //= j
            if A[i] > 1:
                if A[i] in fipn:
                    print("setwise coprime")
                    exit()
                fipn.append(A[i])
        print("pairwise coprime")
else: print("not coprime")

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = [0, 0]
gcd = [1]
gcda = []
ansp = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i] > A[j]:
            a = A[i]
            b = A[j]
        else:
            a = A[j]
            b = A[i]
        c = a % b
        if c == 0:
            gcd.append(b)
            break
        elif c == 1:
            ansp += 1
            break
        for k in range(c):
            a = b
            b = c
            c = a % b
            if c == 0:
                gcd.append(b)
                break
            if c == 1:
                ansp += 1
                break
# print(gcd)            
if ansp == N * (N-1) // 2:
    ans[0] = 1
else:
    gcd.sort()
    if len(gcd) > 1:
        for i in range(1,len(gcd)-1):
            a = gcd[i]
            b = gcd[i+1]
            c = b % a
        if c == 0:
            gcda.append(a)
        elif c == 1:
            pass
        else:   
            for k in range(c):
                b = a
                a = c
                c = b % a
            if c == 1:
                pass
            if c == 0:
                gcda.append(a)
    d = len(gcda)
    if d == 0:
        ans[1] = 1
    else:
        D = gcda[0]
        r = gcda.count(D)
        if r == d:
            pass
        else:
            ans[1] = 1              



if ans[0] == 1:
    print("pairwise comprime")
elif ans[1] == 1:
    print("setwise comprime")
else:
    print("not comprime")