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:
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000

# 素数列挙
def primeNumList(n):
    d = [d for d in range(0, n+1)]
    if n < 2:
        return [[],d]
    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
            d[j] = i
    return [[i for i in range(n + 1) if is_prime[i]], d]

def main():
    # ------ 入力 ------#
    n = int(input())    # 数字
    aList = list(map(int, input().split()))     # スペース区切り連続数字

    # ------ 処理 ------#
    amax = max(aList)
    pl = primeNumList(amax)
    countList = [0] * (amax+1)

    if pl[0] != []:
        for a in aList:
            at = a
            sl = []
            while at != 1:
                s = pl[1][at]
                sl.append(s)
                at = int(at / s)
            sl2 = list(set(sl))
            for s in sl2:
                countList[s] += 1
        m = max(countList)
    else:
        m = 0

    # ------ 出力 ------#
    if m == len(aList):
        print("not coprime")
    elif m >= 2:
        print("setwise coprime")
    else:
        print("pairwise coprime")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000

# 素数列挙
def primeNumList(n):
    if n < 2:
        return []
    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())    # 数字
    aList = list(map(int, input().split()))     # スペース区切り連続数字

    # ------ 処理 ------#
    amax = max(aList)
    pl = primeNumList(amax)
    countList = [0] * len(pl)

    if pl != []:
        for a in aList:
            for i in range(len(pl)):
                if a % pl[i] == 0:
                    countList[i] += 1
        m = max(countList)
    else:
        m = 0

    # ------ 出力 ------#
    if m == len(aList):
        print("not coprime")
    elif m >= 2:
        print("setwise coprime")
    else:
        print("pairwise coprime")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#                               #
    # author : samars_diary #
    # 13-09-2020 │ 11:54:36 #
#                               #

import sys, os.path, math

#if(os.path.exists('input.txt')):
    #sys.stdin = open('input.txt',"r")
    #sys.stdout = open('output.txt',"w")

sys.setrecursionlimit(10 ** 5)

def mod(): return 10**9+7
def i(): return sys.stdin.readline().strip()
def ii(): return int(sys.stdin.readline())
def li(): return list(sys.stdin.readline().strip())
def mii(): return map(int, sys.stdin.readline().split())
def lii(): return list(map(int, sys.stdin.readline().strip().split()))

#print=sys.stdout.write

def solve():
    a=ii();b=lii();c=[];d=b[0]
    for i in range(a-1):
        for j in range(i+1, a):
            c.append(math.gcd(b[i],b[j]))
    for i in range(1, a):
        d=math.gcd(d, b[i])
    if len(set(c))==1 and c[0]==1:
        print('pairwise coprime')
    elif d==1:
        print('setwise coprime')
    else:
        print('not coprime')
solve()

Submission status: Time Limit Exceeded

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

l = lst[0]
g = lst[0]
pair_coprime = True
set_coprime = False
for i in range(1,n):
  if set_coprime == False:
    g = math.gcd(g,lst[i])
    if g == 1:
      set_coprime = True
      
  if pair_coprime == True:
    g_l = math.gcd(l,lst[i])
    if g_l == 1:
      l = l*lst[i]//g_l
    else:
      pair_coprime = False
    
if set_coprime == False:
  print('not coprime')
  
elif pair_coprime == False:
  print('setwise coprime')
else:
  print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
a = []

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

def prime_factorize(n):
  global a
  tmp = []
  while n % 2 == 0:
    if 2 not in a:
      tmp.append(2)
      n //= 2
    else:
      return False
  f = 3
  while f * f <= n:
    if n % f == 0:
      if f not in a:
        tmp.append(f)
        n //= f
      else:
        return False
    else:
      f += 2
  if n != 1:
    if n not in a:
      tmp.append(n)
    else:
      return False
  a = list(set(a+tmp))
  return True

flag = True
for i in range(N):
  ans = prime_factorize(A[i])
  if not ans:
    flag = False
    break
if flag:
  print('pairwise coprime')
elif gcd_list(A) == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
"""E."""

import math
import sys
from typing import List


def input() -> str:  # noqa: A001
    """Input."""
    return sys.stdin.readline()[:-1]


RESULT_A = 'pairwise coprime'
RESULT_B = 'setwise coprime'
RESULT_C = 'not coprime'

n = int(input())

a_list = list(map(int, input().split(' ')))


def get_all_gcd(l: List[int]) -> List[int]:
    result = []
    for i, v1 in enumerate(l[:-1]):
        for v2 in l[i + 1:]:
            result.append(math.gcd(v1, v2))
    return result


gcds = get_all_gcd(a_list)

if [1] * len(gcds) == gcds:
    print(RESULT_A)
    exit(0)

if [1] * len(gcds) == get_all_gcd(gcds):
    print(RESULT_B)
    exit(0)

print(RESULT_C)

Submission status: Time Limit Exceeded

Solution code:
import math
# エラトステネスの古いで高速化してるけど、O(AloglolgA + NlogA)なので、
# 普通に計算してもO(NlogA)で計算できいるので門d内ないのでは？

# sエラトステネスの篩は頭の中に出てきたけど、一定の値までの素数を列挙するという問題だったので、活用できないと思ってしまsった。

N = int(input())


def retrive_prime(x):
    i = 2
    res = []
    tmp = x
    while i**2 <= x:
        if tmp % i == 0:
            count = 0
            while tmp % i == 0:
                tmp //= i
                count += 1
            res.append([i, count])
        i += 1
    if tmp != 1:
        res.append([tmp, 1])
    return res


B = [int(x) for x in input().split()]
A = [retrive_prime(x) for x in B]
ifPairwise = True
ifSetwier = True
data = [0 for _ in range(10**6+1)]
pair = math.gcd(B[0], B[1])
for i in range(N-1):
    a = A[i]
    pair = math.gcd(pair, B[i])
    for x in a:
        if data[x[0]-1] == 1:
            ifPairwise = False
        else:
            data[x[0]-1] = 1
pair = math.gcd(pair, B[-1])
for a in A[-1]:
    if data[a[0]-1] == 1:
        ifPairwise = False
    else:
        data[a[0]-1] = 1

if not pair == 1:
    ifSetwier = False

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

Submission status: Time Limit Exceeded

Solution code:
import math

memo_dic = dict()

def is_pairwise(li) :
    for i in range(len(li)) :
        for k in range(i+1,len(li)) :
            res = math.gcd(li[i],li[k])
            key = str(li[i]) + "_" + str(li[k])
            memo_dic[key] = res
            if (res != 1) :
                return False
    return True

def is_setwise(li) :
    a = 0
    key = str(li[0]) + "_" + str(li[1])
    if (key in memo_dic) :
        a = memo_dic[key]
    else :
        a = math.gcd(li[0],li[1])

    for i in range(2,len(li)) :
        a = math.gcd(a,li[i])
        if (a == 1) :
            break
    
    if (a == 1) :
        return True
    else :
        return False


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

    result = is_pairwise(a_list)
    if(result) :
        print("pairwise coprime")
        return
    
    result = is_setwise(a_list)
    if (result) :
        print("setwise coprime")
    else :
        print("not coprime")


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
A=list(map(int,input().split()))
flag=0
if np.gcd.reduce(A)!=1:
  flag=1
  print("not coprime")
if flag==0:
  flag1=0
  for i in range (N):
    for j in range (N):
      if i!=j and np.gcd(A[i],A[j])!=1:
        flag1=1
      if flag1:
        break
    if flag1:
      break
if flag==0 and flag1==0:
  print("pairwise coprime")
elif flag==0:
  print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:

# A以下の数がN個与えられる。全て素因数分解せよ。
class SpeedPrime:
    # a以下の各数の最小の素因数を記録
    def __init__(self, a):
        self.d = [i for i in range(a+1)]

        i=2
        while i*i<=a:
            if self.d[i]==i:
                j=i*i
                while j<=a:
                    if self.d[j]==j:
                        self.d[j]=i
                    j+=i
            i+=1

    # nを高速素因数分解
    def fac(self, n):
        ret = dict()
        while n!=1:
            prime=self.d[n]
            if prime in ret:
                ret[prime]+=1
            else:
                ret[prime]=1
            n=n//prime
        return ret

import math
from functools import reduce
def gcd(numbers):
    return reduce(math.gcd, numbers)

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

sp=SpeedPrime(max(a))

d=set()
pc=True
for i in a:
    prime=sp.fac(i)
    for k in prime.keys():
        if k in d:
            pc=False
            break
        else:
            d.add(k)

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

g=gcd(a)
if g==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from collections import defaultdict
import sys
N = int(input())
a_ls = list(map(int, input().split()))
now_gcd = a_ls[0]
all_one = True
if a_ls[0] != 1:
    all_one = False
for i in range(1,N):
    now_gcd = gcd(a_ls[i],now_gcd)
    if a_ls[i] != 1:
        all_one = False
if now_gcd != 1:
    print('not coprime')
    sys.exit()
if all_one:
    print('pairwise coprime')
    sys.exit()

def factorization(n):
    '''
    [base,power]のリストを返す
    '''
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 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

prime_times = defaultdict(int)
for a in a_ls:
    arr = factorization(a)
    for base,p in arr:
        prime_times[base] += 1

res = 'pairwise coprime'
#prime_times = dict(prime_times)
for base,times in prime_times.items():
    if base != 1 and times > 1:
        res = 'setwise coprime'
        break
print(res)

Submission status: Time Limit Exceeded

Solution code:
# ABC177E

def GCD(m, n):
    while n != 0:
        m, n = n, m % n
    return m

def f(a):
    n = len(a)
    pairwise_coprime = True
    for i in range(n - 1):
        for j in range(i + 1, n):
            if GCD(a[i], a[j]) != 1:
                pairwise_coprime = False
                break
        if pairwise_coprime == False:
            break
    gcd = a[0]
    for i in range(1, n):
        gcd = GCD(gcd, a[i])
    if pairwise_coprime == False and gcd == 1:
        return 'setwise coprime'
    elif pairwise_coprime:
        return 'pairwise coprime'
    else:
        return 'not coprime'

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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
n = int(input())
a = list(map(int, input().split()))
max_a = max(a)
cnt_a = [0] * (max_a + 1)
for ai in a:
  cnt_a[ai] += 1
ans = 'pairwise'
for i in range(2, max_a + 1):
  cnt = 0
  for j in range(i, max_a + 1, i):
    cnt += cnt_a[j]
  if cnt > 1:
    ans = 'setwise'
g = 0
for ai in a:
  g = gcd(g, ai)

if ans == 'pairwise':
  print(ans, 'coprime')
elif ans == 'setwise' and g == 1:
  print(ans, 'coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

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


# number_to_prime[i]: i の最小の素因数, iが素数ならば0
number_to_prime = [0] * (10**6 + 1)

# preprocess
for i in range(2, 10**6+1):
    if not number_to_prime[i]:
        j = 2
        while j*i <= 10**6:
            number_to_prime[j*i] = i
            j += 1


def is_pairwise():
    used_primes = set()
    pairwise_flag = 1
    for a in A:
        if a == 1:
            continue
        curr_primes = set()
        while number_to_prime[a]:
            prime = number_to_prime[a]
            curr_primes.add(prime)
            a //= prime
        if used_primes & (curr_primes | set([a])):
            pairwise_flag = 0
            break
        else:
            used_primes = used_primes | (curr_primes | set([a]))
    return pairwise_flag

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pairwise():
    print("pairwise coprime")
elif is_setwise(*A):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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


# number_to_prime[i]: i の最小の素因数, iが素数ならば0
number_to_prime = [0] * (10**6 + 1)

# preprocess
for i in range(2, 10**6+1):
    if not number_to_prime[i]:
        j = 1
        while j*i <= 10**6:
            number_to_prime[j*i] = i
            j += 1


def is_pairwise():
    used_primes = set()
    pairwise_flag = 1
    for a in A:
        curr_primes = set()
        while a > 1:
            prime = number_to_prime[a]
            curr_primes.add(prime)
            a //= prime
        if used_primes & curr_primes:
            pairwise_flag = 0
            break
        else:
            used_primes = used_primes | curr_primes
    return pairwise_flag

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pairwise():
    print("pairwise coprime")
elif is_setwise(*A):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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


# number_to_prime[i]: i の最小の素因数, iが素数ならば0
number_to_prime = [0] * (10**6 + 1)

# preprocess
for i in range(2, 10**6+1):
    if not number_to_prime[i]:
        j = 1
        while j*i <= 10**6:
            number_to_prime[j*i] = i
            j += 1


def is_pairwise():
    used_primes = set()
    pairwise_flag = 1
    for a in A:
        if a == 1:
            continue
        curr_primes = set()
        while number_to_prime[a] > 1:
            prime = number_to_prime[a]
            curr_primes.add(prime)
            a //= prime
        if used_primes & curr_primes:
            pairwise_flag = 0
            break
        else:
            used_primes = used_primes | curr_primes
    return pairwise_flag

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pairwise():
    print("pairwise coprime")
elif is_setwise(*A):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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


# number_to_prime[i]: i の最小の素因数, iが素数ならば0
number_to_prime = [0] * (10**6 + 1)

# preprocess
for i in range(2, 10**6+1):
    if not number_to_prime[i]:
        j = 2
        while j*i <= 10**6:
            number_to_prime[j*i] = i
            j += 1


def is_pairwise():
    used_primes = set()
    pairwise_flag = 1
    for a in A:
        if a == 1:
            continue
        curr_primes = set()
        while number_to_prime[a]:
            prime = number_to_prime[a]
            curr_primes.add(prime)
            a //= prime
        curr_primes.add(a)
        if used_primes & curr_primes:
            pairwise_flag = 0
            break
        else:
            used_primes = used_primes | curr_primes
    return pairwise_flag

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pairwise():
    print("pairwise coprime")
elif is_setwise(*A):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd


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


n=int(input())
A=list(map(int,input().split()))
prime=[True for _ in range(10**6+1)]

flag=0
for i in A:
    for j in prime_factorize(i):
        if prime[j]:
            for k in range(j,10**6+1,j):
                prime[k]=False
        else:
            flag=1
            break
if flag==0:print("pairwise coprime");exit()
line=[0]*n
line[0]=A[0]
for i in range(1,n):
    line[i]=gcd(line[i-1],A[i])
if line[-1]==1:print("setwise coprime");exit()
print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

A=list(map(int,input().split()))
A_max=max(A)
D=[0] *(A_max+1) #xを割り切る最小の素数を格納

import math
from functools import reduce

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

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

for i in range(2,A_max+1):
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            D[i]=j
            break
    if D[i]==0:
        D[i]=i

def gcdlist(n):
    a=n
    l=[]
    if D[a] == a:
        return [a]
    else:
        while a>1:
            l.append(D[a])
            a //=D[a] 
            if a==D[a]:
                l.append(a)
                break
        return l

pairwise=True
gcds=[]
for i in range(N):
    l=gcdlist(A[i])
    if i==0:
        for j in l:
            gcds.append(j)
        continue
    for j in l:
        if j not in gcds:
            continue
        else:
            pairwise=False
    if pairwise==True:
        for j in l:
            gcds.append(j)
    else:
        break
if pairwise==True:
    print("pairwise coprime")
else:
    if gcd_list(A) == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            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 primeFactorization(n, primes):
    ans = []
    temp = n
    for p in primes:
        while temp%p == 0:
            ans.append(p)
            temp //= p
    if temp > 1:
        ans.append(temp)
    return collections.Counter(ans)

def resolve():
    N = I()
    A = LI()

    # pairwiseについて、Aを走査して今までに出てきた素因数を記録すればわかる
    primes = sieve(max(A))
    factor = set()
    is_pc = True
    for i in A:
        for j in primes:
            if i % j == 0:
                if j in factor:
                    is_pc = False
                    break
                else:
                    factor.add(j)
        if not is_pc:
            break
    
    is_sc = False
    if not is_pc:
        gcd = A[0]
        for i in A[1:]:
            gcd = math.gcd(i, gcd)
        if gcd == 1:
            is_sc = True

    if is_pc:
        print('pairwise coprime')
    elif is_sc:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            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 primeFactorization(n, primes):
    ans = []
    temp = n
    for p in primes:
        while temp%p == 0:
            ans.append(p)
            temp //= p
    if temp > 1:
        ans.append(temp)
    return collections.Counter(ans)

def resolve():
    N = I()
    A = LI()

    # pairwiseについて、Aを走査して今までに出てきた素因数を記録すればわかる
    primes = sieve(max(A))
    factor = set()
    is_pc = True
    for i in A:
        pf = primeFactorization(i, primes)
        for j in pf.keys():
            if j in factor:
                is_pc = False
                break
            factor.add(j)
        if not is_pc:
            break
    
    is_sc = False
    if not is_pc:
        gcd = A[0]
        for i in A[1:]:
            gcd = math.gcd(i, gcd)
        if gcd == 1:
            is_sc = True

    if is_pc:
        print('pairwise coprime')
    elif is_sc:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd   # gcd(6, 4) -> 2
from functools import reduce


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


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


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

a = []

for i in range(N):
    if A[i] != 1:
        a.extend(factorization(A[i]))

if len(set(a)) == len(a):
    print('pairwise coprime')
    exit()

if gcd_list(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()))
divide_minimam_prime = [i for i in range(max(a) + 1)]
is_prime = [True for i in range(max(a) + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(2,int(max(a)**0.5) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= max(a):
            is_prime[k] = False
            if divide_minimam_prime[k] == k:
                divide_minimam_prime[k] = div
            k += div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(divide_minimam_prime[k])
        div = divide_minimam_prime[k]
        while k % div == 0 and k > 1:
            k = k // div
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_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()))
divide_minimam_prime = [i for i in range(max(a) + 1)]
is_prime = [True for i in range(max(a) + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(2,int(max(a)**0.5) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= max(a):
            is_prime[k] = False
            if divide_minimam_prime[k] == k:
                divide_minimam_prime[k] = div
            k += div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(divide_minimam_prime[k])
        div = divide_minimam_prime[k]
        while k % divide_minimam_prime[k] == 0 and k > 1:
            k = k // div
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_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()))
divide_minimam_prime = [i for i in range(max(a) + 1)]
is_prime = [True for i in range(max(a) + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(2,int(max(a)**0.5) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= max(a):
            is_prime[k] = False
            if divide_minimam_prime[k] == k:
                divide_minimam_prime[k] = div
            k += div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(k)
        while k % divide_minimam_prime[k] == 0:
            k = k // divide_minimam_prime[k]
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_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()))
divide_minimam_prime = [i for i in range(max(a) + 1)]
is_prime = [True for i in range(max(a) + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(2,int(max(a)**0.5) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= max(a):
            is_prime[k] = False
            if divide_minimam_prime[k] == k:
                divide_minimam_prime[k] = div
            k += div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    divnum_of_a = set()
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            divnum_of_a.add(divide_minimam_prime[k])
        k = k // divide_minimam_prime[k]
    use_divnum = use_divnum or divnum_of_a
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_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()))
divide_minimam_prime = [0 for i in range(max(a) + 1)]
is_prime = [True for i in range(max(a) + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(max(a) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= max(a):
            is_prime[k] = False
            if divide_minimam_prime[k] == 0:
                divide_minimam_prime[k] = div
            k += div
    else:
        if divide_minimam_prime[div] == 0:
            divide_minimam_prime[div] = div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    divnum_of_a = set()
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            divnum_of_a.add(divide_minimam_prime[k])
        k = k // divide_minimam_prime[k]
    use_divnum = use_divnum or divnum_of_a
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    
    def factrize(x):
        f = set()
        for i in range(2,int(x**(1/2))+1):
            if x%i == 0:
                f.add(i)
                while x%i == 0:
                    x //= i
        if x != 1:
            f.add(x)
        return f
    
    base = factrize(a[0])
    union = base
    intersection = base
    flag = True
    for num in a[1:]:
        base = factrize(num)
        if len(union) + len(base) != len(union|base):
            flag = False
        intersection = intersection & base
        union = union | base
    
    if flag:
        print("pairwise coprime")
    else:
        if intersection:
            print("not coprime")
        else:
            print("setwise coprime")

if __name__ == "__main__":
    main()