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:
# region header
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
# endregion
# region input function


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])

# endregion


class osa_k():
    def __init__(self, n):
        """高速素因数分解

        Args:
            n (int): n以下全ての値について素因数分解できるようにする
        """
        self.n = n
        self.minFactor = list(range(0, n + 1))
        self.prime = []

    def factorize(self, i):
        if not self.prime:
            self.get_sieve_of_eratosthenes()
        factor = []
        while i != 1:
            p = self.minFactor[i]
            factor.append(p)
            i //= p
        return factor

    def get_sieve_of_eratosthenes(self):
        """エラトステネスの篩

        Raises:
            TypeError: 型エラー
            ValueError: n>=2限定

        Returns:
            list(int): 素数の配列
        """
        if not isinstance(self.n, int):
            raise TypeError('n is int type.')
        if self.n < 2:
            raise ValueError('n is more than 2')
        prime = []
        limit = math.sqrt(self.n)
        data = [i + 1 for i in range(1, self.n)]
        while True:
            p = data[0]
            self.minFactor[p] = p
            if limit <= p:
                self.prime = prime + data
                return self.prime
            prime.append(p)
            new_data = []
            for i in data:
                if i % p != 0:
                    new_data.append(i)
                elif self.minFactor[i] == i:
                    self.minFactor[i] = p
            data = copy.deepcopy(new_data)


n = inp()
a = inpl()
factorizer = osa_k(10**6)
tmp = collections.defaultdict(int)
for i in a:
    p = set(factorizer.factorize(i))
    for j in p:
        tmp[j] += 1
max_val = max(tmp.values())
if max_val == 1:
    print("pairwise coprime")
elif max_val == n:
    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()))
    lcm = [0]*n
    lcm[n-1] = a[n-1]
    for i in range(n-2,0,-1):
        # print(f"{i} , {a[i]} , {lcm[i+1]}")
        lcm[i] = (a[i]*lcm[i+1])//(math.gcd(a[i],lcm[i+1]))
    totgcd = a[0]
    for i in range(1,n):
        totgcd = math.gcd(totgcd,a[i])
    bol = 1
    # for i in range(1,n):
    #     print(f"{lcm[i]}")
    # print(f" yo {(4*5)//math.gcd(4,5)}")
    for i in range(0,n-1):
        x = math.gcd(a[i],lcm[i+1])
        if x != 1:
            bol = 0
            break
    if bol==1:
        print("pairwise coprime")
    elif totgcd==1:
        print("setwise coprime")
    else:
        print("not coprime")
main()

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
lcm = [0]*n
lcm[n-1] = a[n-1]
for i in range(n-2,0,-1):
    # print(f"{i} , {a[i]} , {lcm[i+1]}")
    lcm[i] = (a[i]*lcm[i+1])//(math.gcd(a[i],lcm[i+1]))
totgcd = a[0]
for i in range(1,n):
    totgcd = math.gcd(totgcd,a[i])
bol = 1
# for i in range(1,n):
#     print(f"{lcm[i]}")
# print(f" yo {(4*5)//math.gcd(4,5)}")
for i in range(0,n-1):
    x = math.gcd(a[i],lcm[i+1])
    if x != 1:
        bol = 0
        break
if bol==1:
    print("pairwise coprime")
elif totgcd==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().split()]

m = max(a)
primes = list(range(m+1))
primes[1] = 0
for i in range(2, m+1, 2): primes[i] = 2

for i in range(3, int(m ** 0.5)+1):
    for j in range(i, m+1, i):
        if primes[j] > i: primes[j] = i

b = [0] * (m + 1)
def factorization(n):
    temp = n
    lst = []
    while temp != 1:
        lst.append(primes[temp])
        temp = temp // primes[temp]

    aset = set(lst)
    for i in aset:
        b[i] += 1

for aa in a:
    factorization(aa)
maxb = max(b)
if maxb <= 1: print('pairwise coprime')
elif maxb < n: print('setwise coprime')
else: print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
arr = [0]*(max(a)+1)
flag = True
for i in a:
  arr[i] += 1
  
for i in range(2,max(a)+1):
  ans = 0
  for j in range(i,max(a)+1,i):
    ans += arr[j]
  if ans>1 and flag == True:
    flag = False
    break
  elif flag == False:
    break
    
g = a[0]  
for i in range(1,n):
  g = math.gcd(g,a[i])
  
if flag:
  print("pairwise coprime")
elif g == 1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
arr = [0]*(max(a)+1)
flag = True
for i in a:
  arr[i] += 1
  
for i in range(2,max(a)+1):
  ans = 0
  for j in range(i,max(a)+1,i):
    ans += arr[j]
  if ans>1:
    flag = False
  
g = a[0]  
for i in range(1,n):
  g = math.gcd(g,a[i])
  
if flag:
  print("pairwise coprime")
elif g == 1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
MAX_A = 10**6

sieve = [[] for _ in range(MAX_A+1)]
# sieve[i] = True if i is prime
# sieve[i] = prime factors of i

for f in range(2, MAX_A + 1):
  if not sieve[f]:
    c = f
    while c <= MAX_A:
      sieve[c].append(f)
      c += f

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

cnt = defaultdict(int)
for a in A:
  for s in sieve[a]:
    cnt[s] += 1

def is_pairwise_coprime():
  return all(v == 1 for v in cnt.values())

def is_setwise_coprime():
  return all(v < N for v in cnt.values())

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().split()]

m = max(a)
primes = list(range(m+1))
primes[1] = 0
for i in range(2, m+1, 2): primes[i] = 2

for i in range(3, int(m ** 0.5)+1):
    for j in range(i, m+1, i):
        if primes[j] > i: primes[j] = i

b = [0] * (m + 1)
def factorization(n):
    aset = set()
    temp = n
    while temp != 1:
        aset.add(primes[temp])
        temp = temp // primes[temp]
    for i in aset:
        b[i] += 1

for aa in a:
    factorization(aa)
maxb = max(b)
if maxb <= 1: print('pairwise coprime')
elif maxb < n: print('setwise coprime')
else: print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]

m = max(a)
primes = [1] * (m + 1)
primes[0], primes[1] = 0, 0
if m > 1: primes[2] = 2
else: primes[1] = 0

for i in range(2, int(m ** 0.5)+1):
    if primes[i] == 0: continue
    for j in range(i, m+1, i):
        if primes[j] == 1:
            primes[j] = i

for i in range(m+1):
    if primes[i] == 1: primes[i] = i

b = [0] * (m + 1)
def factorization(n):
    aset = set()
    temp = n
    while temp != 1:
        aset.add(primes[temp])
        temp = temp // primes[temp]
    for i in aset:
        b[i] += 1

for aa in a:
    factorization(aa)
maxb = max(b)
if maxb <= 1: print('pairwise coprime')
elif maxb < n: print('setwise coprime')
else: print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    if a < b:
        a, b = b, a
    return b if a % b == 0 else gcd(b, a%b)

def solve(n, a):
    ok = True
    p = a[0]
    for i in range(1, n):
        q = gcd(p, a[i])
        if q > 1:
            ok = False
            break
        p = p * a[i] // q
    if ok:
        return "pairwise coprime"
    p = a[0]
    for i in range(1, n):
       p = gcd(p, a[i])
    return "setwise coprime" if p == 1 else "not coprime"

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

Submission status: Time Limit Exceeded

Solution code:
import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

p=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
   31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
   73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
   127, 131, 137, 139, 149, 151, 157, 163, 167,
   173, 179, 181, 191, 193, 197, 199, 211, 223,
   227, 229, 233, 239, 241, 251, 257, 263, 269,
   271, 277, 281, 283, 293, 307, 311, 313, 317,
   331, 337, 347, 349, 353, 359, 367, 373, 379,
   383, 389, 397, 401, 409, 419, 421, 431, 433, 
   439, 443, 449, 457, 461, 463, 467, 479, 487,
   491, 499, 503, 509, 521, 523, 541, 547, 557,
   563, 569, 571, 577, 587, 593, 599, 601, 607,
   613, 617, 619, 631, 641, 643, 647, 653, 659,
   661, 673, 677, 683, 691, 701, 709, 719, 727,
   733, 739, 743, 751, 757, 761, 769, 773, 787,
   797, 809, 811, 821, 823, 827, 829, 839, 853,
   857, 859, 863, 877, 881, 883, 887, 907, 911,
   919, 929, 937, 941, 947, 953, 967, 971, 977,
   983, 991, 997,1009]

import math

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
#    while search_list[0] <= math.sqrt(number):
    while search_list[0]**2 <= number:
      #search_listの先頭の値が√nの値を超えたら終了
      #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        search_list = [num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list

#p=get_primenumber(78498)
#p=get_primenumber(1010)
p=get_primenumber(20000)

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp.sort()
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()


for pp in p:
    lap=0
    for ai in ap:
        if  ai%pp==0:
            lap+=1
        if lap>=2:
            print("setwise coprime")
            sys.exit()
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
x=[-1]*(10**6+5)
x[0]=0
x[1]=1
i=2
while i<=10**6+1:
    j=2*i
    if x[i]==-1:
        x[i]=i
        while j<=10**6+1:
            if x[j]==-1:x[j]=i
            j+=i
    i+=1

z=[0]*(10**6+5)

g=gcd(a[0],a[0])
for i in range(n):
    g=gcd(g,a[i])
if g!=1:
    print("not coprime")
else:
    f=0
    for i in range(n):
        p=1
        while a[i]>=2:
            if p==x[a[i]]:
                a[i]=a[i]//p
                continue
            else:
                p=x[a[i]]
                z[p]+=1
                a[i]=a[i]//p

    for i in range(10**6+1):
        if z[i]>=2:
            f=1
    print("pairwise coprime" if f==0 else "setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
n=int(input())
a=list(map(int,input().split()))
x=[-1]*(10**6+5)
x[0]=0
x[1]=1
i=2
while i<=10**6+1:
    j=2*i
    if x[i]==-1:
        x[i]=i
        while j<=10**6+1:
            if x[j]==-1:x[j]=i
            j+=i
    i+=1

z=[0]*(10**6+5)

g=gcd(a[0],a[0])
for i in range(n):
    g=gcd(g,a[i])
if g!=1:
    print("not coprime")
else:
    f=0
    for i in range(n):
        p=1
        while a[i]>=2:
            if p==x[a[i]]:
                a[i]=a[i]//p
                continue
            else:
                p=x[a[i]]
                z[p]+=1
                a[i]=a[i]//p

    for i in range(10**6+1):
        if z[i]>=2:
            f=1
    print("pairwise coprime" if f==0 else "setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
n=int(input())
a=list(map(int,input().split()))
x=[-1]*(10**6+5)
x[0]=0
x[1]=1
i=2
while i<=10**6+1:
    j=2*i
    if x[i]==-1:
        x[i]=i
        while j<=10**6+1:
            x[j]=i
            j+=i
    i+=1

z=[0]*(10**6+5)

g=gcd(a[0],a[0])
for i in range(n):
    g=gcd(g,a[i])
if g!=1:
    print("not coprime")
else:
    f=0
    for i in range(n):
        p=1
        while a[i]>=2:
            if p==x[a[i]]:
                a[i]=a[i]//p
                continue
            else:
                p=x[a[i]]
                z[p]+=1
                a[i]=a[i]//p

    for i in range(10**6+1):
        if z[i]>=2:
            f=1
    print("pairwise coprime" if f==0 else "setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
n=int(input())
a=list(map(int,input().split()))
x=[-1]*(10**6+5)
x[0]=0
x[1]=1
i=2
while i<=10**6+1:
    j=2*i
    if x[i]==-1:
        x[i]=i
        while j<=10**6+1:
            x[j]=i
            j+=i
    i+=1

z=[0]*(10**6+5)
def d(y):
    t=[]
    while y>=2:
        p=x[y]
        t.append(p)
        y=y//p
    t=list(set(t))
    for i in range(len(t)):
        z[t[i]]+=1
    return
g=gcd(a[0],a[0])
for i in range(n):
    g=gcd(g,a[i])
if g!=1:
    print("not coprime")
else:
    f=0
    for i in range(n):
        d(a[i])
    for i in range(10**6+1):
        if z[i]>=2:
            f=1
    print("pairwise coprime" if f==0 else "setwise coprime")

Submission status: Time Limit Exceeded

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

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

    return arr

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

nums = [0]*(max(A)+1)

for a in A:
    for x in prime_factors(a):
        nums[x] += 1

y = max(nums)

if y < 2:
    print('pairwise coprime')
elif y < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:

import sys

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

if maxA==1:
    print('pairwise coprime')
    sys.exit()
    
def sieve_of_eratosthenes(n): #エラトステネスのふるい
    if n==2:
        return [2]
    else:
        candidate = list(range(2, n+1)) #候補
        prime = []
        limit = n**0.5 + 1 #+1がないと平方数を素数にしてしまう
    
        while True:
            p = candidate[0] 
            if limit <= p:
                prime.extend(candidate) #この時点での残っているのは素数
                break
            prime.append(p) #pを素数リストに登録
    
            candidate = [i for i in candidate if i % p != 0]
    
            # i = 0
            # while True:
                # if i >= len(candidate): #iはcandidateの長さ分
                    # break
                # elif candidate[i] % p == 0: #余りがゼロなら
                    # candidate.pop(i) #素数ではないのでpop(取り除く)する
                # i += 1
    
        return prime





prime = sieve_of_eratosthenes(maxA)

X=[0]*(maxA+1)
for i in range(N):
    X[A[i]]+=1

check=0
for i in prime:
    count=0
    for j in range(1,int(maxA/i)+1):
        count+=X[j*i]
    if count==N:
        print('not coprime')
        sys.exit()
    elif count>1:
        check=1
        
if check==1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
from functools import lru_cache
sys.setrecursionlimit(10000000)

N = int(input())
A_list = [int(e) for e in input().split()]

#pairwise coprime …… 素因数分解したとき、共通のものが1個もない
#setwise coprime　…… 素因数分解したとき、全てで共通のものがない

def main():
    #試し割の結果の辞書を求める
    def make_trial_division_dict(n):
        #import math
        td_dict = dict()
        for i in range(2,n+1):
            if i not in td_dict:
                td_dict[i] = i
                for j in range(2,1+n//i):
                    if j*i not in td_dict:
                        td_dict[j*i] = i
        td_dict[1] = 1
        return td_dict

    #試し割結果の辞書を利用して素因数分解する
    @lru_cache(maxsize=None)
    def high_speed_prime_factorization(n):
        pf_list = list()
        pf_list.append(td_dict[n])
        
        if n//td_dict[n] == 1:
            if n!=1:
                pf_list.append(1)
            return pf_list
        else:
            pf_list.extend(high_speed_prime_factorization(n//td_dict[n]))
            return pf_list
        
    td_dict = make_trial_division_dict(max(A_list))

    all_pf = set()    #含まれる素因数がすべて集約される
    common_pf = set() #共通する素因数が集約される
    all_pf |= set(high_speed_prime_factorization(A_list[0]))
    common_pf |= set(high_speed_prime_factorization(A_list[0]))
    is_pairwise = True

    #print(A_list[0],set(high_speed_prime_factorization(A_list[0])))

    for i in range(1,len(A_list)):
        A_pf = set(high_speed_prime_factorization(A_list[i]))
        common_pf &= A_pf 
        
        #print(A_list[i],set(high_speed_prime_factorization(A_list[i])))
        
        if is_pairwise and len(all_pf&A_pf)!=1: #1は共通で含まれる
            is_pairwise = False
        else:
            all_pf |= A_pf

    if is_pairwise:
        print("pairwise coprime")
    elif len(common_pf) == 1: #1は共通で含まれる
        print("setwise coprime")
    else:
        print("not coprime")

main()

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
from functools import lru_cache
sys.setrecursionlimit(10000000)

N = int(input())
A_list = [int(e) for e in input().split()]

#pairwise coprime …… 素因数分解したとき、共通のものが1個もない
#setwise coprime　…… 素因数分解したとき、全てで共通のものがない

#試し割の結果の辞書を求める
def make_trial_division_dict(n):
    #import math
    td_dict = dict()
    for i in range(2,n+1):
        if i not in td_dict:
            td_dict[i] = i
            for j in range(2,1+n//i):
                if j*i not in td_dict:
                    td_dict[j*i] = i
    td_dict[1] = 1
    return td_dict

#試し割結果の辞書を利用して素因数分解する
@lru_cache(maxsize=None)
def high_speed_prime_factorization(n):
    pf_list = list()
    pf_list.append(td_dict[n])
    
    if n//td_dict[n] == 1:
        if n!=1:
            pf_list.append(1)
        return pf_list
    else:
        pf_list.extend(high_speed_prime_factorization(n//td_dict[n]))
        return pf_list

td_dict = make_trial_division_dict(max(A_list))

all_pf = set()    #含まれる素因数がすべて集約される
common_pf = set() #共通する素因数が集約される
all_pf |= set(high_speed_prime_factorization(A_list[0]))
common_pf |= set(high_speed_prime_factorization(A_list[0]))
is_pairwise = True

#print(A_list[0],set(high_speed_prime_factorization(A_list[0])))

for i in range(1,len(A_list)):
    A_pf = set(high_speed_prime_factorization(A_list[i]))
    common_pf &= A_pf 
    
    #print(A_list[i],set(high_speed_prime_factorization(A_list[i])))
    
    if is_pairwise and len(all_pf&A_pf)!=1: #1は共通で含まれる
        is_pairwise = False
    else:
        all_pf |= A_pf

if is_pairwise:
    print("pairwise coprime")
elif len(common_pf) == 1: #1は共通で含まれる
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
N=int(input())
A=list(map(int,input().split()))
maxA=max(A)

X=[0]*(maxA+1)
for i in range(N):
    X[A[i]]+=1

check=0    
for i in range(2,maxA+1):
    count=0
    for j in range(1,int(maxA/i)+1):
        count+=X[j*i]
    if count==N:
        print('not coprime')
        sys.exit()
    elif count>1:
        check=1
        
if check==1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

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

check=0
for i in range(2,sorted(A)[-2]):
    B=[]
    for j in range(N):
        B.append(A[j]%2)
    if B.count(0)==N:
        print('not coprime')
        sys.exit()
    elif B.count(0)>1:
        check=1
        
if check==1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
# import math
import itertools
# import functools
import operator

def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))

    max_a = max(A)
    temp = [0] * (max_a + 1)
    temp[1] = 1

    for i in range(2, max_a + 1):
        if temp[i]:
            continue

        j = i
        while j < max_a + 1:
            if not temp[j]:
                temp[j] = i
            j += i

    B = []
    for a in A:
        s = set()
        while a > 1:
            s.add(temp[a])
            a = a // temp[a]
        B.append(s)
    
    C = tuple(filter(lambda x: x > 1, itertools.chain.from_iterable(B)))
    D = frozenset(C)
    if len(C) == len(D):
        return 'pairwise coprime'

    # if functools.reduce(math.gcd, A) == 1:
    # v = tuple(itertools.accumulate(B, operator.and_))
    if not all(itertools.accumulate(B, operator.and_)):
        return 'setwise coprime'

    return 'not coprime'
    

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import math,sys

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))
#n = int(input())
#a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])

for e in a:
    asf = set(factrial(e))
    if judge & asf != set():
        print("setwise coprime")
        exit()
    #judge |= asf
    judge = judge | asf #too slow
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
# ρ法でとおるかためす。

# 参考1: https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
# 参考2: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
# 参考3: https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%A9%E3%83%BC%E3%83%89%E3%83%BB%E3%83%AD%E3%83%BC%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E6%B3%95


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def is_prime(n):
    "Miller Rabin primality test. 2 <= n <= 2 ** 64 is required"
    if n % 2 == 0:
        return n == 2
    d = n - 1
    r = (d & -d).bit_length() - 1
    d >>= r

    # witnesses をいい感じに決める。
    if n < 2152302898747:
        if n < 9080191:
            if n < 2047:
                witnesses = [2]
            else:
                witnesses = [31, 73]
        else:
            if n < 4759123141:
                witnesses = [2, 7, 61]
            else:
                witnesses = [2, 3, 5, 7, 11]
    else:
        if n < 341550071728321:
            if n < 3474749660383:
                witnesses = [2, 3, 5, 7, 11, 13]
            else:
                witnesses = [2, 3, 5, 7, 11, 13, 17]
        else:
            if n < 3825123056546413051:
                witnesses = [2, 3, 5, 7, 11, 13, 17, 19]
            else:
                witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
    # witnesses の決定終了

    for a in witnesses:
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x *= x
            x %= n
            if x == n - 1:
                break
        else:
            return False
    return True


def find_factor(n):
    "Find a non-trivial factor of n by using Pollard's rho algorithm."
    m = int(n ** 0.125) + 1
    c = 1
    while True:
        y = 1
        r = 1
        q = 1
        g = 1
        while g == 1:
            x = y
            for _ in range(r):
                y = (y * y + c) % n
            for k in range(0, r, m):
                ys = y
                for _ in range(m):
                    y = (y * y + c) % n
                    q = q * (x - y) % n
                g = gcd(q, n)
                if g != 1:
                    break
            else:  # 残りの k から r までをやる
                ys = y
                for _ in range(r-k):
                    y = (y * y + c) % n
                    q = q * (x - y) % n
                g = gcd(q, n)
            r *= 2

        if g == n:
            g = 1
            while g == 1:
                ys = (ys * ys + c) % n
                g = gcd(x - ys, n)

        if g == n:
            c += 1  # c を変えて続行。
        else:  # g は n の非自明な素因数。
            return g


def fac(n):
    "計算量は O(n ^ 1/4) 程度。"
    if n == 1:
        return []
    if is_prime(n):
        return [n]

    ret = []
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]:
        while n % p == 0:
            ret.append(p)
            n //= p
        if n == 1:
            return ret

    while n != 1 and not is_prime(n):
        f = find_factor(n)
        if is_prime(f):
            while n % f == 0:
                ret.append(f)
                n //= f
        elif is_prime(n // f):
            ret.append(n // f)
            n = f
        else:
            return sorted(ret + fac(f) + fac(n // f))

    if n == 1:
        return sorted(ret)
    else:
        ret.append(n)
        return sorted(ret)




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

divisible_by_prime = dict()
divisible_by_prime[1] = 1
for A in As:
    for p in set(fac(A)):
        if p not in divisible_by_prime:
            divisible_by_prime[p] = 1
        else:
            divisible_by_prime[p] += 1

ispair = True
isset = True
ans = max(v for v in divisible_by_prime.values())
if ans <= 1:
    print("pairwise coprime")
elif ans < N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
# ρ法でとおるかためす。

# 参考1: https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
# 参考2: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
# 参考3: https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%A9%E3%83%BC%E3%83%89%E3%83%BB%E3%83%AD%E3%83%BC%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E6%B3%95


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def is_prime(n):
    "Miller Rabin primality test. 2 <= n <= 2 ** 64 is required"
    if n % 2 == 0:
        return n == 2
    d = n - 1
    r = (d & -d).bit_length() - 1
    d >>= r

    # witnesses をいい感じに決める。
    if n < 2152302898747:
        if n < 9080191:
            if n < 2047:
                witnesses = [2]
            else:
                witnesses = [31, 73]
        else:
            if n < 4759123141:
                witnesses = [2, 7, 61]
            else:
                witnesses = [2, 3, 5, 7, 11]
    else:
        if n < 341550071728321:
            if n < 3474749660383:
                witnesses = [2, 3, 5, 7, 11, 13]
            else:
                witnesses = [2, 3, 5, 7, 11, 13, 17]
        else:
            if n < 3825123056546413051:
                witnesses = [2, 3, 5, 7, 11, 13, 17, 19]
            else:
                witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
    # witnesses の決定終了

    for a in witnesses:
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x *= x
            x %= n
            if x == n - 1:
                break
        else:
            return False
    return True


def find_factor(n):
    "Find a non-trivial factor of n by using Pollard's rho algorithm."
    m = int(n ** 0.125) + 1
    c = 1
    while True:
        y = 1
        r = 1
        q = 1
        g = 1
        while g == 1:
            x = y
            for _ in range(r):
                y = (y * y + c) % n
            for k in range(0, r, m):
                ys = y
                for _ in range(m):
                    y = (y * y + c) % n
                    q = q * (x - y) % n
                g = gcd(q, n)
                if g != 1:
                    break
            else:  # 残りの k から r までをやる
                ys = y
                for _ in range(r-k):
                    y = (y * y + c) % n
                    q = q * (x - y) % n
                g = gcd(q, n)
            r *= 2

        if g == n:
            g = 1
            while g == 1:
                ys = (ys * ys + c) % n
                g = gcd(x - ys, n)

        if g == n:
            c += 1  # c を変えて続行。
        else:  # g は n の非自明な素因数。
            return g


def fac(n):
    "計算量は O(n ^ 1/4) 程度。"
    if n == 1:
        return []
    if is_prime(n):
        return [n]

    ret = []
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]:
        while n % p == 0:
            ret.append(p)
            n //= p
        if n == 1:
            return ret

    while n != 1 and not is_prime(n):
        f = find_factor(n)
        if is_prime(f):
            while n % f == 0:
                ret.append(f)
                n //= f
        elif is_prime(n // f):
            ret.append(n // f)
            n = f
        else:
            return sorted(ret + fac(f) + fac(n // f))

    if n == 1:
        return sorted(ret)
    else:
        ret.append(n)
        return sorted(ret)


from collections import defaultdict

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

divisible_by_prime = defaultdict(int)
divisible_by_prime[1] = 1
for A in As:
    for p in set(fac(A)):
        divisible_by_prime[p] += 1

ispair = True
isset = True
ans = max(v for v in divisible_by_prime.values())
if ans <= 1:
    print("pairwise coprime")
elif ans < N:
    print("setwise coprime")
else:
    print("not coprime")