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: Time Limit Exceeded

Solution code:
import math 
import sys
from functools import reduce

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

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

if gcd_list(A) > 1:
  print("not coprime")
  sys.exit()
  
union = set()
intersection = set()

visited = set()
A_set = set()

flag = False
MAX = 10**6
for a in A:
  #print(visited, a)
  if a in visited: 
    print("setwise coprime")
    sys.exit()
    flag = True 
    break
  b = a
  p = 2
  while p <= MAX and b > 1:
    if b % p == 0:
      q = p
      for q in range(p,MAX+1,p): #pの倍数を全てvisitedへ
        visited.add(q)     
    while b % p == 0:
      b = b // p
    p += 1

print("pairwise coprime")



"""
def raise_prime(B):
  n = len(B)
  if n == 1:
    
  C = B[0: n//2]
  D = B[n//2:n]
"""


  
  
"""
for a in A:
  p = 2
  while p <= N:
    if p not in visited:
      
      
    
  
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    union.add()
    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
"""

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    S = 1
    d = dict()
    for x in A:
        S *= x
    flag = True
    for x in A:
        if gcd(S//x, x) == 1:
            continue
        else:
            flag = False
            break
    if flag:
        print("pairwise coprime")
    else:
        g = A[0]
        for x in A[1:]:
            g = gcd(x, g)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from collections import Counter

def factorize(n):
    rt = int(sqrt(n)+1)
    facts = []
    for i in range(2, rt+1):
        if n % i == 0:
            facts.append(i)
            while n % i == 0:
                n //= i
    if n != 1:
        facts.append(n)
    return facts

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

P = Counter()

for a in A:
    p = Counter(factorize(a))
    P += p

p_max = max(P.values()) if P.values()  else 1
if  p_max == 1:
    print('pairwise coprime')
elif  p_max <  n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    d = set()
    while num%2==0:
        d.add(2)
        num //= 2
    for i in range(3,int(sqrt(num))+1,2):
        while num%i==0:
            d.add(i)
            num //= i
    if num>2:
        d.add(num)
    return list(d)

n = inp()
x = ip()
ans = 'pairwise coprime'
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    #print(t)
    if t != 1:
        ans = 'setwise coprime'
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    st = set()
    for i in x:
        for j in pfact(i):
            if j not in st:
                st.add(j)
            else:
                ans = 'setwise coprime'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
A=[int(x) for x in input().split()]
gcd=A[0]
for i in range(1,N):
    gcd=math.gcd(gcd,A[i])
if gcd!=1:
    print("not coprime")
else:
    flag=1
    maxA=max(A)
    primeset=set()
    primeset.add(2)
    for h in range(3,maxA+1):
        primeflag=1
        for k in primeset:
            if h%k==0:
                primeflag=0
                break
        if primeflag==1:
            primeset.add(h)
    already_prime=set()
    for j in range(N):
        now=A[j]
        for k in primeset:
            if now%k==0:
                if k in already_prime:
                    flag=0
                    break
                else:
                    already_prime.add(k)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3


import collections
import functools

try:
    from math import gcd
except ImportError:
    from fractions import gcd


L = 10 ** 6 + 1


def sieve_of_eratosthenes(end):
    """Enumerates prime numbers below the given integer `end`.

    Returns (as a tuple):

    - `is_prime`: a list of bool values.
      If an integer `i` is a prime number, then `is_prime[i]` is True.
      Otherwise `is_prime[i]` is False.
    - `primes`: a list of prime numbers below `end`.
    """

    if end <= 1:
        raise ValueError("The integer `end` must be greater than one")
    is_prime = [True for _ in range(end)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for i in range(2, end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes


PRIMES = sieve_of_eratosthenes(L)


def factorize(n):
    factors = []
    if n < 2:
        return factors
    for p in PRIMES:
        if p * p > n:
            break
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        factors.append(n)
    return factors


def is_pairwise_coprime(bs):
    lcm_fs = dict()
    all_fs = collections.Counter()
    for b in bs:
        fs = collections.Counter(factorize(b))
        all_fs.update(fs)
        for k, v in fs.items():
            if k in lcm_fs:
                lcm_fs[k] = max(lcm_fs[k], v)
            else:
                lcm_fs[k] = v
    return all(lcm_fs[k] == all_fs[k] for k in lcm_fs)


def is_setwise_coprime(bs):
    return functools.reduce(gcd, bs) == 1


def main():
    n = int(input())
    bs = [int(b) for b in input().split()]
    if is_pairwise_coprime(bs):
        print("pairwise coprime")
    elif is_setwise_coprime(bs):
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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:
  mm=[0 for i in range(10**6+1)]
  f=True
  for i in a:
    if mm[i] and i!=1:
      f=False
      break
    mm[i]=1
    for j in range(168):
      if i%p[j]==0:
        if mm[p[j]] and i!=p[j]:
          f=False
          break
        mm[p[j]]=1
        if mm[i//p[j]] and i//p[j]!=p[j] and i!=p[j]:
          f=False
          break
        mm[i//p[j]]=1
    if not f:
      break
  if f:
    print("pairwise coprime")
  else:
    print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
N = int(input())
A = list(map(int,input().split()))
A.sort()
c = 0
flg = 0
for i in range(N-1,0,-1):
  for j in range(i-1,-1,-1):
    c = gcd(A[i],A[j])
    if c != 1:
      flg = 1
a = gcd(A[0],A[1])
for i in range(2,N):
  a = gcd(a,A[i])
if a == 1 and flg == 0:
  print("pairwise coprime")
elif a == 1 and flg == 1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:

import math
n=int(input())
a = list(map(int, input().split()))
pair_check=[]
for i in range(n):
    for k in range(i+1,n):
        pair_check.append(math.gcd(a[i],a[k]))
ans = a[0]
pair_check_check=0
for i in range(1, n):
    ans = math.gcd(ans, a[i])

for i in range(len(pair_check)):
    if pair_check[i]==1:
        pair_check_check+=1

if pair_check_check==len(pair_check):
    print("pairwise coprime")
    exit()

elif ans==1:
    print("setwise coprime")
    exit()
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(raw_input())
arr = raw_input()  
v = list(map(int,arr.split(' ')))

def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)
l=v[0]
g=v[0]
p=v[0]
for i in range(1,len(v)):
    l=l*v[i]/gcd(l,v[i])
    g=gcd(g,v[i])
    p*=v[i]
if p==l:
    print "pairwise coprime"
elif g==1:
    print "setwise coprime"
else:
    print "not coprime"

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())

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

gcdAll = A[0]
isPairwise = True

for j in range(1, N):
    gcdAll = math.gcd(gcdAll, A[j])
    if not isPairwise:
        continue
    for i in range(0, j):
        gcdNow = math.gcd(A[i], A[j])
        if gcdNow != 1:
            isPairwise = False
            break

if isPairwise:
    print('pairwise coprime')
elif gcdAll == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd
n = int(input())
a = list(map(int, input().split()))
a.sort()
used = [False] * (10**6+1)

def sieve_of_erastosthenes(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

input_list = sieve_of_erastosthenes(int(-(-10**3//1))+1)
prime_list = [i for i, b in enumerate(input_list) if b == True]

def factorization(n):
    arr = []
    temp = n
    for i in prime_list:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

g = a[0]
arr = factorization(a[0])
for i in arr:
    used[i] = True

pair = True
for i in range(n-1):
    g = gcd(g, a[i+1])
    # 一度でも互いに素でない組合せが出たらpariwise coprimeではない
    if pair:
        arr = factorization(a[i+1])
        for i in arr:
            if i == 1: continue
            if used[i]: pair=False
            used[i] = True
if g > 1:
    print('not coprime')
    exit(0)
if not pair:
    print('setwise coprime')
    exit(0)
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import functools
import math

N = input()
A = list(map(int, input().split()))
A = sorted(A)
gcd = functools.reduce(math.gcd, A)
if 2 <= gcd:
  print("not coprime")
else:
  isPC = True
  for i, a in enumerate(A):
    for aa in A[i+1:]:
      if 1 != math.gcd(a, aa):
        isPC = False
        break
    if not isPC:
      break
  if isPC:
    print("pairwise coprime")
  else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.readline
import time
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
from collections import deque 


def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

def lcd(a, b):
    return a * b // gcd(a, b)

N = inp()
A = inpl()

pw = True
pwnum = A[0]

swnum = A[0]

for i in range(1, N):
    if pw:
        gc = gcd(pwnum, A[i])
        if gc != 1:
            pw = False
        pwnum = pwnum * A[i] // gc
    if swnum != 1:
        swnum = gcd(swnum, A[i])

if pw:
    print('pairwise coprime')
elif swnum == 1:
    print('setwise coprime')
else:
    print('not coprime')

# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce


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

    if not reduce(gcd, As) == 1:
        print('not coprime')
    else:
        flag = True
        for i in range(len(As) - 1):
            for j in range(i + 1, len(As)):
                if not gcd(As[i], As[i + 1]) == 1:
                    flag = False
                    break
            if not flag:
                break
        if flag:
            print('pairwise coprime')
        else:
            print('setwise coprime')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, AS):
    is_pairwise = True
    maxAS = max(AS)
    sieved = [False] * (maxAS + 10)
    for p in range(2, maxAS + 1):
        if sieved[p]:
            continue
        # p is prime
        x = p + p
        while x <= maxAS:
            sieved[x] = True
            x += p
        sum_div = 0
        for i, a in enumerate(AS):
            dividable = 0
            while a % p == 0:
                a //= p
                dividable = 1
            AS[i] = a
            sum_div += dividable
        if sum_div >= 2:
            is_pairwise = False
        if sum_div == N:
            return "not coprime"

    if is_pairwise:
        return "pairwise coprime"
    return "setwise coprime"


def main():
    # parse input
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


# tests
T1 = """
3
3 4 5
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
pairwise coprime
"""

T2 = """
3
6 10 15
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
setwise coprime
"""

T3 = """
3
6 10 16
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
not coprime
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Time Limit Exceeded

Solution code:
def find_gcd(x, y): 
    while(y): 
        x, y = y, x % y 
  
    return x 
      
n=int(input())
a=input().split()
i=0
j=1
flag=1
while i<n-1:
    if j==n:
        i+=1
        j=i+1
    else:
        gcd=find_gcd(int(a[i]),int(a[j]))
        if gcd!=1:
            flag=0
            break
        j+=1
if  flag==1:
    print('pairwise coprime')
    
else:
    num1=int(a[0]) 
    num2=int(a[1]) 
    gcd=find_gcd(num1,num2) 
  
    for i in range(2,len(a)): 
        gcd=find_gcd(gcd,int(a[i])) 
    if gcd==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
import 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
if A==[1]*N:
  print('pairwise coprime')
  exit()
a=A[0]
d=a
if A[0]!=1:
  D={}
  x=0
  for i in range(N):
    d=math.gcd(d,A[i])
    c=A[i]
    F=factorization(A[i])
    for a,b in F:
      if a not in D:
        D[a]=1
      else:
        x=1
      #互いに素じゃない二組がある  

  if x==1 and d==1:
    print('setwise coprime')
  elif x==0 and d==1:
    print('pairwise coprime')
  else:
    print('not coprime')
else:
  D={}
  x=0
  for i in range(N):
    if A[i]!=1:
      F=factorization(A[i])
      for a,b in F:
        if a not in D:
          D[a]=1
        else:
          x=1
    
  if x==1:
    print('setwise coprime')
  else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
## 素因数分解
#nを素因数分解したリストを返す
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table



N = INT()
A = LIST()
flag = False
A.sort(reverse=True)


memo = defaultdict(int)
s = set()
for a in A:
    d = divisor(a)
    # print(d)
    s = s.union(set(d))
    for y in d:
        if y == 0:
            continue
        # elif memo[y] == 0:
        memo[y] += 1
        # else:
        #     flag == False
# print(s)
# exit()
# for a in A:
#     d = divisor(a)
#     set(d)
#     diff = s - set(d)
# for i in range(len(A) - 1):
# A[i]
cnt = 0
for a in A:
    d = divisor(a)
    # print(d)
    for y in d:
        if y == 1:
            continue
        if memo[y] == 1:
            continue
        else:
            # print("d:", d)
            cnt += 1
if cnt == 0:
    flag = True
    
if flag == True:
    print("pairwise coprime")
elif reduce(gcd, A) == 1:
        print("setwise coprime")
else:
    print("not coprime")
    

    # A.sort()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

if __name__ == '__main__':

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

    gcd_ = gcd(A[0], A[1])
    for i in range(2, len(A)):
        gcd_ = gcd(gcd_, A[i])

    set_wise = False
    if gcd_ == 1:
        set_wise = True

    pairwise = True
    for i in range(n):
        for j in range(i+1, n):
            gcd_ = gcd(A[i], A[j])
            if gcd_ != 1:
                pairwise = False

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

Submission status: Time Limit Exceeded

Solution code:
import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict
from functools import lru_cache


@lru_cache(None)
def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


def merge_dict(d1, d2):
    for k, v in d2.items():
        d1[k] += v
    return d1


def input():
    return sys.stdin.readline().strip()


def prime_factorization(N: int) -> dict:
    primes = defaultdict(int)
    primes[1] = 1
    if N < 2:
        return primes
    i = 2
    while i * i <= N:
        while N % i == 0:
            primes[i] += 1
            N = N // i
        i += 1
    if N != 1:
        primes[N] = 1
    return primes


def main():
    n = int(input())
    A = [int(i) for i in input().split()]
    primes = defaultdict(int)
    is_pair_gcd = True
    # pre-process
    for i in range(n):
        primes = merge_dict(primes, prime_factorization(A[i]))

    set_gcd = A[0]
    for i in range(1, n):
        set_gcd = gcd(set_gcd, A[i])
        if is_pair_gcd:
            p = prime_factorization(A[i])
            for k, v in p.items():
                if k == 1:
                    continue
                if primes[k] != v:
                    is_pair_gcd = False
                    break
    if is_pair_gcd:
        print("pairwise coprime")
    elif not is_pair_gcd and set_gcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")

    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
m = min(A)
M = max(A)

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(M//2+1)


for i in range(2, M//2+1):
    if checked[i]:
        continue
    if is_pairwise_coprime == False and i > m:
        break
    
    tmp = 0
    for j in range(N):
        if A[j]%i == 0:
            tmp += 1
    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    if is_setwise_coprime == False:
        break
    
    n = i
    while n < M//2+1:
        checked[n] = 1
        n += i

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

Submission status: Time Limit Exceeded

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)
        while n % 2 == 0:
            n //= 2
    i = 3
    while i <= n:
        if n % i == 0:
            e.add(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]
    a.sort()
    n = len(a)
    if n > 78498:
        return 'setwise coprime'
    elif n < 10**4:
        if is_pairwise_coprime(n, a):
            return 'pairwise coprime'
    else:
        for i in range(n-1):
            if 1 < a[i] == a[i+1]:
                return 'setwise coprime'
            used_factor = set()
            for p in PRIMES:
                for ai in a:
                    if ai % p == 0:
                        if p in used_factor:
                            return 'setwise coprime'
                        else:
                            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: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
k = math.gcd(a[0],a[1]) #最大公約数
j = a[0]*a[1]#漱石
v = 0
for i in range(2,n):
    j*=a[i]
    k = math.gcd(k,a[i])
for i in range(n):
    if(j//a[i]%a[i]==0)and(a[i]!=1):
        v += 1
        break
if(k==1):
    if(v>0):
        print("setwise coprime")
    else:
        print("pairwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

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


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

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


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

INF = 1 << 29

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

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


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


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

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

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

    return CONV()


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


sys.setrecursionlimit(200005)


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

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

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

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


def main():
    N = iRaw()
    As = isRaw()
    gcds = gcd_list(As)
    if gcds!=1:
        print("not coprime")
        return
    lcms = lcm_div_list(As)
    mul_d = 1
    lcm_d = 1
    for a in As:
        mul_d = (mul_d*a)
        lcm_d = lcm_div(lcm_d,a)
        if mul_d!=lcm_d:
            print("setwise coprime")
            return
    print("pairwise coprime")
    return
    
main()

Submission status: Time Limit Exceeded

Solution code:
import math


def gcd_muti(A):
    ans = A[0]
    for i in range(1, len(A)):
        ans = math.gcd(ans, A[i])
    return ans


def gcd_every(A):
    s = set()
    fucs = list(map(factorization, A))
    for fuc in fucs:
        for radix, _ in fuc:
            if radix in s:
                # print(s, radix)
                return False
            s.add(radix)
    return True

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

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

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

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

    return arr

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

all_gcd = gcd_muti(A) == 1
every_gcd = gcd_every(A)

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