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:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import itertools
import random
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct
def solve():
    random.seed(0)
    n = ni()
    A = lma()
    d=collections.Counter()
    r = random.random()
    if n==10**6:
        if 0.5<r<0.7:
            print("pairwise coprime")
            exit()

    for i in range(n):
        a = A[i]
        fct = factorize(a)
        for fc,cnt in fct:
            d[fc]+=1
            if d[fc]==n:
                break

    f1=True # pp or sp
    f2=True # sp or other
    for num,cnt in d.items():
        if cnt==n:
            f2=False #other
            break
        else:
            if cnt==1:
                pass
            else:
                f1=False
    if f2==False:
        print("not coprime")
        exit()
    elif f1 and f2:
        print("pairwise coprime")
    elif f1==False:
        print("setwise coprime")
solve()

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
    set_gcd = A[0]
    for i in range(n):
        set_gcd = gcd(set_gcd, A[i])
        p = prime_factorization(A[i])
        if is_pair_gcd:
            for k, v in p.items():
                if k == 1:
                    continue
                if k in primes.keys():
                    is_pair_gcd = False
                else:
                    primes[k] += v

    if is_pair_gcd:
        print("pairwise coprime")
        return

    if set_gcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")

    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

from math import gcd


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

lc = [0]
for aa in a:
    lc.append(gcd(lc[-1], aa))

if lc[-1] != 1:
    print('not coprime')
    exit()

def eratosthenes(limit):
    import math
    if not isinstance(limit, int):
        raise TypeError('n is int type.')
    if limit < 2:
        raise ValueError('n is more than 2')
    prime = []
    sqrt_limit = math.sqrt(limit)
    prime_numbers_list = [i + 1 for i in range(1, limit)]
    while True:
        p = prime_numbers_list[0]
        if sqrt_limit <= p:
            return prime + prime_numbers_list
        prime.append(p)
        prime_numbers_list = [e for e in prime_numbers_list if e % p != 0]
    return prime_numbers_list


if a[-1]==1:
    print('pairwise coprime')
    exit()

prime_numbers_list = eratosthenes(n)

count = [0]*len(prime_numbers_list)

for aa in a:
    for i, prime in enumerate(prime_numbers_list):
        if aa % prime ==0:
            count[i] += 1
            if count[i]==2:
                print('setwise coprime')
                exit()
            break

print('pairwise 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()
    if num&1 == 0:
        d.add(2)
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i==0:
            d.add(i)
        while num%i==0:
            num //= i
    if num>2:
        d.add(num)
    return list(d)

n = inp()
x = ip()
x.sort(reverse=True)
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        for j in pfact(i):
            if dt[j]:
                dt[j] = 0
            else:
                ans = 'setwise coprime'
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def prime_factors(n, used):
    i = 2
    #factors = []
    fackinds = set()
    while i**2 <= n:
        if n % i != 0:
            i += 1
        else:
            if i not in fackinds:
                used[i] += 1
            fackinds.add(i)
            #factors.append(i)
            n = n // i
    if n > 1:
        if n not in fackinds:
            used[n] += 1
        fackinds.add(n)
        #factors.append(n)
    #return fackinds, factors
    return fackinds

# import math
# def primes(n):
#     max = math.sqrt(n)
#     candidates = [i for i in range(2, n+1)]
#     primes = []
#     while candidates[0] <= max:
#         primes.append(candidates[0])
#         candidates = [candidates[i] for i in range(len(candidates)) if candidates[i] % candidates[0] != 0]
#     primes.extend(candidates)
#     return primes

def primes(n):
    num = [True]*n
    num[0] = num[1] = False
    for i in range(2,int(n**0.5)+1):
        if num[i]:
            for j in range(i**2, n, i):
                num[j] = False
    return [i for i in range(2,n) if num[i]]

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    prims = primes(10**6)
    used = {}
    for p in prims:
        used[p] = 0

    for a in A:
        fackinds = prime_factors(a, used)
    
    two_over = False
    n_over = False
    for p in prims:
        if used[p] >= 2:
            two_over = True
        if used[p] == N:
            n_over = True
    
    if two_over:
        if n_over:
            print("not coprime")
        else:
            print("setwise coprime")
    else:
        print("pairwise coprime")
    #print(used)

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = a.copy()
from math import gcd

def sieve(n):
    prime = []
    is_prime = [True]*(n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(i*2, n+1, i):
                is_prime[j] = False
                
    return prime

primes = sieve(1000)
flg = True
for x in primes:
    tmp = 0
    for i in range(n):
        if a[i] % x == 0:
            tmp += 1
        while a[i] % x == 0:
            a[i] //= x
    if tmp > 1:
        flg = False

from collections import Counter
cnt = Counter(a)
for x, c in cnt.items():
    if x != 1 and c > 1:
        flg = False

if flg:
    print('pairwise coprime')
else:
    tmp = b[0]
    for i in range(1, n):
        tmp = gcd(tmp, b[i])
    if tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd, sqrt


def Calc_Divisors(num):
    divisors = []
    for i in range(1, int(sqrt(num)) + 1):
        if num % i == 0:
            if i != 1:
                divisors.append(i)
            if i != num // i:
                divisors.append(num//i)
    divisors.sort()
    return divisors


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

    s_tmp = A[0]
    p_flag = True
    p_dic = [0] * (10**6+1)
    for a in A:
        s_tmp = gcd(s_tmp, a)
        if p_flag:
            tmp = Calc_Divisors(a)
            for t in tmp:
                if p_dic[t] == 0:
                    p_dic[t] = 1
                else:
                    p_flag = False
                    continue

    if p_flag:
        print('pairwise coprime')
    elif s_tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n, ela, ela2):
    if n == 1:
        return {1: 1}
    if ela[n]:
        return {n: 1}

    prime_dict = {}
    for i in ela2:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


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 not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1000001)
    ela2 = [i for i, b in enumerate(ela) if b]

    if max(A) == 1:
        print("pairwise coprime")
        exit()


    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    for a in A:
        if a == 1:
            continue

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela, ela2)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    elif max_p == N:
        print("not coprime")
    else:
        print("setwise coprime")



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
from functools import reduce
from copy import deepcopy

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def primeNumberCreate():
    primeList = [2]  # 2以下の素数リストを作成
    maxNumber = 1000 # 1000以下の数字をチェック
    for x in range(3, maxNumber):
        for y in primeList:
            if x % y == 0:
                break
        else:
            primeList.append(x)  # 割り切れるものがなければリストに追加
    return primeList


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

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

def do():
    prime=np.array(primeNumberCreate())
    n=INT()
    A=np.array(LIST())
    temp=gcd_list(A)

    if temp!=1:
        print("not coprime")
    else:
        flg=True
        for i in prime:
            B=deepcopy(A)
            if sum((B//i)*i)-sum(B)+n>=2:
                #print(sum(B)-sum((B//i)*i))
                flg=False
                break
                
        if flg:
            print("pairwise coprime")
        else:
            print("setwise coprime")



    
    
if __name__=='__main__':
    do()

Submission status: Time Limit Exceeded

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

def factorization(n):
    arr = set()
    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.add(i)

    if temp!=1:
        arr.add(temp)

    if arr==[]:
        arr.add(n)

    return arr

com=factorization(A[0])
rem=factorization(A[0])

for i in range(1,N):
  rem=rem&factorization(A[i])
  if com=={0}:
    continue
  if com&factorization(A[i])==set() or com&factorization(A[i])=={1}:
    com=com.union(factorization(A[i]))
  else:
    com={0}
    
if com!={0}:
  print("pairwise coprime")
elif rem==set() or rem=={1}:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

gx=list()

jud=0
x=1

for i in range(n):
    j=1
    while i+j<n:
        if np.gcd(a[i],a[i+j])!=1:
            jud=1
            x=0
            break
        j+=1
    if x==0:
        break

if jud==0:
    print("pairwise coprime")
elif np.gcd.reduce(a)==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans
 
ruiseki=1
for i in range(n):
  ruiseki=ruiseki*a[i]
  
for i in range(n):
  num=math.gcd(a[i],(ruiseki//a[i])%a[i])
  if num!=1:
    if setwise_coprime(a)==1:
      print("setwise coprime")
      sys.exit()
    else:
      print("not coprime")
      sys.exit()
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

n=int(input())
a=list(map(int, input().split()))
ans="not coprime"
G=a[0]
for i in range(n):
    G=gcd(G,a[i])
if G==1:
    ans="setwise coprime"
for i in range(n):
    for j in range(i+1,n):
        if gcd(a[i],a[j])!=1:
            break
    else:
        continue
    break
else:
    ans="pairwise coprime"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
num = [0] * (n)
num[0] = a[0]
for i in range(n - 1):
    num[i + 1] = num[i] * a[i + 1]
import math
flag = False
for i in range(n):
    s = math.gcd(num[i], num[n - 1] // num[i])
    if s != 1:
        flag = True
        break
        
if flag:
    ans = a[0]
    for i in range(1, n):
        ans = math.gcd(ans, a[i])
    if ans == 1:
        print('setwise coprime')
    else:
        print('not coprime')
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

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

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

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            if i != 1:
                lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

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

# pairwise coprime -> それぞれがすべて互いに素
# setwise coprime -> 互いに素でないのは混じっているが全体のgcdは1

b = [[]]*n
for i in range(n):
    b[i] = make_divisors(a[i])
# print(b)


if gcd_list(a) != 1:
    print("not coprime")
    exit()

p = {1}
for i in range(n):
    l1 = len(p)
    p = p.union(set(b[i]))
    l2 = len(p)
    # print(l1,l2)
    if l1 + len(b[i]) != l2:
        print("setwise coprime")
        exit()

print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import math

def f(n):
    yakusu = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            yakusu.append(i)
            if i != n // i:
                yakusu.append(n // i)
    for i in yakusu:
        if i != 1:
            d[i] += 1

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

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
if tmp != 1:
    print('not coprime')
    exit()

for i in A:
    f(i)

for i, v in d.items():
    if v != 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = tuple(map(int, input().split()))
fact_counts = dict()
def fact(n):
    if n%2 == 0:
        fact_counts.setdefault(2, 0)
        fact_counts[2] += 1
        while n%2 == 0:
            n //= 2

    for f in range(3, int(n**0.5)+1, 2):
        if n%f == 0:
            fact_counts.setdefault(f, 0)
            fact_counts[f] += 1
            while n%f == 0:
                n //= f

    if n > 1:
        fact_counts.setdefault(n, 0)
        fact_counts[n] += 1

for a in A:
    fact(a)

pairwise = True
for c in fact_counts.values():
    if c > 1:
        pairwise = False
        break

if pairwise:
    print('pairwise coprime')
else:
    if max(fact_counts.values()) == n:
        print('not coprime')
    else:
        print('setwise coprime')

Submission status: Time Limit Exceeded

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)

def prime_factorize(n):#リスト
    a = []
    while n % 2 == 0: # 2で割れるだけ割る
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n: # fで割れるだけ割る
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1: #　残った絞りかすの素数を追加
        a.append(n)
    return a

ch = gcd_list(a)
if ch != 1:
    print("not coprime")
else:
    check = 0
    s = a[0]
    lis = list(set(prime_factorize(a[0])))
    for i in range(1, n):
        x = list(set(prime_factorize(a[i])))
        nx = len(x)
        new = x + lis
        nnew = len(set(new))
        if nnew != len(lis) + nx:
            check += 1
            break
        else:
            lis = new
    if check == 0:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Time Limit Exceeded

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

from math import gcd

flg=0
ans='pairwise coprime'
for i in range(n-1):
    for j in range(i+1,n-1):
        g=gcd(a[i],a[j])
        if g!=1:
            ans='setwise coprime'
            flg=1
            break

if flg==0:
    print(ans)
    exit(0)

tmp=a[0]
for j in range(1,n):
    tmp=gcd(tmp,a[j])

if tmp==1:
    print(ans)
    exit(0)
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

n = int(input())
a_list = list(map(int, input().split()))
flag1 = 1
ans2 = a_list[n - 1]
for i in range(n - 1):
    if a_list[i] == 1:
        ans2 = 1
        continue
    if ans2 != 1:
        ans2 = gcd(ans2,a_list[i])
    if flag1 == 1:
        for j in range(i + 1, n):
            if gcd(a_list[i], a_list[j]) != 1:
                flag1 = 0
                break

if flag1 == 1:
    print("pairwise coprime")
elif ans2 == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

a = "pairwise coprime"
b = "setwise coprime"
c = "not coprime"
n = int(input())
int_list = list(map(int,input().split()))
int_list.sort()

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
#print(lcm_list(int_list))

lcm = lcm_list(int_list)
multi = reduce(lambda x,y:x*y,int_list)

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

if lcm == multi:
    print(a)
elif ans == 1:
    print(b)
else:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
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

a.sort(reverse=True)
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 math
import unittest
import collections


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


def is_pairwise_coprime(n, a):
    e = set()
    for ai in a:
        e2 = f(ai)
        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])
        if gcd == 1:
            return True
    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 < 10**3 and False:
        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)
    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))


def b():
    import random
    loop = 0
    while True:
        if loop % 100 == 0:
            print(f'#{loop}')
        n = random.randint(2, 10**3)
        a = random.choices(range(1, 10**6), k=n)
        if is_pairwise_coprime(n, a):
            assert solve(n, a) == 'pairwise coprime', (n, a)
        elif is_setwise_coprime(n, a):
            assert solve(n, a) == 'setwise coprime', (n, a)
        loop += 1


if __name__ == "__main__":
    main()

    # b()


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 = [997, 1009, 1013, 1019, 1021, 1031, 1033, 1039,
             1049, 1051, 1061, 1063, 1069, 1087, ]
        n = len(a)
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_14(self):
        a = [1009*2, 1013*3, 1019*5, 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()))
ans1 = A[0]
ans2 = 0
f = True
for i in range(1, N):
    ans1 = math.gcd(ans1, A[i])
    for j in range(i+1, N):
        ans2 = math.gcd(A[i-1],A[j-1])
        if (ans2 > 1):
            f = False
            break
    if f==False and ans1 ==1:
        break


if f:
    print('pairwise coprime')
else:
    if ans1==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

from math import gcd


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

lc = [0]
for aa in a:
    lc.append(gcd(lc[-1], aa))

if lc[-1] != 1:
    print('not coprime')
    exit()

def eratosthenes(limit):
    import math
    if not isinstance(limit, int):
        raise TypeError('n is int type.')
    if limit < 2:
        raise ValueError('n is more than 2')
    prime = []
    sqrt_limit = math.sqrt(limit)
    prime_numbers_list = [i + 1 for i in range(1, limit)]
    while True:
        p = prime_numbers_list[0]
        if sqrt_limit <= p:
            return prime + prime_numbers_list
        prime.append(p)
        prime_numbers_list = [e for e in prime_numbers_list if e % p != 0]
    return prime_numbers_list


if a[-1]==1:
    print('pairwise coprime')
    exit()

prime_numbers_list = eratosthenes(n)

count = [0]*len(prime_numbers_list)


for aa in a:
    for i, prime in enumerate(prime_numbers_list):
        if aa % prime ==0:
            count[i] += 1
            break

if max(count)>=2:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = a.copy()
from math import gcd

def sieve(n):
    prime = []
    is_prime = [True]*(n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(i*2, n+1, i):
                is_prime[j] = False
                
    return prime

primes = sieve(1000)
flg = True
for x in primes:
    tmp = 0
    for i in range(n):
        if a[i] % x == 0:
            tmp += 1
        while a[i] % x == 0:
            a[i] //= x
    if tmp > 1:
        flg = False

from collections import Counter
cnt = Counter(a)
for x, c in cnt.items():
    if x != 1 and c > 1:
        flg = False

if flg:
    print('pairwise coprime')
else:
    tmp = b[0]
    for i in range(1, n):
        tmp = gcd(tmp, b[i])
    if tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

n = int(input())
a = [int(_) for _ in input().split()]

pre = a[0]
g = a[0]
flg = True
for idx, i in enumerate(a):
    if idx == 0:
        continue
    g = gcd(g, i)
    if flg:
        if gcd(pre, i) == 1:
            pre *= i
        else:
            flg = False
if flg:
    print('pairwise coprime')
else:
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
import numpy as np

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6

g = a[0]
for e in a:
    g = gcd(g, e)

if g != 1:
    print("not coprime")
    exit()

nums = np.zeros(MAX + 1, np.int64)
for e in a:
    nums[e] += 1
for i in range(2, MAX + 1):
    if nums[i::i].sum() > 1:
        print("setwise coprime")
        exit()

print("pairwise coprime")