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:
#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()
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:
import math
n = int(input())
a = list(map(int,input().split()))
x = True
for i in range(n - 1):
    for j in range(i + 1,n):
        if math.gcd(a[i],a[j]) != 1:
            break
    else:
        continue
    break
else:
    print("pairwise coprime")
    x = False
if x:
    ans = a[0]
    for i in range(1,n):
        ans = math.gcd(ans,a[i])
    if ans == 1:
        print("setwise coprime")
        x = False
if x:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort()

pc = True
gg = False
cnt = Counter()

fm = {}

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

for a in factorization(A[0]):
    if a > 1:
        cnt[a] = 1

for i in range(1, N):
    for a in factorization(A[i]):
        if cnt[a] >= 1:
            pc = False
        if a > 1:
            cnt[a] += 1

if pc:
    print("pairwise coprime")
elif cnt.most_common(1)[0][1] < N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:

import math
#素数列挙
def get_primes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        A = [i for i in A if i%prime!=0]

    P.extend(A)
          
    return P


def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    sosus = set(get_primes(max(A)+1))
    dvd = set()



    val = A[0]
    for i in A:
        val = math.gcd(i,val)

    if val ==1:
        pass
    else:
        print('not coprime')
        return

    for i in A:
        tmp=[]
        for j in sosus:
            if i % j ==0:
                tmp.append(j)
                while i % j ==0:
                    i //=j
            if i ==1:
                break
        sosus.difference_update(tmp)
        
        if i != 1:
            break
    else:
        print('pairwise coprime')
        return

    print('setwise coprime')

resolve()

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
l = input()
a = l.split(' ')

chk = 0

for i in range(n):
    for j in range(i+1,n):
        if(math.gcd(int(a[i]), int(a[j]))!=1):
            chk = 1

tmp = int(a[0])

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


if(chk==0):
    print("pairwise coprime")

elif(tmp==1):
    print("setwise coprime")

else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    sc = False
    key = a[0]
    for i in range(1, n):
        key = math.gcd(key, a[i])
    
    if key == 1:
        sc = True
    
    key = a[0]
    pc = True
    for i in range(1, n):
        if math.gcd(key, a[i]) > 1:
            pc = False
            break
        key *= a[i]
    
    if pc:
        print("pairwise coprime")
    elif sc:
        print("setwise coprime")
    else:
        print("not coprime")
        
    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
import sys

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

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
if gcd_list(a) != 1:
  print('not coprime')
  sys.exit()

for i in range(n):
  for j in range(i+1, n):
    if math.gcd(a[i], a[j]) != 1:
      print('setwise coprime')
      sys.exit()
      
print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

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

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

s = 1
LIS = list(itertools.combinations(A, 2))
for i in LIS:
    if math.gcd(i[0], i[1]) != 1:
        s = 0
        break

# -> [(1, 2), (1, 3), (2, 3)]

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

Submission status: Time Limit Exceeded

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, As):
    import math
    primes = [0] * (max(As) + 1)
    pairwise_flg = True
    for x in As:
        i = 2
        while x != 1:
            if x % i == 0:
                if primes[i] != 0:
                    pairwise_flg = False
                    break
                primes[i] = 1
                while x % i == 0:
                    x = x // i
            else:
                i += 1
                if i > math.sqrt(x):
                    if primes[x] != 0:
                        pairwise_flg = False
                    else:
                        primes[x] = 1
                    break
        if not pairwise_flg:
            break
    if pairwise_flg:
        print('pairwise coprime')
        return

    tmp = math.gcd(As[0], As[1])
    for A in As:
        tmp = math.gcd(tmp, A)
    if tmp == 1:
        print('setwise coprime')
        return

    print('not coprime')


if __name__ == '__main__':
    N = int(input())
    As = [int(i) for i in input().split()]
    # # test
    # import random
    # N = 10 ** 6
    # As = [random.randint(1, 10 ** 6) for _ in range(N)]
    solve(N, As)

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:
# -*- coding: utf-8 -*-
import copy

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

    return divisors


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

pcf = True
pc = set(make_divisors(a[0]))
pcl = len(pc)
sc = copy.deepcopy(pc)

for i in a[1:]:
    d = set(make_divisors(i))
    dl = len(d) - 1
    pc = pc.union(d)
    pcl2 = len(pc)
    if pcl + dl != pcl2:
        pcf = False
    pcl = pcl2

    sc = sc.intersection(d)

if pcf:
    print("pairwise coprime")
elif len(sc) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
from functools import reduce

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


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


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


def is_coprime(x, y):
    return math.gcd(x, y) == 1


combi = list(itertools.combinations(A, 2))
allCoprime = True
allNotCoprime = True
for x in combi:
    if is_coprime(x[0], x[1]):
        allNotCoprime = False
    else:
        allCoprime = False

if gcd_list(A) == 1:
    allNotCoprime = False


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

Submission status: Time Limit Exceeded

Solution code:
import math
def main():

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


    isprime = [True] * (1 + pow(10, 6))
    prime = []
    SPF = [None] *  (1 + pow(10, 6))
    def manipulated_seive(N):
        isprime[0] = isprime[1] = False
        for i in range(2, N):
            if isprime[i] == True:
                prime.append(i)
                SPF[i] = i
            j = 0
            while (j < len(prime) and i * prime[j] < N and prime[j] <= SPF[i]):

                isprime[i * prime[j]] = False
                SPF[i * prime[j]] = prime[j]

                j += 1
        return

    manipulated_seive(max(A))
    prime = set(prime)

    d = dict()
    ispair = True
    isset = True

    for v in A:
        for p in prime:
            if p <= v:
                if v % p == 0:
                    d[p] = d.get(p, 0) + 1
                    u = v // p
            else:
                break
    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"

    return "not coprime"

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

Submission status: 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

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():
    n = ni()
    A = lma()
    d=collections.Counter()
    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
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):
    if n == 1:
        return {1: 1}

    prime_dict = {}
    for i, b in enumerate(ela):
        if not b:
            continue
        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 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(1001)

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

from math import gcd

def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a

f = True
l = set()
for i in range(n):
    x = prime_factorize(a[i])
    y = l|x
    if len(l)+len(x)!=len(y):
        f = False
        break
    l = y
    
if f:
    print('pairwise coprime')
    exit()

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

if g==1:
    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()))

pw_ok = True
pw = a[0]
sw = a[0]
for i in a[1:]:
    sw = gcd(sw, i)
    if not pw_ok and sw == 1: break
    g = gcd(pw, i)
    if g != 1:
        pw_ok = False
    pw = pw*i//g # pw = lcm(pw, i)

if pw_ok:
    print('pairwise coprime')
elif sw == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

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

import math
from functools import reduce

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

def sieve_of_eratosthenes(n): 
    candidate = [i for i in range(2, n+1)] 
    prime = []
    limit = math.sqrt(n) + 1 

    while True:
        p = min(candidate) 
        if limit <= p:
            prime.extend(candidate) 
            break
        prime.append(p) 

        candidate = [i for i in candidate if i % p != 0]

    return prime

prime = sieve_of_eratosthenes(10**6+1)

for p in prime:
  cnt = 0
  for a in A:
    if a%p == 0: cnt += 1
    if cnt == 2:
      if gcd_list(A) == 1: print('setwise coprime')
      else: print('not coprime')
      exit()
print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
#素数列挙
def get_primes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        A = [i for i in A if i%prime!=0]

    P.extend(A)
          
    return P


def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    sosus = set(get_primes(max(A)+1))
    dvd = set()






    for i in A:
        tmp=[]
        for j in sosus:
            if i % j ==0:
                tmp.append(j)
                while i % j ==0:
                    i //=j
            if i ==1:
                break
        sosus.difference_update(tmp)
        
        if i != 1:
            break
    else:
        print('pairwise coprime')
        return

    val = A[0]
    for i in A:
        val = math.gcd(i,val)

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

resolve()

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):
    if n == 1:
        return {1: 1}
    if ela[n]:
        return {n: 1}

    prime_dict = {}
    for i, b in enumerate(ela):
        if not b:
            continue
        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 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)

    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)
        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:
'''
Contest 177 - Task E


'''
import functools
import math

def setwise(nums):
    return functools.reduce(lambda a,b: math.gcd(a,b), nums)


def compute(nums):
    gcds = []
    size = len(nums)
    for i in range(size):
        for j in range(i+1, size):
            # print(f"i: {i} and j: {j}")
            gcds.append(math.gcd(nums[i], nums[j]))

    # print(gcds)
    if all(map(lambda n: n==1, gcds)):
        print("pairwise coprime")
    elif setwise(gcds) == 1:
        print("setwise coprime")
    else:
        print("not coprime")

if __name__ == "__main__":
    num = int(input())
    nums = list(map(int, input().split(" ")))
    compute(nums)

Submission status: Time Limit Exceeded

Solution code:
import math

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=math.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=math.gcd(num1,num2) 
  
    for i in range(2,len(a)): 
        gcd=math.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(" ")))
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

base=A[0]
condition=0
for i in range(1,len(A),1):
    g=gcd(base,A[i])
    base*=A[i]
    if g!=1:
        condition=2
        break
base=A[0]
if condition!=0:
    for i in range(1,len(A),1):
        base=gcd(base,A[i])
        if base==1:
            condition=1
            break
ans=["pairwise coprime","setwise coprime","not coprime"]
print(ans[condition])

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)

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

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce


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

    tmp = [0] * N

    s = 1
    for i in range(N):
        tmp[- i - 1] = s
        s *= A[-i - 1]

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

    gcd_ = reduce(math.gcd, A)

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


if __name__ == '__main__':
    main()

Submission status: 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()
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
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:
from subprocess import*
call(('pypy3','-c',"""
# (コードそのまま)

import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n=int(input())

A=list(map(int,input().split()))
from math import sqrt
def eratosu(n):
  if not isinstance(n,int):
    raise TypeError("nがint型になってねえぞ")
  if n<2:
    raise ValueError('nが2よりちっちぇえぞ')
  prime = []
  limit = sqrt(n)
  data = [i+1 for i in range(1, n)]  #2,3,4,...,n
  while True:
    p = data[0]
    if limit <= p:
        return prime + data
    prime.append(p)
    data = [e  for e in data if e % p != 0]
PRIME=eratosu(10**6+10)
@lru_cache(maxsize=10**10)
def bunkai(n):
    if n==1:return []
    ans=[]
    temp=n
    #そんな早くしなくてよかったり、何回もするわけじゃないなら、
    #for i in range(2,int(sqrt(n))+1): とかで
    primelist= PRIME
    for i in primelist:
        if i>sqrt(n):break
        if temp % i ==0:
            ji=0
            while temp%i==0:
                ji+=1
                temp//=i
            ans.append([i,ji])
    if ans==[]:return([[n,1]])  #素数のとき
    if temp!=1:
        ans.append([temp,1])  #4*5882353とか
    return ans

flag=1
seen={i:0 for i in PRIME}
#print(bunkai(3))
for i in A:
    for l in bunkai(i):
        now=l[0] 
        if now==1:continue
        if seen[now]!=0:
            flag=0
        seen[now]+=1
if flag:
    print("pairwise coprime")
elif max(seen.values())!=n:
    print("setwise coprime")
else:
    print("not coprime")

#print(seen)
"""))

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
def lcm(a, b):
    return a*b // gcd(a, b)


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

pw_ok = True
pw = a[0]
sw = a[0]
for i in a[1:]:
    sw = gcd(sw, i)
    if gcd(pw, i) != 1:
        pw_ok = False
    pw = lcm(pw, i)

if pw_ok:
    print('pairwise coprime')
elif sw == 1:
    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()))
MAX = 10 ** 6


def sieve(x):
    """
    Sieve of Eratosthenes
    :param x: max value
    :return: list of bool
    """

    is_prime = [True] * (x + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, x + 1):
        if is_prime[i]:
            for j in range(i * 2, x + 1, i):
                is_prime[j] = False

    return is_prime


is_prime = sieve(MAX)
primes = [i for i, e in enumerate(is_prime) if e]
a.sort()

bl = True
for e in a:
    nxt = []
    for e2 in primes:
        if e % e2 != 0:
            nxt.append(e2)
        else:
            while e % e2 == 0:
                e //= e2

    if e != 1:
        bl = False

    primes = nxt

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

if g == 1 and bl:
    ans = "pairwise coprime"
elif g == 1:
    ans = "setwise coprime"
else:
    ans = "not coprime"

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def gcd(a, b):
    r = a % b

    while r:
        a = b
        b = r
        r = a % b

    return b


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


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


def pairwise():
    LCM = p[0]
    mul = p[0]

    for i in range(1, n):
        LCM = lcm(LCM, p[i])
        mul *= p[i]

        if mul != LCM:
            return False

    return True


def setwise():
    GCD = p[0]
    for i in range(1, n):
        GCD = gcd(GCD, p[i])

    return GCD == 1


GCD = p[0]
LCM = p[0]
mul = p[0]

done = False

for i in range(1, n):
    GCD = gcd(GCD, p[i])

    if not done:
        LCM = lcm(LCM, p[i])
        mul *= p[i]

    if LCM != mul:
        done = True

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import gcd
input=sys.stdin.readline
#sys.setrecursionlimit(10**6)
from numba import njit

@njit
def Ed(num,ycnt):
    for i in range(1,int(num**0.5)+1):
        if num%i==0:
            ycnt[i]+=1
            if num//i!=i:
                ycnt[num//i]+=1

def main():
    input()
    a=[int(i) for i in input().split()]

    N=10**6+1
    ycnt=[0]*N
    gsum=a[0]

    for i in a:
        gsum=gcd(gsum,i)
        Ed(i,ycnt)
    
    for i in range(N):
        if ycnt[i]>=2 and i!=1:
            break
    else:
        print("pairwise coprime")
        exit()
    if gsum==1:
        print("setwise coprime")
    else:print("not coprime")

if __name__=="__main__":main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N=int(input())
A=list(map(int,input().split()))

import math
def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

data=get_sieve_of_eratosthenes(1000000)
def prime_factorization(n):
    arr=[]
    for p in data:
        if p >n:
            break
        if n%p==0:
            arr.append(p)
        
    return arr

isPairwise = True
isSetwise = True
dict=defaultdict(lambda:0)

for i in range(N):
    arr = prime_factorization(A[i])
    for j in range(len(arr)):
        prime=arr[j]
        if prime!=1:
            dict[prime]+=1

for i in dict.values():
    if i==N:
        isPairwise=False
        isSetwise=False
    elif i>1:
        isPairwise=False
    else:
        pass

if isPairwise:
    print('pairwise coprime')
elif isSetwise:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
pgcd = True
sgcd = a[n-1]

for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
    if sgcd==1:
        break
if sgcd!=1:
    print('not coprime')
else:
    l = [a[0]]
    for i in range(1,n):
        for aa in l:
            if math.gcd(aa, a[i]) != 1:
                print('setwise coprime')
                break
        else:
            l.append(a[i])
            continue
        break
    else:
        print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math

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

lcmv = a[0]
sekikun = a[0]
for i in range(1, n):
    gcdv = math.gcd(lcmv, a[i])
    lcmv *= a[i]
    lcmv //= gcdv
    sekikun *= a[i]
    if sekikun != lcmv:
        break
    if i == n - 1:
        print("pairwise coprime")
        exit()


gcdv=a[0]
for i in range(1, n):
    gcdv = math.gcd(gcdv, a[i])
if gcdv == 1:
    print("setwise coprime")
else:
    print("not coprime")