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

#iを篩にかけた数をmemo
def sieve_table(n):
    table = [0] * (n+1)
    for i in range(2, n+1):
        if table[i] > 0:
            continue

        table[i] = i
        for j in range(2 * i, n+1, i):
            table[j] = i
    return table

#tableから素因数分解
def factorization_from_table(x, table):
    res = set()
    while x > 1:
        res.add(table[x])
        x //= table[x]
    
    return res

table = sieve_table(10 ** 6)
set_primes = set()

flg = True
for i in range(n):
    res = factorization_from_table(a[i], table)
    if len(set_primes & res) > 0:
        flg = False
        break
    
    set_primes = set_primes | res

if flg:
    print('pairwise coprime')
else:
    from math import gcd
    tmp = a[0]
    for i in range(1, n):
        tmp = gcd(tmp, a[i])
    
    if tmp == 1:
        print('setwise coprime')
    else:
        print('not 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 math
def is_primes(n):
    primes = [1]*n
    primes[0] =0
    primes[1] =0
    for i in range(2,int(n**0.5)+1):
        if primes[i] ==1:
            for j in range(2*i,n,i):
                primes[j] = 0
    return primes

def factorize(n,prms):
    b = 2
    fct = []
    while b * b <= n:
        if not prms[b]:
            continue
        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

n =ni()
A = lma()
mx= 2*10**6
prms = is_primes(mx+1)
d=collections.Counter()
for a in A:
    fct = factorize(a,prms)
    #print(fct)
    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
            break
if f2==False:
    print("not coprime")
elif f1 and f2:
    print("pairwise coprime")
elif f1==False:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
def max(a,b):
    if a>b:
        return a
    else:
        return b
 
def min(a,b):
    if a>b:
        return b
    else:
        return a
 
def gcd(a,b):
    a,b = max(a,b),min(a,b)
    while a%b!=0:
        a,b = b,a%b
    return b
 
 
def gcdl(A):
    if len(A)==2:
        return gcd(A[0],A[1])
    elif len(A)==1:
        return A[0]
    else:
        return gcd(gcdl(A[:len(A)//2]),gcdl(A[len(A)//2:]))


def sieve_of_eratosthenes(n):
    pl = [i for i in range(2, n + 1)]
    i=0
    D = [0]*(n+1)
    p = pl[0]
    while p**2<=n:
        pl1 = []
        for j in range(len(pl)):
            if pl[j]%p!=0 or j<=i:
                pl1.append(pl[j])
            else:
                D[pl[j]] = p
        pl = pl1
        i+=1
        p=pl[i]
    for p in pl:
        D[p] = p
    return D

import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    D = sieve_of_eratosthenes(1000000)

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

    F = set([])
    flag = True
    for a in A:
        b = a
        fact = set([])
        while b>1:
            fact.add(D[b])
            b//=D[b]
        if len(F & fact)>0:
            flag=False
            break
        F = F | fact

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
        if k: ret[i] = k
        i += 1 + i % 2
    if n > 1: return {n}
    return set(ret)
N=int(input())
L=list(map(int,input().split()))
 
gc=L[0]
for i in L:
  gc=gcd(i,gc)
  if gc==1:
    break
if gc!=1:
  print("not coprime")
  exit()
 
 
ans=set()
c=0
for i in L:
  c+=len(primeFactor(i))
  ans|=set(primeFactor(i))
if c==len(ans):
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Time Limit Exceeded

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

#iを篩にかけた数をmemo
def sieve_table(n):
    table = [0] * (n+1)
    for i in range(2, n+1):
        if table[i] > 0:
            continue

        table[i] = i
        for j in range(2 * i, n+1, i):
            table[j] = i
    return table

#tableから素因数分解
def factorization_from_table(x, table):
    res = set()
    while x > 1:
        res.add(table[x])
        x //= table[x]
    
    return res

table = sieve_table(10 ** 6)
set_primes = set()

flg = True
for i in range(n):
    res = factorization_from_table(a[i], table)
    if len(set_primes & res) > 0:
        flg = False
        break
    
    set_primes = set_primes | res

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

Submission status: Time Limit Exceeded

Solution code:
import math
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def divisor(n):
    ass = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            if i != 1:
                ass.append(i)
            if i ** 2 == n:
                continue
            ass.append(n // i)
    return ass

n = int(input())
a = list(map(int, input().split()))
pair = False
divisors = set(divisor(a[0]))
ggcd = a[0]
for i in range(1, n):
    divs = set(divisor(a[i]))
    if len(divs & divisors) != 0:
        pair = True
    else:
        divisors = set(list(divisors) + list(divs))
    ggcd = math.gcd(ggcd, a[i])
if ggcd != 1:
    print("not coprime")
else:
    if pair:
        print("setwise coprime")
    else:
        print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
import copy

n=int(input())
a=list(map(int,input().split()))
a.sort()
ch5=0
for  M in a:
  if M==1:
    ch5+=1
    a.remove(M)
  if M>1:
    break
if ch5>0:
  a.append(1)
B=copy.deepcopy(a)


dp=[0 for _ in range(1000000+1)]

sosuu = [2]
A = 1000
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.append(L)
        
L=len(a)

if len(a)>79000:
  g=a[0]
  for h in range(1,L):
    g=math.gcd(g,a[h])
    
  if g==1:
    print('setwise coprime')
    
  else:
    print('not coprime')
  
  

else:
  ch1=0
  ch3=0
  for w in sosuu:
    ch2=0
    for q in range(L):
      if B[q]%w==0:
        ch2+=1
        S=B[q]
        while S%w==0:
          S=S//w
        B[q]=S
    if ch2>1:
      ch3+=1
  d={}
  ch4=0
  for u in B:
      if u>1000:
        if u not in d:
          d[u]=0
        else:
          ch4+=1
  if ch3==0 and ch4==0:
    print('pairwise coprime')
    
      
  
  
    
  else:
    g=a[0]
    for h in range(1,L):
      g=math.gcd(g,a[h])
    
    if g==1:
      print('setwise coprime')
    
    else:
      print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd, sqrt, ceil
from functools import reduce
_, *aa = map(int, open(0).read().split())

def factorize(n):
    factors = set()
    if n % 2 == 0:
        factors.add(2)
        n //= 2
    while n % 2 == 0:
        n //= 2
    for i in range(3, ceil(sqrt(n + 1)) + 1):
        if n % i == 0:
            factors.add(i)
            n //= i
        while n % i == 0:
            n //= i
    if n > 2:
        factors.add(n)
    return factors

def main(aa):
    
    pair_co = True
    max_factors = set()
    for a in aa:
        factors = factorize(a)
        new_max_factors = max_factors | factors
        if len(new_max_factors) < len(max_factors) + len(factors):
            pair_co = False
            break
        max_factors = new_max_factors
#     if min_factors:
#         return 'not coprime'
#     elif pair_co
    if pair_co:
        return 'pairwise coprime'
    elif reduce(gcd, aa) == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'
        

print(main(aa))

Submission status: Time Limit Exceeded

Solution code:
def max(a,b):
    if a>b:
        return a
    else:
        return b
 
def min(a,b):
    if a>b:
        return b
    else:
        return a
 
def gcd(a,b):
    a,b = max(a,b),min(a,b)
    while a%b!=0:
        a,b = b,a%b
    return b
 
 
def gcdl(A):
    if len(A)==2:
        return gcd(A[0],A[1])
    elif len(A)==1:
        return A[0]
    else:
        return gcd(gcdl(A[:len(A)//2]),gcdl(A[len(A)//2:]))


def sieve_of_eratosthenes(n):
    pl = [i for i in range(2, n + 1)]
    i=0
    D = [0]*(n+1)
    p = pl[0]
    while p**2<=n:
        pl1 = []
        for j in range(len(pl)):
            if pl[j]%p!=0 or j<=i:
                pl1.append(pl[j])
            else:
                D[pl[j]] = p
        pl = pl1
        i+=1
        p=pl[i]
    for p in pl:
        D[p] = p
    return D

D = sieve_of_eratosthenes(1000000)

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

F = set([])
flag = True
for a in A:
    b = a
    fact = set([])
    while b>1:
        fact.add(D[b])
        b//=D[b]
    if len(F & fact)>0:
        flag=False
        break
    F = F | fact

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

Submission status: Time Limit Exceeded

Solution code:
import math
import copy

n=int(input())
a=list(map(int,input().split()))
a.sort()
ch5=0
for  M in a:
  if M==1:
    ch5+=1
    a.remove(M)
if ch5>0:
  a.append(1)
B=copy.deepcopy(a)


dp=[0 for _ in range(1000000+1)]

sosuu = [2]
A = 1000
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.append(L)
        
L=len(a)

if len(a)>80000:
  g=a[0]
  for h in range(1,L):
    g=math.gcd(g,a[h])
    
  if g==1:
    print('setwise coprime')
    
  else:
    print('not coprime')
  
  

else:
  ch1=0
  ch3=0
  for w in sosuu:
    ch2=0
    for q in range(L):
      if B[q]%w==0:
        ch2+=1
        S=B[q]
        while S%w==0:
          S=S//w
        B[q]=S
    if ch2>1:
      ch3+=1
  d={}
  ch4=0
  for u in B:
      if u>1000:
        if u not in d:
          d[u]=0
        else:
          ch4+=1
  if ch3==0 and ch4==0:
    print('pairwise coprime')
    
      
  
  
    
  else:
    g=a[0]
    for h in range(1,L):
      g=math.gcd(g,a[h])
    
    if g==1:
      print('setwise coprime')
    
    else:
      print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in map(int, input().split()):
  counts[a] += 1

max_count = 0
for i in range(2,M):
  count = 0
  for j in range(i,M,i):
    count += counts[j]
  max_count = max(max_count,count)

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
import operator
n = int(input())
num_list = [int(i) for i in input().split()]
count = 0

# for i in range(n-1):
#     for j in range(i+1,n):
#         if math.gcd(num_list[i],num_list[j]) == 1:
#             count += 1
#         else:
#             break

# if count == n * (n-1) / 2:
#     print("pairwise coprime")

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

if reduce(lcm_base, num_list, 1) == reduce(operator.mul, num_list):
    print("pairwise coprime")
elif reduce(math.gcd, num_list) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
r = max(a)+1
s = []
t = [0]*r
for i in range(r):
    s.append([])
for i in range(2,r):
    for j in range(1,-(-r//i)):
        s[i*j].append(i)
for i in range(n):
    for j in range(len(s[a[i]])):
        t[s[a[i]][j]] += 1
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
M=10**6+1
f=lambda p: exit(print(['pairwise','setwise','not'][p]+' coprime'))
n,*l=map(int,open(0).read().split())
from math import *
g=l[0]
for x in l: g=gcd(g,x)
if g>1: f(2)
C=[0]*M
for x in l: C[x]=1
for i in range(2,M):
  if sum(C[j] for j in range(i,M,i))>1: f(1)
f(0)

Submission status: Time Limit Exceeded

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def soinsubunkai_e(n,m):
    a = set()
    i = 1
    for i in m:
        while n % i == 0 and i!=1:
            a.add(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=n
    a.add(nokori)
    return a

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


def era(n):
    a=[2,3]
    b=[0 for i in range(n+1)]
    for i in range(2,int(math.sqrt(n)+1)):
        j=1
        temp=i*j
        while temp<=n:
            b[temp]=1
            temp+=i
    for i in range(4,n+1):
        if b[i]==0:
            a.append(i)
    return a


def main():
    #l,r,d=map(int,input().split())
    n=int(input())
    a=list(map(int,input().split()))
    sosu=[]
    memo = defaultdict(int)
    ccc=era(n)
    for i in range(n):
        if a[i]!=1:
            temp=soinsubunkai_e(a[i],ccc)
        else:
            temp={}
        for j in temp:
            memo[j]+=1

    memo.pop(1,None)
 #   print(sosu)
 #   print(memo)
 #   print(memo.values())
    if len(memo)>=1:
        mmm=max(memo.values())
    else:
        mmm=1
    if mmm<=1:
        print("pairwise coprime")
    elif mmm<n:
        print("setwise coprime")
    else:
        print("not coprime")








if __name__ == "__main__":

    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy
from functools import reduce
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

m = int(input())
a = list(map(int, input().split()))
max_int = math.ceil(math.sqrt(a[m-1]))

tmp = gcd_list(a)

if tmp > 1:
  print("not coprime")
else:
  pro = numpy.prod(a)
  ans = a[0]
  for i in range(1,m):
    ans *= a[i] // math.gcd(ans,a[i])
  if ans == pro:
    print("pairwise coprime")
  else:
    print("setwise coprime")

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])
        if ans == 1:
            return ans
    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:
                return False
            s.add(radix)
    return True


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

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

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

    return arr

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from collections import Counter

def arrayF(n): 
    F=[0]*(n+1) 
    i=2 
    while i*i<=n:
        if F[i] == 0: 
            k=i*i
            while k <= n:
                if F[k] == 0:
                    F[k] = i
                k += i
        i += 1 
    return F


def factorization(x, F): 
    primeFactors = []
    while F[x] > 0:
        primeFactors.append(F[x])
        x //= F[x] 
    if x != 1:
        primeFactors.append(x)
    return set(primeFactors)

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

amax = max(A)
F  = arrayF(amax)

P = Counter()
for a in A:
    p = Counter(factorization(a, F))
    P += p

p_max = max(P.values()) if P 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:
import math
from functools import reduce

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

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

flg=True
flg2=True
table=[0]*(mxa+1)
for (i,x) in zip(a,range(len(a))):
  fc=fact(i)
  for j in fc:
    table[1]=0
    if table[j]==1:
      flg=False
      break
    table[j]+=1

if flg:
  print("pairwise coprime")
elif reduce(math.gcd, a)==1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
def erathos(N):
    res = []
    D = [True] * (N+1)
    D[0] = False
    D[1] = False
    for i in range(2,N+1):
      if not D[i]:
        continue
      res.append(i)
      j = i * 2
      while j <= N:
        D[j] = False
        j += i
    return res;

def prime_set(a, plist):
    res = set()
    for prime in plist:
      while a % prime == 0:
        a = a // prime
        res.add(prime)
    if a > 2:
      res.add(a)
    return res
  
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    plist = erathos(1000)
    
    Factors = []
    for a in A:
      Factors.append(prime_set(a, plist))
    
    fset = set(Factors[0])
    fcommon = set(Factors[0])
    eleflg = True
    for f in Factors[1:]:
      fcommon = fcommon & f
      if len(fset & f) == 0:
        fset = fset | f
      else:
        eleflg = False
        # 互いに素でないペアがいる
        pass
    if len(fcommon) > 0:
      print("not coprime")
    elif eleflg:
      print("pairwise coprime")
    else:
      print("setwise coprime")
    #print(fcommon)
    exit(0)

main()

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from collections import Counter

def arrayF(n): 
    F=[0]*(n+1) 
    i=2 
    while i*i<=n:
        if F[i] == 0: 
            k=i*i
            while k <= n:
                if F[k] == 0:
                    F[k] = i
                k += i
        i += 1 
    return F


def factorization(x, F): 
    primeFactors = set()
    while F[x] > 0:
        primeFactors.add(F[x])
        x //= F[x] 
    if x != 1:
        primeFactors.add(x)
    return Counter(primeFactors)

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

amax = max(A)
F  = arrayF(amax)

P = Counter()
for a in A:
    p = factorization(a, F)
    P += p

p_max = max(P.values()) if P 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:
import math
from functools import reduce
n = int(input())
num_list = [int(i) for i in input().split()]
count = 0

for i in range(n-1):
    for j in range(i+1,n):
        if math.gcd(num_list[i],num_list[j]) == 1:
            count += 1
        else:
            break

if count == n * (n-1) / 2:
    print("pairwise coprime")
elif reduce(math.gcd, num_list) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

tmp = [set() for _ in range(10**6+1)]
for i in range(2, int(10**6//(0.5))+1):
    for j in range(i, 10**6+1, i):
        tmp[j].add(i)


flag = False
for i in range(n-1):
    if len(tmp[a[i]] & tmp[max(a)]) > 0:
        flag = True
        break

if flag == False:
    print("pairwise coprime")
else:
    if reduce(gcd, a) == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Alist = list(map(int, input().split()))
import math
from functools import reduce

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

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

if not gcd_list(Alist) == 1:
  print("not coprime")
  exit()
else:
  flag = True
  for i in range(N):
    for j in range(i+1, N-1+1):
      if flag and (not gcd(Alist[i], Alist[j]) == 1):
        print("setwise coprime")
        flag = False
  if flag:
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd, sqrt


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


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 = list(set(prime_factorize(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:
from math import gcd
from functools import reduce
n = int(input())
a = list(map(int, input().split()))

tmp = [set() for _ in range(10**6+1)]
for i in range(2, 10**6//2+1):
    for j in range(i, 10**6+1, i):
        tmp[j].add(i)

# acc = [set() for _ in range(n)]
# for i, v in enumerate(a):
#     if i == 0:
#         acc[i] = tmp[v]
#     else:
#         acc[i] = acc[i-1] | tmp[v]

flag = False
for i in range(n-1):
    if len(tmp[a[i]] & tmp[max(a)]) > 0:
        flag = True
        break

if flag == False:
    print("pairwise coprime")
else:
    if reduce(gcd, a) == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

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

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

  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)


if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import gcd


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    A = nl()
    c = A[0]
    b = []

    m = A[0]

    for i in range(n - 1):
        m *= A[i + 1]

    for i in range(n - 1):
        c = gcd(c, A[i + 1])

    for i in range(n):
        b.append(gcd(A[i], m // A[i]))

    if c == 1 and all([bb == 1 for bb in b]):
        print('pairwise coprime')
    elif c == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
  
def main():
  n = int(input())
  arr = list(map(int, input().split()))
  prime = primes(max(arr))
  pf = isPair(prime, arr)
  sf = isSet(prime, arr)
  

  if pf and sf:
    print('pairwise coprime')
    exit()
  if not sf:
    print('not coprime')
    exit()
  else:
    print('setwise coprime')
    exit()

def isPair(prime, arr):
  searched = []
  for p in prime:
    for a in arr:
      if a % p == 0:
        if p in searched:
          return False
        searched += [p]
  return True

def isSet(prime, arr):
  searched = []
  for p in prime:
    if arr[0] % p == 0:
      searched.append(p)
      
  for a in arr[1:]:
    if len(searched) == 0:
      return True
    tmp = []
    for s in searched:
      if a % s == 0:
        tmp.append(s)
        
    searched = tmp
  if len(searched) == 0:
      return True
  return False
  
  
main()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
inpl = lambda: list(map(int,input().split()))
def primes(N):
    P = []
    for i in range(2,N):
        sieve = 1
        for p in P:
            if p*p > i:
                break
            elif i % p == 0:
                sieve = 0
                break
        if sieve == 0:
            continue
        else:
            P.append(i)
    return P

N = int(input())
A = inpl()

g = A[0]
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

P = primes(1000)
for p in P:
    n = 0
    for i in range(N):
        if A[i] % p == 0:
            n += 1
            while A[i] % p == 0:
                A[i] //= p
            if n > 1:
                print('setwise coprime')
                exit()
s = set()
for a in A:
    if a == 1:
        continue
    elif a in s:
        print('setwise coprime')
        exit()
    else:
        s.add(a)
print('pairwise coprime')