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

is_pairwise = True

def calc_primes(n):
    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

primes = calc_primes(int(math.sqrt(10**6)))
used = set()

def factorize(n):
    for prime in primes:
        if n == 1:
            break
        is_used = False
        while n % prime == 0:
            if prime in used:
                return False
            n //= prime
            is_used = True
        if is_used:
            used.add(prime)
    return True

all_gcd = A[0]
for a in A:
    all_gcd = math.gcd(all_gcd, a)
    if is_pairwise:
        if not factorize(a):
            is_pairwise = False

if is_pairwise:
    print('pairwise coprime')
elif all_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()))
pflag=True
sflag=False

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
for i in range(n):
  if sosu[a[i]]!=1 and gu>1:
    pflag=False
  if a[i]%2==0:
    gu+=1
    
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

def main():
    N = int(input())
    As = list(map(int, input().split()))
    pairwise_flag = True
    setwise_flag = True
    if N > 78498:
        pairwise_flag = False
    
    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)

    or_factor = 0
    or_factor_over1000 = set()
    all_gcd = None
    for i, a in enumerate(As):
        digit = 1
        factor = 0
        x = a
        if pairwise_flag:
            for p in primes:
                if x % p == 0:
                    factor += digit
                    x //= p

                while x % p == 0:
                    x //= p
                digit <<= 1

        if i > 0:
            all_gcd = math.gcd(all_gcd, a)
            if pairwise_flag:
                if or_factor & factor:
                    pairwise_flag = False
                or_factor |= factor
                if x > 1:
                    if x in or_factor_over1000:
                        pairwise_flag = False
                    or_factor_over1000.add(x)
        else:
            all_gcd = a
            if x > 1:
                or_factor_over1000.add(x)
    if pairwise_flag:
        print('pairwise coprime')
    elif all_gcd > 1:
        print('not coprime')
    else:
        print('setwise coprime')

main()

Submission status: Wrong Answer

Solution code:
from collections import Counter


def eratosthenes(mx, arr):
    sss = set(arr)
    array = [1 for _ in range(mx + 1)]
    array[0] = array[1] = 0
    pair_wise = True
    set_wise = True

    if len(arr) > len(sss):
        pair_wise = False


    cnt = 0
    for i in range(2, mx+1, 2):
        array[i] = 0
        if i in sss:
            cnt += 1
    if cnt > 1:
        pair_wise = False
    if cnt == len(sss):
        set_wise = False

    for i in range(3, mx + 1, 2):
        if not array[i]:
            continue
        cnt = 0
        for j in range(i, mx + 1, i):
            array[j] = 0
            if i in sss:
                cnt += 1
        if cnt > 1:
            pair_wise = False
        if cnt == len(sss):
            set_wise = False
            break

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

def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    eratosthenes(max(a), a)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import numpy
n = int(input())
arr = list(map(int,input().split()))
x = 1
for i in range(n-1):
  if numpy.gcd(arr[i],arr[i+1]) != 1 :
    x = 0
    break
    
if x == 0:
  if numpy.gcd.reduce(arr) == 1: print('setwise coprime')
  else: print('not coprime')
else : print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
import unittest
import collections


def f(n):
    e = set()
    if n < 2:
        return e
    if n % 2 == 0:
        e.add(2)
        n //= 2
        while n % 2 == 0:
            n //= 2
    i = 3
    while i <= n:
        if n % i == 0:
            e.add(i)
            n //= i
            while n % i == 0:
                n //= i
        i += 2
    return e


def is_pairwise_coprime(n, a):
    e = set()
    for i in range(n):
        e2 = f(a[i])
        if e & e2:
            return False
        e |= e2
    return True


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


# number of prime
UPPER = 78498
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
]


def solve(n, a):
    if not is_setwise_coprime(n, a):
        return 'not coprime'

    a = [e for e in a if e > 1]
    n = len(a)
    if n > 78498:
        return 'setwise coprime'
    elif n < 10**3:
        if is_pairwise_coprime(n, a):
            return 'pairwise coprime'
    else:
        used_factor = set()
        for p in PRIMES:
            for i in range(n):
                if a[i] % p == 0:
                    if p in used_factor:
                        return 'setwise coprime'
                    else:
                        a[i] //= p
                        used_factor.add(p)
        return 'setwise coprime'
    if is_pairwise_coprime(n, a):
        return 'pairwise coprime'
    return 'setwise coprime'


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(n, a))


if __name__ == "__main__":
    main()


class Test(unittest.TestCase):
    def test_1(self):
        n = 3
        a = [3, 4, 5]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_2(self):
        n = 3
        a = [6, 10, 15]
        self.assertEqual(is_pairwise_coprime(n, a), False)
        self.assertEqual(is_setwise_coprime(n, a), True)
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_3(self):
        n = 3
        a = [6, 10, 16]
        self.assertEqual(solve(n, a), 'not coprime')

    def test_4(self):
        n = 3
        a = [1, 1, 1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_5(self):
        n = 3
        a = [1, 2, 2]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_6(self):
        n = 10
        a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_7(self):
        n = 11
        a = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_8(self):
        n = 2
        a = [1, 1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_9(self):
        n = 2
        a = [1, 2]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_10(self):
        n = 2
        a = [10**6, 10**6-1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_11(self):
        n = 3
        a = [10**6, 10**6-1, 10**6, ]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_12(self):
        n = len(PRIMES) * 2
        a = PRIMES + PRIMES
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_13(self):
        a = [1009, 1013, 1019, 1021, 1031, 1033, 1039,
             1049, 1051, 1061, 1063, 1069, 1087, ]
        n = len(a)
        self.assertEqual(solve(n, a), 'pairwise coprime')

Submission status: Wrong Answer

Solution code:
N = int(input())

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

max_a = max(A)

set_a = set(A)

setFlag = False

if len(set_a) != len(A):
    setFlag = True

for i in range(2,int(max_a**0.5)+2):
    tmp_count = 0
    pairFlag = True
    for key,a in enumerate(set_a):
        if a%i == 0:
            tmp_count += 1
            if 1 == tmp_count or tmp_count == key+1:
                continue
            else:
                setFlag = True
                break
        else:
            pairFlag = False
    if pairFlag:
        print('not coprime')
        exit()

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

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
lim = 200000
inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def COMinit(max=lim, mod=MOD):
    factrial[0] = factrial_inv[0] = 1
    factrial[1] = factrial_inv[1] = 1
    inv_t[0] = inv_t[1] = 1
    for i in range(2, max):
        factrial[i] = factrial[i-1]*i % mod
        inv_t[i] = -inv_t[mod % i]*(mod//i) % mod
        factrial_inv[i] = factrial_inv[i-1]*inv_t[i] % mod


def comb(a, b, mod=MOD):
    if a < b:
        return 0
    if factrial[0] == -1:
        COMinit()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % mod


def prime_factor(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 = [int(_) for _ in input().split()]
p = [2]

for i in range(3, 10**3+100):
    for P in p:
        if i % P == 0:
            break
    else:
        p.append(i)

dic = {}
for P in p:
    dic[P] = 0

for i in range(n):
    if a[i] == 1:
        print("pairwise coprime")
        exit(0)
    temp = a[i]
    for P in p:
        if temp % P == 0:
            dic[P] += 1
            while temp % P == 0:
                temp //= P
        if temp == 1:
            break
    if temp != 1:
        if temp in dic.values():
            dic[temp] += 1
        else:
            dic[temp] = 1
# print(ans[0:10])

ans = dic.values()
# print(ans)
# print(p, len(p))
# print(dic)
if max(ans) == n:
    print("not coprime")
elif max(ans) == 1:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
lis = [True for i in range(10**6+1)]
flag = False
for i in range(2, 10**3 + 10):
    if lis[i] == True:
        j = i
        while j <= 10**3+10:
            lis[j] = False
            j += i
        now = 0
        for a in A:
            if a % i == 0:
                now += 1
        if now == n:
            print("not coprime")
            exit()
        if now > 1:
            flag = True
if flag:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import copy

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    #arr=list(map(int, readline().rstrip().split()))
    n=int(readline())
    arr=list(set(list(map(int, readline().rstrip().split()))))
    n=len(arr)
    be=[0]*(10**6+1)
    for i in range(n):
        be[arr[i]]+=1
    is1=True
    is2=True
    for i in range(2,10**6+1):
        x = i
        found=0
        while x <= 10**6:
            found+=be[x]
            x += i
        if found >= 2:
            is1=False
        if found == n:
            is2=False
    if is1==True:
        print("pairwise coprime")
    elif is2==True:
        print("setwise coprime")
    else:
        print("not coprime")

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Wrong Answer

Solution code:
from math import gcd
def g(a):
    al=len(a)
    if al==2:
        return gcd(a[0],a[1])
    elif al==1:
        return a[0]
    return gcd(g(a[al//2:]),g(a[:al//2+1]))
n=int(input())
a=list(map(int,input().split()))
if g(a)!=1:
    print("not coprime")
    exit()
one=a.count(1)
if len(a)-one>168:
    print("setwise coprime")
    exit()
for i in range(len(a)-1):
    for j in range(i+1,len(a)):
        if gcd(a[i],a[j])!=1:
            print("setwise coprime")
            exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
Np = int(input())
A = list(map(int,input().split()))
A = [i for i in A if i != 1]
N = len(A)
flag = 0
if Np != N:
  flag =1
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 len(A) != len(set(A)):
  print('not coprime')
  sys.exit()
if N >= 78500 and flag == 0:
  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:
from math import gcd
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 [a[0] for a in arr]

N = int(input())
A = list(set(sorted([int(i) for i in input().split()])))
if len(A) == N:  
  all_flag = True
  devisors = set()
  for n in range(N-1):
      if n == 0:
          g = gcd(A[n],A[n+1])
      else:
          g = gcd(A[n+1],g)
      temp = factorization(A[n])
      for t in temp:
          if t in devisors:
              all_flag=False
          else:
              devisors.add(t)
  if all_flag and g == 1:
      print('pairwise coprime')
  elif g==1:
      print('setwise coprime')
  else:
      print('not 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 len(targets) != N:
        is_pw = False

    if len(targets) == 1:
        print("not 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 < len(targets):
            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:
# 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

cnt_one=0
for i in range(N):
    if A[i]==1:
        cnt_one+=1

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

if cnt_one!=0:
    if len(A)==len(set(A))+cnt_one-1:
        pc_flg=True



x = A[0]

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

A = list(set(A))

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:
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):
    if isPrime(m):
        mapa[m]+=1
    else:
        for i in primes:
            if m%i==0:
                mapa[i]+=1
            while m%i==0:
                m//=i
            if m<i:
                break
        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!=n and tmp!=1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

n = int(input())
A = list(map(int,input().split()))
d  =[0]*(2*10**6+1)
c = [0]*(2*10**6+1)
max_val = 2*10**6
for a in A:
    d[a] += 1
A.sort()

set_ = set()
for i in range(2,max_val+1):
    if c[i]==0:
        for j in range(i,max_val+1,i):
            c[j]=1
            if d[j] != 0:
                if i not in set_:
                    set_.add(i)
                d[j] = 0

if len(set_)==n:
    print('pairwise coprime')
elif len(set_)==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()))

isSetWise = False
gcd = A[0]
if A[0] == 1:
    print("setwise coprime")
    exit()
for i in range(1, N):
    if A[i] == 1:
        print("setwise coprime")
        exit()
    gcd = math.gcd(gcd, A[i])
if gcd == 1:
    isSetWise = True

isPairWise = True
for i in range(N-1):
    if math.gcd(A[i], A[i+1]) != 1:
        isPairWise = False
        break

if isPairWise:
    print("pairwise coprime")
    exit()

if isSetWise:
    print("setwise coprime")
    exit()

print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
from functools import reduce

input = sys.stdin.readline


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

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

ans = "pairwise coprime"
for ai in a:
    for i in range(ai, len(ds), ai):
        if ds[i] != 0:
            ans = ""
            break
        ds[i] += 1
    else:
        continue
    break


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

pass

Submission status: Wrong Answer

Solution code:
def sieve_eratosthenes(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes

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

ps = set()
for i,m in enumerate(sieve_eratosthenes(1000000)):
    if m == 1:
        ps.add(i)

from collections import defaultdict
import math

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

a.sort()

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

if g == 1:
    if n > len(ps):
        print("setwise coprime")
    else:
        d = defaultdict(int)
        for i in range(n):
            f = factorization(a[i])
            for x, y in f:
                d[x] += 1
        for i in d.values():
            if i != 1:
                print("setwise coprime")
                exit()
        print("pairwise 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 = [l for l in L if l>1]
if len(L)>1:
  L.sort()
  if L[0]==L[-1]:
    print("not coprime")
    exit()
  for i in range(len(L)-1):
    if L[i]==L[i+1]:
      R = False
print("pairwise coprime" if R else "setwise coprime")

Submission status: Wrong Answer

Solution code:
import math
N = int( input() )
A = sorted( list(map(int, input().split())))
ans = A[0]
# http://www.ysr.net.it-chiba.ac.jp/~yashiro/sosu/
P = list( map( int, "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".split(" ")))
L = []
def factorization(n):
    temp = n
    K = []
    for p in P:
      if p > int(-(-n**0.5//1))+1:
        break
      if temp % p == 0:
        if p in L:
          return True
        K.append( p )
    if K==[]:
      K.append( n )
    L.extend( K )
    return False

for i in range(1, N):
    ans = math.gcd(ans, A[i])
    if ans == 1:
      break
if ans != 1:
  ret = "not coprime"
else:
  ret = "pairwise coprime"
  for a in A:
    if factorization( a ):
      ret = "setwise coprime"
      break
print( ret )

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,10000)):
            if math.gcd(a[i],a[k])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[0]*(10**6+100)
for m in a:
  l[m]=1
x=0
j=2
#print(l)
while j <10**3+1:
  c=0
  k=1
  while j*k<=10**6+1 :
    if l[j*k]==1:
      c+=1
    k+=1
  if c==n:
    print("not coprime")
    exit()
  elif c>1:
    x=1
  j+=1 
  
if x==1:
  print("setwise coprime")
else:
  print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce


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

    gcd_ = reduce(math.gcd, A)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
num=A[0]
for a in A:
    num=gcd(num,a)
if num!=1:
    print('not coprime')
else:
    def euler_phi(n):
        """1. nの素因数を列挙する"""
        tmp_n = n
        prime_factors = []
        for k in range(2, int(tmp_n ** 0.5) + 1):
            if tmp_n % k == 0:
                prime_factors.append(k)
                while tmp_n % k == 0:
                    tmp_n = tmp_n // k
        if tmp_n != 1:
            prime_factors.append(tmp_n)

        """2. 素因数について演算する"""
        len_prime = len(prime_factors)
        ans = 0
        for bit_state in range(1, 1 << len_prime):
            popcount = bin(bit_state).count("1")
            tmp = 1
            for i in range(len_prime):
                if (bit_state >> i) & 1:
                    tmp *= prime_factors[i]
                continue
            if popcount % 2 == 1:
                ans += cnt[tmp]
            else:
                ans -= cnt[tmp]

        return ans


    def make_divisors(n):
        """自然数nの約数を列挙したリストを出力する
        計算量: O(sqrt(N))
        入出力例: 12 -> [1, 2, 3, 4, 6, 12]
        """
        divisors = []
        for k in range(1, int(n ** 0.5) + 1):
            if n % k == 0:
                divisors.append(k)
                if k != n // k:
                    divisors.append(n // k)
        divisors = sorted(divisors)
        return divisors


    cnt = [0] * (10**6 + 1)
    for i in range(N):
        for j in make_divisors(A[i]):
            cnt[j] += 1

    ans=0
    for a in A:
        ans+=euler_phi(a)
    

    def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


    if sum(cnt)-ans-1==combinations_count(N,2):
        print('pairwise coprime')
    else:
        print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

d = a[0]
m = a[0]

g = True

for i in range(1, n):
    d = gcd(d, a[i])

if d != 1:
    print("not coprime")
else:
    while len(a) > 1:
        for i in range(0, n, 2):
            b = []
            if i == n-1:
                b.append(a[i])
            else:
                e = gcd(a[i], a[i+1])
                if e != 1:
                    g = False
                    break
                else:
                    b.append(a[i] * a[i+1])
        a = b.copy()

    if not g:
        print("setwise coprime")
    else:
        print("pairwise coprime")

Submission status: Wrong Answer

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

def sieve(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)
    for serial in range(3, num, 2):
        if serial >= sqrt:
            return input_list
        for s in range(serial ** 2, num, serial): 
            input_list[s] = False
            
def fact(num):
    arr = []
    temp = num
    for i in range(2, int(-(-num**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([num, 1])
    return arr

flg=True
prim=sieve(mxa+5)
table=[0]*(mxa+1)
for i in a:
  fc=fact(i)
  fct=[fc[j][0]for j in range(len(fc))]
  for j in fct:
    if table[j]==1:
      flg=False
    table[j]+=1

if flg:
  print("pairwize coprime")
elif n in table:
  print("not coprime")
else:
  print("setwize coprime")

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
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(l[i]%3==0):
        e1+=1
    if(l[i]%5==0):
        e2+=1
    if(l[i]%7==0):
        e3+=1

if(e<=1 and e1<=1 and e2<=1 and e3<=1 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()))

t = A[0]
check = A[0]
for i in range(n):
    s = math.gcd(check, A[i])
    t = math.gcd(t, A[i])
    check *= (A[i] // t)


if t == 1 and s == 1:
    print('pairwise coprime')
elif t == 1:
    print('setwise coprime')
else:
    print('not coprime')