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: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

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

sys.setrecursionlimit(1000000)

class Eratosthenes:
    # https://cp-algorithms.com/algebra/prime-sieve-linear.html
    def __init__(self, n):
        primes, lp = [], [0] * (n + 1)
        for i in range(2, n + 1):
            if lp[i] == 0:
                primes.append(i)
                lp[i] = i

            for pj in primes:
                if pj > lp[i] or i * pj > n: break
                lp[i * pj] = pj
        self.primes, self.lp = primes, lp

    def is_prime(self, x): return self.lp[x] == x

    def factors(self, x):
        ret = []
        while x > 1:
            ret.append(self.lp[x])
            x //= self.lp[x]
        return ret


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

    era = Eratosthenes(1 + 10 ** 6)
    cumgcd = reduce(lambda x,y: math.gcd(x, y), A)
    s = set()
    for ai in A:
        for i in set(era.factors(ai)):
            if i in s:
                break
            s.add(i)
        else:
            continue
        break
    else:
        print("pairwise coprime")
        return

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd

"""
pairwise coprimeであるための条件は、全てのAに関して素因数に重複がないことである。
したがって、各Aに関して素因数分解を行う⇒各数の素因数の種類数をカウントし総和する。⇒全体の素因数の種類数をカウントし、先ほどの総和と比較する。
"""
N = int(input())
A = list(map(int,input().split()))
primes = []
def primeFinder(n):
    memo = [1]*(n+1)
    memo[0] = 0
    memo[1] = 0
    for i in range(2,n+1):
        if memo[i] == 1:
            primes.append(i)
            for j in range(i*2,n+1,i):
                memo[j] = 0
primeFinder(1000000)

primeMemo = set()
cnt = 0
for i in range(N):
    a = A[i]
    for p in primes:
        if p*p > a:
            break
        if a%p == 0:
            cnt += 1
            primeMemo.add(p)
        while a%p==0:
            a //= p
    if a != 1:
        cnt += 1
        primeMemo.add(a)

if cnt == len(primeMemo):
    print('pairwise coprime')
    exit()
g = A[0]
for i in range(1,N):
    g = gcd(g,A[i])
if g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce

N, *A = map(int, open(0).read().split())

t = [0] * (10 ** 6 + 1)
for a in A:
    t[a] += 1

for i in range(2, 10 ** 6 + 1):
    c = 0
    for j in range(i, 10 ** 6 + 1, i):
        c += t[j]
    if c > 1:
        break
else:
    print('pairwise coprime')
    exit()

if reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:


#素因数分解（10**6まで）
def soinsu_bunkai(m):
    pf=set()
    mm =m
    pri_num =[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]
    for i in pri_num:
        if i > mm:
            break
        while mm %i==0:
            pf.add(i)
            mm //=i
    if mm !=1:
        pf.add(mm)
    return pf

# 初期入力
import math
import sys
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
used =set()
pair_w =set()

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    ans ="pairwise coprime"
    for a in A:
        aa =soinsu_bunkai(a)
        if used & aa:
            print("setwise coprime")
            sys.exit() #共通要素があったらpair_wではない→set_w
        used |=aa

        
print(ans)

Submission status: Accepted

Solution code:
#高速素因数分解  osa_k法 
def osa_k(a):
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
    return tmp

    # 初期入力
import math
import sys
from bisect import bisect_left
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
used =set()

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    MAXN =10**6 +10
    #osa_k法
    sieve = [i for i in range(MAXN+1)]
    p = 2
    while p*p <= MAXN:
        if sieve[p] == p:
            for q in range(2*p,MAXN+1,p):
                if sieve[q] == q:
                    sieve[q] = p
        p += 1
    
    ans ="pairwise coprime"
    for a in A:
        aa =osa_k(a)
        if used & aa:
            ans ="setwise coprime"
            break #共通要素があったらpair_wではない→set_w
        used |=aa
    
print(ans)

Submission status: Accepted

Solution code:
import math

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


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, cnt])

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

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

    return arr


def is_pairwise():
    cs = [0] * 1000010
    for i in a:
        for p, _ in factorization(i):
            if p != 1 and cs[p] == 1:
                return False
            cs[p] = 1
    return True


def is_setwise():
    c = a[0]
    for i in a:
        c = math.gcd(c, i)
    return c == 1


if is_pairwise():
    print('pairwise coprime')
elif is_setwise():
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

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):
        """エラトステネスの篩
        """
        limit = math.sqrt(self.n)
        for prime in range(2, self.n + 1):
            if prime >= limit:
                break
            if self.minFactor[prime] == prime:
                self.prime.append(prime)
                for composite in range(2 * prime, self.n + 1, prime):
                    if self.minFactor[composite] == composite:
                        self.minFactor[composite] = prime


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
if not tmp.values():
    print("pairwise coprime")
    exit()
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: Accepted

Solution code:
from math import gcd
from functools import reduce
 
 
def facs(n):
    yield 2
    for x in range(3, n, 2):
        yield x
 
 
def main():
    input()  # N
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 1
    histogram = [0] * MAX_A
    for x in array:
        histogram[int(x)] += 1
 
    for divider in facs(MAX_A):
        count = sum(histogram[divider::divider])
        if count > 1:
            break
    else:
        return 'pairwise coprime'
 
    gcd_total = reduce(gcd, array)
    if gcd_total == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'
 
 
if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import math
from functools import reduce


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


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


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

if gcd_list(A) != 1:
    print('not coprime')
    exit()

primes = set()
for a in A:
    len_primes = len(primes)
    divs = set(prime_factorize(a))
    primes |= divs

    if len(primes) != len_primes + len(divs):
        print('setwise coprime')
        exit()

print('pairwise coprime')

Submission status: Accepted

Solution code:
#E_Coprime
import math
import functools

# エラトステネスの篩
        
def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    D_prime = [i for i in range(n+1)] 
    D_prime[0] = 0
    D_prime[1] = 1
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            D_prime[i] = i
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
            D_prime[j] = i
    return D_prime

    

Fnum_list2 = []
# 入力
N = int(input())
A = list(map(int,input().split()))

#Fnum_list = eratosthenes(N)

A.sort()
Amax = A[-1]
Fnum_list2 = primes(Amax)
j = A[0]
ans = 1
#Fnum_list = eratosthenes(N)
Ai_primes     = set()
Ai_primes_add = []
gcd_num = 0
for i in range(len(A) ):
    p = A[i]
    while p != 1:
        j = p
        p = int (p / Fnum_list2[j])
        if Fnum_list2[j] in Ai_primes:
            ans = 0
        else:
            Ai_primes_add.append(Fnum_list2[j])
    if Fnum_list2[j] in Ai_primes:
        break
    else:
        Ai_primes |= set(Ai_primes_add)
        Ai_primes_add.clear()

gcd_num = functools.reduce(math.gcd,A)

if ans == 0:
    if gcd_num == 1:
        ans = 2

# 出力
if ans == 1:
    print("pairwise coprime")
else:
    if ans == 2:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque
from functools import *
from fractions import Fraction as f
from copy import *
from bisect import *	
from heapq import *
from math import *
from itertools import permutations ,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def inc(d,c):
	d[c]=d[c]+1 if c in d else 1
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<n	
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)


t=1
N=10**6+5
spf=[i for i in range(N+1)]
for i in range(2,int(ceil(sqrt(N)))+2):
	if spf[i]==i:
		for j in range(i*i,N,i):
			if spf[j]==j:
				spf[j]=i
			
def fact(i):
	s=set()
	while i!=1:
		s.add(spf[i])	
		i//=spf[i]
	return s	

while t>0:
	t-=1
	n=fi()
	a=li()
	s=set()
	g=a[0]
	flag=0
	for i in range(n):
		g=gcd(g,a[i])
		k=fact(a[i])
		if len(s&k)!=0:
			flag|=1
		s|=k
	if flag==0:
		print("pairwise coprime")
	elif g==1:
		print("setwise coprime")	
	else:
		print("not coprime")

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
maxA=max(A)
count=[0]*(maxA+1)
for x in A:
    count[x]+=1
maxc=0
for i in range(2,maxA+1):
    maxc = max(maxc,sum(count[i::i]))

if maxc==N:
    print('not coprime')
elif maxc<=1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Accepted

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N = n1()
A = nn()

#MAX = 10**6
MAX = max(A)
dp = defaultdict(list)

p = 2
while p <= MAX:
    i = p
    while i <= MAX:
        dp[i].append(p)
        i += p

    p += 1
    while len(dp[p]) >= 1:
        p += 1

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

dic = defaultdict(list)

for ai in A:
    fact = dp[ai]
    for x in fact:
        dic[x].append(ai)

maxlen = 0
for k, v in dic.items():
    maxlen = max(len(v), maxlen)

if maxlen == 1:
    print("pairwise coprime")
elif maxlen == N:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Accepted

Solution code:
def eratosthenes(N):
    is_prime = {i: True for i in range(2, N+1)}
    primes = []
    for i in range(2, N+1):
        if is_prime[i]:
            primes.append(i)
            if i**2 <= N:
                for j in range(i**2, N+1, i):
                    is_prime[j] = False
    return primes


def gcd(a, b):
    a, b = max(a, b), min(a, b)
    if b == 0:
        return a
    return gcd(b, a % b)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    allgcd = A[0]
    primes = eratosthenes(1000)
    divs = set()
    pairwise_coprime = True
    for a in A:
        if allgcd > 1:
            allgcd = gcd(allgcd, a)
        if not pairwise_coprime:
            continue
        for p in primes:
            if a % p == 0:
                if p in divs:
                    pairwise_coprime = False
                while a % p == 0:
                    a //= p
                divs.add(p)
            if a == 1:
                break
        if a != 1:
            if a in divs:
                pairwise_coprime = False
            divs.add(a)
    if pairwise_coprime:
        print("pairwise coprime")
    else:
        if allgcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd
class Factor:
    def __init__(self, max_element):
        self.minFactor = [-1]*(max_element+1)
        for i in range(2, max_element+1):
            if self.minFactor[i] == -1:
                for j in range(i, max_element+1, i):
                    self.minFactor[j] = i
    def getFactorSet(self, element):
        retSet = set(1)
        while element > 1:
            retSet.add(element)
            retSet.add(self.minFactor[element])
            element //= self.minFactor[element]
        return retSet
    def getPrimeFactorSet(self, element):
        retSet = set()
        while element > 1:
            retSet.add(self.minFactor[element])
            element //= self.minFactor[element]
        return retSet
    def getPrimeFactorDic(self, element):
        retDic = {}
        while element > 1:
            val = self.minFactor[element]
            if val in retDic:
                retDic[val] += 1
            else:
                retDic[val] = 1
            element //= val
        return retDic

def main():
    n = int(input())
    a = list(map(int, input().split()))
    f = True
    fact = Factor(max(a))
    st = set()
    for v in a:
        fac_set = fact.getPrimeFactorSet(v)
        for u in fac_set:
            if u in st:
                f = False
                break
            st.add(u)
        if not f:
            break
    if f:
        print("pairwise coprime")
    else:
        all_gcd = a[0]
        for i in range(1, n):
            all_gcd = gcd(all_gcd, a[i])
        if all_gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = LIST()

c = [0]*(10**6+1)
for x in a:
    c[x] += 1

k = max(sum(c[i::i]) for i in range(2, 10**6+1))

if k <= 1:
    print("pairwise coprime")
elif k < n:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

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

def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor: GCD)を求める
    計算量: O(log(min(a, b)))
    """
    while b:
        a, b = b, a % b
    return a


def multi_gcd(array: list) -> int:
    """arrayのGCDを求める"""
    n = len(array)
    ans = array[0]
    for i in range(1, n):
        ans = gcd(ans, array[i])
    return ans


def make_mindiv_table(n):
    mindiv = [i for i in range(n + 1)]
    for i in range(2, int(n ** 0.5) + 1):
        if mindiv[i] != i:
            continue
        for j in range(2 * i, n + 1, i):
            mindiv[j] = min(mindiv[j], i)
    return mindiv


def get_prime_factors(num):
    res = []
    while mindiv[num] != 1:
        res.append(mindiv[num])
        num //= mindiv[num]
    return res


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


mindiv = make_mindiv_table(10 ** 6)

set_primes = set()
flag = True
for val in a:
    set_ = set(get_prime_factors(val))
    for v in set_:
        if v in set_primes:
            flag = False
        set_primes.add(v)
    if not flag:
        break
else:
    print("pairwise coprime")
    exit()

gcd_ = multi_gcd(a)
if gcd_ == 1:
    print("setwise coprime")
    exit()

print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd
flag=0
N=int(input())
A=list(map(int,input().split()))
Max=max(A)
a=[0]*(Max+1)
for i in A:
    a[i]+=1
for i in range(2,Max+1):
    if sum(a[i::i])>=2:
        flag=1
        break
if flag==0:
    print('pairwise coprime')
else:
    r=A[0]
    for i in A:
        r=gcd(r,i)
    if r==1:
        print('setwise coprime')
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [0] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i] == 0:
            p.append(i)
            t[i] = i
            for j in range(2*i, n, i):
                if t[j] == 0:
                    t[j] = i

    for j in range(i+1, n):
        if t[j] == j or t[j] == 0:
            p.append(j)
            t[j] = j

    return p, t


@mt
def slv(N, A):
    _, T = eratosthenes(10**6+1)

    used = set()
    for a in A:
        while a != 1:
            p = T[a]
            if p in used:
                break
            while a % p == 0:
                a //= p
            used.add(p)
        if a != 1:
            break

    else:
        return 'pairwise coprime'

    return 'setwise coprime' if reduce(math.gcd, A) == 1 else 'not coprime'


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [0] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i] == 0:
            p.append(i)
            t[i] = i
            for j in range(2*i, n, i):
                if t[j] == 0:
                    t[j] = i

    for j in range(i+1, n):
        if t[j] == j or t[j] == 0:
            p.append(j)
            t[j] = j

    return p, t


@mt
def slv(N, A):
    _, T = eratosthenes(10**6+1)

    used = set()
    for a in A:
        while a != 1:
            p = T[a]
            if p in used:
                break
            while a % p == 0:
                a //= p
            used.add(p)
        if a != 1:
            break

    else:
        return 'pairwise coprime'

    g = 0
    for a in A:
        g = math.gcd(a, g)
    return 'setwise coprime' if g == 1 else 'not coprime'


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [0] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i] == 0:
            p.append(i)
            t[i] = i
            for j in range(2*i, n, i):
                if t[j] == 0:
                    t[j] = i

    for j in range(i+1, n):
        if t[j] == j or t[j] == 0:
            p.append(j)
            t[j] = j

    return p, t


@mt
def slv(N, A):
    P, T = eratosthenes(10**6+1)
    P = set(P)

    used = set()
    for a in A:
        while a != 1:
            p = T[a]
            if p in used:
                break
            while a % p == 0:
                a //= p
            used.add(p)
        if a != 1:
            break

    else:
        return 'pairwise coprime'

    g = 0
    for a in A:
        g = math.gcd(a, g)
    return 'setwise coprime' if g == 1 else 'not coprime'


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd
import sys

MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p,MAXN+1,p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1
    
def pf(a):
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
        
    return list(tmp)




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



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

deta = set()
for a in A:
    a=pf(a)
    
    for p in a:
        if p in deta:
            print("setwise coprime")
            sys.exit()
            
        deta.add(p)


print("pairwise coprime")

Submission status: Accepted

Solution code:
#ABC177E
N = int(input())
#N = 1000000
A = list(map(int, input().split()))
#A = [i+1 for i in range(1000000)]
p = {2*i+1: 1 for i in range(1, 500)}
for i in range(3, 1000, 2):
  for j in p:
    if j != i:
      if j % i == 0:
        p[j] = 0
L = [2]
for i in p:
  if p[i] == 1:
    L.append(i)
def gcd(x, y):
  k, l = x, y
  while l:
    k, l = l, k % l
  return k
g = A[0]
i = 0
nn = len(L)
while i < N:
  g = gcd(g, A[i])
  if g == 1:
    break
  i += 1
if g > 1:
  print("not coprime")
else:
  D = {}
  m = 0
  for i in A:
    pnt = 0
    x = i
    for j in L:
      cnt = False
      while x % j == 0:
        cnt = True
        x //= j
      if cnt:
        if j in D:
          D[j] += 1
          if D[j] == 2:
            m = 2
            break
        else:
          D[j] = 1
      pnt += 1
      if pnt == nn and x != 1:
        if x in D:
          D[x] += 1
          if D[x] == 2:
            m = 2
        else:
          D[x] = 1
        break
      if x == 1:
        break
    if m >= 2:
      break
  if D == {}:
    print("pairwise coprime")
  else:
    if m > 1:
      print("setwise coprime")
    else:
      print("pairwise coprime")