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 numpy as np


def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2, N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum


def make_divisors(n, pn):
    arr = []
    temp = n
    for i in pn:
        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 set([item[0] for item in arr])


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

pn = seachPrimeNum(1000000)

is_pairwise = True
is_setwise = False

f_set = set()
n_set = set()

for item in a:
    if item in n_set:
        is_pairwise = False
        break
    else:
        n_set.add(item)
    for fc in make_divisors(item, pn):
        if fc in f_set:
            is_pairwise = False
            break
        else:
            f_set.add(fc)
    if not is_pairwise:
        break

s_set = make_divisors(a[0], pn)
for item in a[1:]:
    tmp_set = make_divisors(item, pn)
    s_set = s_set & tmp_set
    if len(s_set) == 0:
        is_setwise = True

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

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
l=list(map(int,input().split()))
e=0
c=l[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(e<=1 and c==1):
    print("pairwise coprime")
elif(e>=2 and c==1):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
from functools import reduce


def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True


def Eratosthenes_sieve(n):
    primes = []
    table = [True] * (n + 1)
    for i in range(n + 1):
        if is_prime(i):
            primes.append(i)
    return primes


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


def decomposition(n):
    if n == 1:
        return True
    is_coprime = True
    if appear[n]:
        is_coprime = False
    else:
        appear[n] = True
    # while i * i <= n:
    for i in primes:
        if i**2 > n:
            break
        if n % i == 0:
            if appear[i]:
                is_coprime = False
            else:
                appear[i] = True
    return is_coprime


n = int(input())
a = list(map(int, input().split()))
ma = max(a)
primes = Eratosthenes_sieve(ma)
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:
import math

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

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

if ans!=1:
    print('not coprime')

else:
    for i in range(min(10000,n-1)):
        for k in range(min(i+1,n-1),min(n,1000)):
            if math.gcd(a[i],a[k])!=1:
                print('setwise coprime')
                exit()
        for j in range(max((n-1000),i+1),n):
            if math.gcd(a[i],a[j])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math

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

# 累積GCD
left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
    left[i + 1] = (math.gcd(left[i], a[i]))
    right[n - i - 1] = (math.gcd(right[n - i], a[n - 1 - i]))

ans = 0
for i in range(n):
    ans = max(ans, math.gcd(left[i], right[i + 1]))

if ans == 1:
    print("pairwise coprime")
elif left[n] == 1 and right[0] == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
N = int(input())

if N<=10**5:
    def eratosthenes(n):
        prime = []
        limit = n**0.5
        numbers = [i for i in range(2,n+1)]
        while True:
            p = numbers[0]
            if limit <= p:
                return prime + numbers
            prime.append(p)
            numbers = [i for i in numbers if i%p != 0]
        return prime

    def prime_decomposition(n):
      i = 2
      d = {}
      while i * i <= n:
        while n % i == 0:
          n //= i
          if i not in d:
              d[i] = 0
          d[i] += 1
        i += 1
      if n > 1:
        if n not in d:
            d[n] = 1
      return d

    pl = eratosthenes(10**6)
    pd = {}
    for p in pl:
        pd[p] = 0

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

    A.sort()



    d = {}
    ans = 0
    for i in range(N):
        if A[i] not in pd:
            primes = prime_decomposition(A[i])
            for p in primes:
                if p not in d:
                    d[p] = 0
                else:
                    ans = 1
                    break
        else:
            if A[i] in d:
                ans = 1
                break
            d[A[i]] = 0

    if ans == 0:
        print('pairwise coprime')
    else:
        def gcd(a, b):
        	while b:
        		a, b = b, a % b
        	return a
        a = A[0]
        for i in range(N):
            a = gcd(a,A[i])
        if a==1:
            print('setwise coprime')
        else:
            print('not coprime')
else:
    def eratosthenes(n):
        prime = []
        limit = n**0.5
        numbers = [i for i in range(2,n+1)]
        while True:
            p = numbers[0]
            if limit <= p:
                return prime + numbers
            prime.append(p)
            numbers = [i for i in numbers if i%p != 0]
        return prime

    def prime_decomposition(n):
      i = 2
      d = {}
      while i * i <= n:
        while n % i == 0:
          n //= i
          if i not in d:
              d[i] = 0
          d[i] += 1
        i += 1
      if n > 1:
        if n not in d:
            d[n] = 1
      return d

    pl = eratosthenes(10**6)
    pd = {}
    for p in pl:
        pd[p] = 0

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

    A.sort()

    d = {}
    ans = 0
    if len(set(A)) != N:
        ans = 1
    for i in range(N):
        if A[i] in d:
            ans = 1
            break
        if A[i] not in pd:
            primes = prime_decomposition(A[i])
            for p in primes:
                if p not in d:
                    for j in range(1,(10**6)//p+1):
                        d[j*p] = 0
                else:
                    ans = 1
                    break




    if ans == 0:
        print('pairwise coprime')
    else:
        def gcd(a, b):
        	while b:
        		a, b = b, a % b
        	return a
        a = A[0]
        for i in range(N):
            a = gcd(a,A[i])
        if a==1:
            print('setwise coprime')
        else:
            print('not coprime')

Submission status: Wrong Answer

Solution code:
gcd=lambda x,y:gcd(y,x%y) if y!=0 else x
def f(a):
    p=a[0]
    for i in range(1,len(a)):
        p=gcd(p,a[i])
    if p==1:
        print("setwise coprime")
    else:
        print("not coprime")

n=int(input())
a=list(map(int,input().split()))
if 1 in a:
    print("not coprime")
    exit()
l=[0 for i in range(2*10**6)]
for i in a:
    l[i]+=1
h=[0 for i in range(2*10**6)]
for i in range(2,2*10**6):
    if h[i]:
        continue
    p=0
    for j in range(i,2*10**6,i):
        h[j]=1
        p+=l[j]
    if p>1:
        f(a)
        exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
prime_cnt = [0]*(len(small_primes))

Flag1, Flag2 = True, False

for i, p in enumerate(small_primes):
  for a in A:
    if a%p == 0:
      prime_cnt[i] += 1
  if prime_cnt[i] == N:
    print("not coprime")
    Flag1 = False
    break
  elif prime_cnt[i] > 1:
    Flag2 = True

if Flag1:
  if Flag2:
    print("setwise coprime")
  else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
      

N=int(input())
A=list(map(int,input().split()))
left=[0]*N
right=[0]*N
for i in range(1,N):
    left[i]=gcd(left[i-1],A[i-1])
    right[N-1-i]=gcd(right[N-i],A[N-i])
#pairwiseについて
ans=1
for i,j in zip(left,right):
    ans=max(ans,gcd(i,j))
#sewtwiseについて
a=A[0]
for i in range(1,N):
    a=gcd(a,A[i])

if ans==1:
    print('pairwise coprime')
elif a==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
*a,=map(int, input().split())
mapa=[0]*(10**6+1)

from bisect import bisect_left

n0 = 10**6
primes = set(range(2, n0+1))
for i in range(2, int(n0**0.5+1)):
    primes.difference_update(range(i*2, n0+1, i))
primes=list(primes)
maxp=primes[-1]

def isPrime(m):
    b=bisect_left(primes, m)
    return m<=maxp and primes[b]==m

def func(m):
    for i in range(2,int(m**0.5)+2):
        if isPrime(m):
            break
        else:
            if m%i==0:
                mapa[i]+=1
                while m%i==0:
                    m//=i
    if m>1:
        mapa[m]+=1

for ai in a:
    func(ai)

tmp=max(mapa)
#print(mapa[:20])
if tmp==n:
    print('not coprime')
elif tmp==1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import math

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

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

if ans!=1:
    print('not coprime')

else:
    for i in range(min(1000,n-1)):
        for k in range(min(i+1,n-1),min(n,1000)):
            if math.gcd(a[i],a[k])!=1:
                print('setwise coprime')
                exit()
        for j in range(max((n-1000),i+1),n):
            if math.gcd(a[i],a[j])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
import sys
import math
N=int(input())
alist=list(map(int,input().split()))
alist.sort()

all_GCD=alist[0]
for i in range(1,N):
  all_GCD=math.gcd(all_GCD,alist[i])
  if all_GCD==1:
    break
else:
  print("not coprime")
  sys.exit(0)
  
max_a=alist[-1]  
inv_table = [0]+[1]
for i in range(2,max_a+1):
  inv_table.append(-(MOD//i)*inv_table[MOD%i]%MOD)
  
lcm_MOD=1
prod_MOD=1
for i in range(N):
  gcd_term=math.gcd(lcm_MOD,alist[i])
  lcm_MOD=lcm_MOD*alist[i]*inv_table[gcd_term]
  prod_MOD*=alist[i]
  lcm_MOD%=MOD  
  prod_MOD%=MOD
  if lcm_MOD!=prod_MOD:
    print("setwise coprime")
    sys.exit(0)
    
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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

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

ch = gcd_list(a)
if ch != 1:
    print("not coprime")
else:
    check = 0
    s = a[0]
    for i in range(1, n):
        if s % a[i] == 0:
            check += 1
            break
        else:
            s *= a[i]
    if check == 0:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = [int(i) for i in input().split()]

chk = [0]*(10**6+1)

for i in range(n):
    if chk[a[i]] == 1 and a[i] >= 2:
        print("not coprime")
        exit()
    chk[a[i]] += 1

flag = True

for i in range(2,10**6+1):
    #tmp = i
    kake = 1
    num = 0
    #print(i)
    while i * kake <= 10**6:
        #print(i)
        if chk[i*kake] == 1:
            if num == 1:
                flag = False
                break
            num = 1
            #break
        kake += 1
gcd_num = math.gcd(a[0],a[1])
        
for i in range(n-2):
    gcd_num = math.gcd(gcd_num,a[i+2])
    
if flag == True:
    print("pairwise coprime")
elif gcd_num == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
def yakusu(n):
    results = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            results.append(i)
            if i != (n // i):
                results.append(n // i)
    results += [n]
    return results
def eratos(A):
    max_Ai = 10**6
    isprime = [0 for i in range(max_Ai+1)]
    ans = []
    for ai in set(A):
        if ai == 1:
            continue
        elif isprime[ai] == 0:
            y = yakusu(ai)
            ans += [y[0]]
            for i in y:
                if isprime[i]:
                    j = i + i
                    while j <= max_Ai:
                        if isprime[j] == 0:
                            isprime[j] = i
                        j = j + i
        else:
            ans += isprime[ai]

    return isprime, ans
N = int(input())
A = list(map(int, input().split()))
isprime, ans = eratos(A)
set_ans = set(ans)
if len(set_ans) == N:
    print('pairwise coprime')
elif len(set_ans) == 1:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

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

sosu = [1 for _ in range(10**6+1)]
sosu[0] = 0
sosu[1] = 1
i = 2
while i < len(sosu):
    j = i*2
    if sosu[i] == 0:
        i += 1
        continue
    while j < len(sosu):
        sosu[j] = 0
        j += i
    i += 1
sosus = []
for i in range(2, len(sosu)):
    if sosu[i]:
        sosus.append(i)

sosuset = set()
flag = 0
GCD = a[0]
for i in range(n-1, -1, -1):
    J = 0
    j = sosus[J]
    GCD = math.gcd(GCD, a[i])
    while j*j <= a[i]:
        if a[i]%j == 0 and j in sosuset:
            flag = 1
            break
        while a[i]%j == 0:
            a[i]//=j
            sosuset.add(j)
        J += 1
        j = sosus[J]
    if a[i] != 1:
        sosuset.add(a[i])


if GCD == 1 and flag == 0:
    print("pairwise coprime")
elif GCD == 1 and flag == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
import math

if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    check_pairwise()
    check_set()
    return


def check_pairwise():
    active = set()
    for i in range(0, n):
        #print(active)
        pp = getprimes(a[i])
        #print("pp", pp)
        for p in pp:
            if p in active:
                return
            else:
                active.add(p)
    print("pairwise coprime")
    exit()



def check_set():
    active = getprimes(a[0])
    for i in range(1, n):
        if not a[i] % a[i-1] == 0:
            rm = []
            for act in active:
                if not a[i] % act == 0:
                    rm.append(act)
            for r in rm:
                active.remove(r)
                if not active:
                    print("setwise coprime")
                    exit()
    print("not coprime")
    exit()




def getprimes(num):
    if num in primes:
        return set([num])
    pp = set()
    for p in iterprimes:
        if p > int(math.sqrt(num)+2):
            break
        if num % p == 0:
            pp.add(p)

    return pp




def n_primes(n):
    nums = list(range(0, n + 1))
    primes = []
    for i in range(2, n + 1):
        num = nums[i]
        if num != 0:
            primes.append(num)
            for i in range(0, n // num + 1):
                nums[i * num] = 0
    return primes


n = RN()
a = sorted(RA())
iterprimes = n_primes(10 ** 6)
primes = set(iterprimes)
solve()

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

x = A[0]

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

A = list(set(A))
A.sort()

if pc_flg:
    for i in range(len(A)):
        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
            if not(pc_flg):
                break
        if not(pc_flg):
            break


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

Submission status: Wrong Answer

Solution code:
from math import gcd
import sys
sys.setrecursionlimit(1000000)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    tmp = gcd(A[0],A[1])
    set_A = set(A)
    for i in range(2,N):
        tmp = gcd(tmp, A[i])

    if tmp != 1:
        print('not coprime')
        exit()
    max_A = max(A)
    ans = [False] * (max_A + 1)
    flag = True
    def divisor(n):
        ass = []
        for i in range(1,int(n**0.5)+1):
            if n%i == 0:
                ass.append(i)
                if ans[i]:
                    return False
                if i != 1:
                    ans[i] = True
                if i**2 == n:
                    continue
                if ans[n//i]:
                    return False
                ans[n//i] = True
                ass.append(n//i)
        ans[n] = True
        return True #sortされていない
    for a in A:
        if not divisor(a):
            flag = False
            break

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






if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
check_list = [0]*1000010
conf = False

def make_divisors(n):
    divisors = []
    global conf
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if check_list[i] >= 1:
                conf = True
                check_list[i] += 1
            elif check_list[i] == 0 and i != 1:
                check_list[i] = 1
            if i != n // i:
                divisors.append(n//i)
                if check_list[n//i] >= 1:
                    conf = True
                    check_list[i] += 1
                elif check_list[n//i] == 0 and n//i != 1:
                    check_list[n//i] = 1
    # divisors.sort()
    return divisors[1:]

def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(len(A)):
        make_divisors(A[i])
    if max(check_list) == len(A):
        return "not coprime"
    else:
        if conf:
            return "setwise coprime"
        else:
            return "pairwise coprime"

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

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N = int(input())
A = list(map(int,input().split()))
def prime_factorize(n):
    a = deque()
    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 N >= 78500:
  a = prime_factorize(A[0])
  for i in a:
    k = 0
    for j in range(N):
      if A[j] % i == 0:
        k += 1
    if k == N :
      print('not coprime')
      sys.exit()
  print('setwise coprime')
  sys.exit()
PA = deque()
c = 0
k = 0
mflag = 12
mnum = 0
for i in range(N):
  tA = A[i]
  a = prime_factorize(tA)
  a = set(a)
  PA.extend(a)
  la = len(a)
  c += la
  if la < mflag:
    mflag = la
    mnum = A[i]
am = set(PA)
cm = len(am)
if cm == c:
  print('pairwise coprime')
  sys.exit()
A.remove(mnum)  
am = prime_factorize(mnum)
am = set(am)
lA = len(A)
for i in am:
  k = 0
  for j in range(lA):
    if A[j] % i == 0:
      k += 1
  if k == lA:
    print('not coprime')
    sys.exit()
print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np
 
def prime(n):
    primes = np.zeros(n + 1, dtype=np.bool)
    primes[2] = 1
    primes[3::2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            primes[p * p::2 * p] = 0
    return primes
pp=prime(10**3)
p=[]
for i in range(2,1001):
  if pp[i]:
    p.append(i)
n=int(input())
a=list(map(int,input().split()))
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

g=a[0]
for i in a[1:]:
  g=gcd(g,i)
if g==1:
  m=[0 for i in range(1001)]
  mm=[0 for i in range(10**6+1)]
  f=True
  for i in a:
    if mm[i]:
      f=False
      break
    mm[i]=1
    for j in range(168):
      if i%p[j]==0:
        if m[j]:
          f=False
          break
        m[j]=1
    if not f:
      break
  if f:
    print("pairwise coprime")
  else:
    print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
A=list(range(2,10**3+1))
p=list()
while A[0]**2<=10**3+1:
	tmp=A[0]
	p.append(tmp)
	A=[e for e in A if e%tmp!=0]
primes = p+A
N = int(input())
L = list(map(int, input().split()))
R = True
for p in primes:
  c = 0
  for l in L:
    if l%p==0:
      c += 1
      while l%p==0:
        l //= p
  if c==N:
    print("not coprime")
    exit()
  if c>1:
    R = False
L.sort()
if L[0]==L[N-1]:
  print("not coprime")
  exit()
for i in range(N-1):
  if L[i]==L[i+1]:
    R = False
    break
print("pairwise coprime" if R else "setwise coprime")

Submission status: Wrong Answer

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

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


primes=[];
isprime=[1 for i in range(0,1001)];
isprime[1]=0;isprime[0]=0
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
#s=[0 for i in range(0,1001)];
s=[0 for i in range(0,1000001)]
#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 s[p]:
        pc=0
      s[p]=1
    if a>=1000:
    #if a!=1:
      #if a in s2:
      if s[a]:
        pc=0
      #s2.add(a)
      s[a]=1

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

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]

primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    while k**2 <= mA:
      sgn[k] = 1
      k += add
  k += 2
#prime_num が用意されているとき
def factorization(n):
  M = n
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if counter[p] == 0:
          counter[p] = 1
        else:
          return False
        while M%p == 0:
          M //= p
  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  if flag:
    flag = factorization(a)
    g = gcd(g, A[k])
    continue
  else:
    g = gcd(g, A[k])
if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    targets = LI()
    MAX_INT = max(targets) + 1
    targets = set(targets)
    is_pw = True
    if 1 in targets:
        print("setwise coprime")
        return

    for i in range(2, MAX_INT):
        origin = i
        kosuu = 0
        while origin <= MAX_INT:
            if origin in targets:
                kosuu += 1
            origin += i

        if kosuu <= 1:
            continue
        elif kosuu < N:
            is_pw = False
        else:
            print("not coprime")
            return

    if is_pw:
        print("pairwise coprime")
        return
    print("setwise coprime")


main()

Submission status: Wrong Answer

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

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

from math import ceil,floor
sumi=set()
ans=pc
maxi=10**6
flag=True

for num in A:
    if num not in sumi:
        p = floor(maxi/num)+1
        for i in range(1,p):
            tmp=i*num
            if tmp in sumi:
                flag=False
                break
            else:
                sumi.add(tmp)
            #print(num,i*num)
    else:
        flag=False
    #print(num,sumi)

if flag:
    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:
from math import gcd

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

f = 0

for i in range(N):
    for j in range(i+1,N):
        if gcd(A[i],A[j]) != 1:
            f = 1
            break
    else:
        continue
    break

if f == 0:
    print("pairwise coprime")
    exit()

Submission status: Wrong Answer

Solution code:
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

N=int(input())
A=[int(x) for x in input().split()]
    
result="pairwise coprime"

for i in callIsPrime(min(1000,max(A))):
  on=0
  off=0
  for a in set(A):
    if a%i==0:
      on+=1
    elif a%i!=0:
      off+=1
    if on>=2 and off>=1:
      break
  if on>=2 and off==0:
    result="not coprime"
    break
  elif on>=2:
    result="setwise coprime"
    
if len(set(A))==1:
  result="not coprime"
elif result!="not coprime" and len(set(A))!=len(A):
  result="setwise coprime"

print(result)

Submission status: Wrong Answer

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

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


primes=[];
isprime=[1 for i in range(0,1001)];
isprime[1]=0;isprime[0]=0
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
#s=[0 for i in range(0,1001)];
s=[0 for i in range(0,1000001)]
#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 s[p]:
        pc=0
      s[p]=1
    #if a>=1000:
    if a!=1:
      #if a in s2:
      if s[a]:
        pc=0
      #s2.add(a)
      s[a]=1

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:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


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')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, 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]


n = inp()
a = inpl()

data = get_sieve_of_eratosthenes(10**6)
print(len(data))
ans = "pairwise coprime"
for i in data:
    coprime = 0
    for j in range(n):
        if a[j] % i == 0:
            coprime += 1
        elif a[j] % i != 0 and (coprime >= 2 or ans == "setwise coprime"):
            break
    if coprime == n:
        ans = "not coprime"
        break
    elif coprime >= 2:
        ans = "setwise coprime"
print(ans)