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:
from math import gcd
from collections import defaultdict
def main():
    n = int(input())
    a = list(map(int,input().split()))
    dic = defaultdict(bool)
    pairW = True
    setW = a[0]
    for i in a:
        t = 1
        while t**2 <= i:
            if i % t == 0:
                if (t != 1 and dic[t]) or (i//t != 1 and dic[i//t]):
                    pairW = False
                    break
                else:
                    dic[t] = True
                    dic[i//t] = True
            t += 1
        setW = gcd(setW,i)
    

    if pairW:
        print("pairwise coprime")
        return
    elif setW == 1:
        print("setwise coprime")
        return
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getList()

pair = True
semi = True
# not divisible
# 全部互いに素かどうか
judge = [0] * (10 ** 6 + 1)
num_list = [0] * (10 ** 6 + 1)

for i in A:
    judge[i] += 1

for i in range(2, 10 ** 6 + 1):
    if num_list[i] == 1:
        continue
    cnt = 0
    for j in range(i, 10 ** 6 + 1, i):
        num_list[j] = 1
        cnt += judge[j]
    if cnt > 1:
        if cnt == N:
            semi = False
        pair = False

if pair and semi:
    print('pairwise coprime')
elif semi:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

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

def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

A.sort()
M = A[-1]
d = {}
ans = 0

for i in range(N):
    if A[i] not in d:
        primes = prime_decomposition(A[i])
        for p in primes:
            for j in range(1,M//p+1):
                d[j*p] = 0
    else:
        ans = 1
        break
if ans == 0:
    print('pairwise coprime')
else:
    def gcd(a, b):
    	while b:
    		a, b = b, a % b
    	return a
    a = A[0]
    for i in range(N):
        a = gcd(a,A[i])
    if a==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Accepted

Solution code:
def seachPrimeNum(N):
    max = int(N**.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

P=seachPrimeNum(5*10**5)

def factorization(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)

    if arr==[]:
        arr.append(n)
    return arr

factorization(24) 

n=int(input())
A=[int(i) for i in input().split()]
DIC={i:0 for i in range(1,10**6+1)}
for ele in A:
    DIC[ele]+=1
pair=True
setw=True
if n!=len(A):
    pair=False

for pri in P:
    cnt=0
    for i in range(pri,10**6+1,pri):
        cnt+=DIC[i]
    if cnt>1:
        pair=False
    if cnt==len(A):
        setw=False

if pair:
    print("pairwise coprime")
elif setw:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from fractions import gcd
N=int(sys.stdin.readline().strip())
A=map(int, sys.stdin.readline().split())

def factorization(n):
    arr=set()
    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.add(i)

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

    if arr==[]:
        arr.add(n)

    return arr

pairwise_coprime=True

SOINSU=defaultdict(lambda: 0)

setwise_coprime=None
for i,a in enumerate(A):
    #全ての数が互いに素か　pairwise coprime判定
    if pairwise_coprime==False:
        pass
    else:
        f=factorization(a)
        for x in f:
            if SOINSU[x]==1:
                pairwise_coprime=False
                break
            SOINSU[x]=1
    #GCDの累積を取る　setwise coprime判定
    if i==0:
        setwise_coprime=a
    else:
        setwise_coprime=gcd(setwise_coprime,a)

if pairwise_coprime==True:
    print "pairwise coprime"
elif setwise_coprime==1:
    print "setwise coprime"
else:
    print "not coprime"

Submission status: Accepted

Solution code:
import sys
n=int(input())
A=[int(i) for i in input().split()]

N=10**6
spf = [i for i in range(N+1)]

for i in range(2,N):
    if i**2>N:
        break
    if spf[i] == i:
        for j in range(i**2,N+1,i):
            if spf[j] == j:
                spf[j] = i

def get(n):
    ps = set()
    while n != 1:
        ps.add(spf[n])
        n //= spf[n]
    return ps

#f1=True
f2=True

n0 = list(get(A[0]))
K=set(n0)
J=set(n0)

for a in A[1:]:
    res = get(a)
    #print(K,J,res)
    
    if len(res) != 0:
        K &= res
        
    if len(J & res) !=0:
        f2 = False
        
    if len(res) != 0:
        J |= res
        
#print(K,J,res)        
        
if (1 in A) or len(K) == 0:
    f1 = True
else:
    f1 = False
    
if f1:
    if f2:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

# from fractions import gcd
from math import gcd
# def lcm(x, y):
#   return x // gcd(x, y) * y

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

    return divisors

def solve():
    N = II()
    A = LI()
    mx = max(A)
    A = sorted(A, reverse=True)
    # print(A)
    g = A[0]
    flag_pc = True
    F = [0] * (mx+1)
    ff = True
    for a in A:
        g = gcd(g, a)
        # print(g)
        if g != 1:
            flag_pc = False
        
        # print(a)
        if F[a] > 0 and a != 1:
            ff = False

        if ff:
            for j in range(1, int(a**0.5)+1):
                if a % j == 0:
                    if F[j] > 0 and j != 1:
                        ff = False
                        break
                    F[j] += 1

                    if j != (a//j):
                        if F[a//j] > 0 and (a//j) != 1:
                            ff = False
                            break
                        F[a//j] += 1
    # print(F)
    # print(ff)

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    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:
                break

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

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

    return arr


def can_factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  # ここにバグがないか心配
        if temp % i == 0:
            arr.append(i)

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

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

    return arr


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
import random
from math import gcd


N = a_int()
A = ints()
random.shuffle(A)

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
for a in A:
    g_set = gcd(g_set, a)
    if flg:
        for p, n in factorization(a):
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Accepted

Solution code:
import math as mt
I=lambda:list(map(int,input().split()))
mod=10**9
n,=I()
l=I()
x=0
y=0
temp=l[0]
for i in range(1,n):
	temp=mt.gcd(temp,l[i])
N=10**6+3
ss=[0]*(N)
ss[0]=1
for i in range(2,N):
	if ss[i]==0:
		ss[i]=i
		for j in range(2*i,N,i):
			ss[j]=i
if temp!=1:
	print("not coprime")
else:
	pos=1
	visi=[0]*N
	for i in range(n):
		now=l[i]
		while now>1:
			te=ss[now]
			if visi[te]:
				pos=0
				break
			while now%te==0:
				now//=te
			visi[te]=1
		if not pos:
			break
	if pos:
		print("pairwise coprime")
	else:
		print("setwise coprime")

Submission status: Accepted

Solution code:
import sys
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))

# MOD = 10**9 + 7
def main():
	MAXN = 1000001
	spf = [0 for i in range(MAXN)] 
	# sett = set()
	def sieve(): 
		spf[1] = 1
		for i in range(2, MAXN):  
			spf[i] = i 

		for i in range(4, MAXN, 2): 
			spf[i] = 2

		for i in range(3, ceil(sqrt(MAXN))): 
			
			if (spf[i] == i): 
				
				for j in range(i * i, MAXN, i): 
					
					if (spf[j] == j): 
						spf[j] = i
	sieve()
	n = int(input()); arr = read()
	gcd_ = arr[0]
	check = [0]*(10**6 +1)
	f1 = 0; f2 = 1
	for i in arr:
		gcd_ = gcd(gcd_, i)
		# x = i
		ret = []
		flag = 1
		while (i != 1):
			if check[spf[i]]:# in sett:
				flag = 0
			ret.append(spf[i]) 
			i = i // spf[i]
		for j in ret:check[j] = 1
		# sett = sett.union(ret)
		# print(x, flag)
		f1 += flag; f2 &= flag

	# print(sett)

	if f2:print("pairwise coprime")
	elif gcd_ == 1:print("setwise coprime")
	else:print("not coprime")



	



if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import math
import numpy as np

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



def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

prime_num = set(get_sieve_of_eratosthenes_new(999984))

def pairwise_coprime():
    gcd = dict()
    for a in A:
        if a in prime_num:
            if not (a in gcd):
                gcd[a] = 1
            else:
                return False
        else:
            tmp = a
            for p in prime_num:
                if tmp == 1:
                    break
                # print(tmp, p)

                if tmp % p == 0:
                    if not(p in gcd):
                        gcd[p] = 1
                    else:
                        return False
                    
                    while tmp % p == 0:
                        tmp //= p
    # print(gcd)
    
    return True
                


def setwise_coprime():
    gcd = A[0]
    for i in range(1, N):
        gcd = math.gcd(gcd, A[i])
        # print(gcd)
        if gcd == 1:
            break
    
    if gcd == 1:
        return True
    else:
        return False

if pairwise_coprime():
    print("pairwise coprime")
elif setwise_coprime():
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

n = int(input())
List = list(map(int, input().split()))
N = max(List)
A = defaultdict(int)
for e in List:
    A[e] += 1
furui = [True]*(N+1)

state = "pairwise coprime"
for i in range(2, N+1):
    if not furui[i]:
        continue
    count = 0
    k = i
    while k <= N:
        if k in A:
            count += A[k]
            if count >= 2:
                # print(i, k)
                state = "setwise coprime"
            if count == n:
                print("not coprime")
                exit()

        furui[k] = False
        k += i

print(state)

Submission status: Accepted

Solution code:
from math import gcd
n=int(input())
a=list(map(int,input().split()))
a.sort()
lis=[False]*(10**6+1)
ok=True
d=dict()
for num in a:
    if num in d:
        d[num]+=1
    else:
        d[num]=1
for num in range(2,10**6+1):
    if lis[num]:
        continue
    cnt=0
    for i in range(num,10**6+1,num):
        lis[i]=True
        if i in d:
            cnt+=d[i]
    if cnt>=2:
        ok=False
if ok:
    print("pairwise coprime")
else:
    g=a[0]
    for num in a:
        g=gcd(g,num)
    if g==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
from math import gcd
M = 10**6
def main(N, A):
    g = 0
    for a in A:
        g = gcd(g, a)
    if g > 1:
        print('not coprime')
        return

    u = [False] * (M + 1)
    cc = [0] * (M + 1)
    for a in A:
        cc[a] += 1
    for n in range(2, M + 1):
        if u[n]: continue
        c = 0
        for nn in range(n, M + 1, n):
            u[nn] = True
            c += cc[nn]
        if c >= 2:
            print('setwise coprime')
            return
    print('pairwise coprime')

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)

Submission status: Accepted

Solution code:
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
N = int(input())
arr = list(map(int, input().split()))
M = max(arr)
arr.sort()
check = [0]*(M+1)
flg = True
for i in arr:
    for k in make_divisors(i):
        if check[k] != 0 and k != 1:
            flg = False
            break
        else:
            check[k] = 1
    if not flg:
        break
if flg:
    print('pairwise coprime')
    exit()
first = arr[0]
for i in range(1,N):
    first = math.gcd(first,arr[i])
if first == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd

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

g = a[0]
for i in range(1, n):
    g = gcd(g, a[i])
    if g == 1:
        break
else:
    print('not coprime')
    exit()

ind = [-1] * (10**6)

prime = [2, 3, 5, 7]
for i in range(11, 10 ** 6, 2):
    j = 0
    flag = True
    while prime[j] * prime[j] <= i:
        if i % prime[j] == 0:
            flag = False
            break
        else:
            j += 1
    if flag:
        prime.append(i)

for i in range(len(prime)):
    ind[prime[i]] = i

# len(prime) = 78498

tf = [False] * len(prime)

for i in a:
    for j in range(len(prime)):
        if i == 1:
            break
        if prime[j] * prime[j] > i:
            if tf[ind[i]]:
                print('setwise coprime')
                exit()
            tf[ind[i]] = True
            break

        if i % prime[j] == 0:
            if tf[j]:
                print('setwise coprime')
                exit()
            tf[j] = True
            while i % prime[j] == 0:
                i //= prime[j]

print('pairwise coprime')

Submission status: Accepted

Solution code:
from functools import reduce
from itertools import combinations
from math import gcd


def func(A):
    n = len(A) - len(set(A))
    if n > 0 and n+1 != A.count(1):
        return False
    is_A = [False] * (10**6+1)
    for a in A:
        is_A[a] = True
    n = 0
    for i in range(2, 10**6+1, 2):
        if is_A[i]:
            n += 1
    if n > 1:
        return False
    for i in range(3, 10**6+1, 2):
        n = 0
        for j in range(i, 10**6+1, i):
            if is_A[j]:
                n += 1
        if n > 1:
            return False
    return True


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    if func(A):
        # if not all(gcd(i, j)==1 for i, j in combinations(A, 2)):
        #     raise NameError
        print('pairwise coprime')
    elif reduce(gcd, A) == 1:
        print('setwise coprime')
    else:
        print('not coprime')
    

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

sosu = [1 for _ in range(10**6+1)]
sosu[0] = 0
sosu[1] = 1
i = 2
while i < len(sosu):
    j = i*2
    if sosu[i] == 0:
        i += 1
        continue
    while j < len(sosu):
        sosu[j] = 0
        j += i
    i += 1

sosus = []
for i in range(2, len(sosu)):
    if sosu[i]:
        sosus.append(i)

sosuset = set()
flag = 0
GCD = a[0]
for i in range(n-1, -1, -1):
    J = 0
    j = sosus[J]
    GCD = math.gcd(GCD, a[i])

    while j*j <= a[i]:
        if a[i]%j == 0 and j in sosuset:
            flag = 1
            break
        while a[i]%j == 0:
            a[i]//=j
            sosuset.add(j)
        J += 1
        j = sosus[J]
    if a[i] in sosuset:
        flag = 1
    if a[i] != 1:
        sosuset.add(a[i])


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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = LIST()
lim = 10**6+1
g = [[] for _ in range(lim+1)]
g[1].append(1)
for i in range(2, lim+1):
	if g[i] == []:
		for j in range(1, lim//i + 1):
			g[i*j].append(i)

num = [0]*(lim+1)

for a in A:
	if a == 1:
		continue
	for x in g[a]:
		if num[x]:
			break
		num[x] = 1

	else:
		continue
	break
else:
	print("pairwise coprime")
	exit()


#素因数分解
def factorization(n):
	arr = []
	tmp = n
	for i in range(2, int(-(-n**0.5//1))+1):
		if tmp%i == 0:
			cnt = 0
			while tmp%i == 0:
				cnt += 1
				tmp //= i
			arr.append([i, cnt])
	if tmp != 1:
		arr.append([tmp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr
	
dic = defaultdict(int)
for x, y in factorization(A[0]):
	dic[x]=y

for a in A[1:]:
	for x, y in dic.items():
		if a%x:
			dic[x] = 0
		else:
			dic[x] = min(y, a//x)

for x, y in dic.items():
	if x != 1 and y != 0:
		print("not coprime")
		break
else:
	print("setwise coprime")

Submission status: Accepted

Solution code:
from math import *
import fractions
import sys
import collections
import itertools
import pprint
from collections import deque
from heapq import *
import copy
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
n = 10**6
d={}
pairflag=1
setflag=0
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)
#print(len(primes))
buf=[0]*(max(A)+10)
seen=[0]*(max(A)+10)
for i in range(N):
    if d.get(A[i])==None:
        d[A[i]]=1
    else:
        d[A[i]]=d[A[i]]+1
#print(d)
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
for i in primes:
    cnt=0
    for j in range(i,10**6+1,i):
        if d.get(j)!=None:
            cnt=cnt+d[j]
    if cnt>1:
        pairflag=0
        break

num=A[0]
for i in range(1,N):
    num=ggcd(num,A[i])
if num==1:
    setflag=1
else:
    setflag=0

if pairflag==1:
    print("pairwise coprime")
elif setflag==1:
    print("setwise coprime")
else:
    print("not coprime")

"""
x=list(set(A))
for i in x:
    for j in range(2*i,10**6+1,i):
        if d.get(j)!=None:
            pairflag=0
            break
    if pairflag==0:
        break
print(pairflag)

"""

Submission status: Accepted

Solution code:
import math
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


N=int(input())
A=list(map(int,input().split()))
count=0
for i in range(N):
    if A[i]==1:
        count+=1
a=A[0]
for i in range(1,N):
    a=math.gcd(a,A[i])
if N>=78500+count and a==1:
    print("setwise coprime")
elif N>=78500+count and a>1:
    print("not coprime")
else:
    flag=True
    num_list=[0 for i in range(10000000)]
    for i in range(N):
        if A[i]>1:
            list_=factorization(A[i])
            for b,d in list_:
                if num_list[b]!=0:
                    flag=False
                else:
                    num_list[b]+=1
    if flag==True and a==1:
        print("pairwise coprime")
    elif flag==False and a==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

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

import math 

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

if ans!=1:
    #print(ans)
    print("not coprime")
    exit()
else:
    checked=[0]*(int(max(a))+1)
    #print(checked)
    for item in a:
        for j in range(1,int(item**0.5)+1):
            if item%j==0 and j*j<=item:
                if checked[j]==0:
                    if j!=1:
                        checked[j]+=1
                    
                    if j*j!=item:
                        if checked[item//j]==0:
                            checked[item//j]+=1
                        else:
                            #print(item,j,checked)
                            print("setwise coprime")
                            exit() 
                else:
                    #print(item,j,checked)
                    print("setwise coprime")
                    exit()
print("pairwise coprime")

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 10 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N = int(input())
A = list(map(int, input().split()))
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

# calc prime
MAX = 10 ** 6 + 2
is_prime = [True] * (MAX + 1)
is_prime[0] = False
is_prime[1] = False
i = 2
primes = []
cnt_a = Counter(A)
if cnt_a[1] == N:
    print('pairwise coprime')
    exit()
cnt_facts = defaultdict(int)
while i < MAX:
    if is_prime[i]:
        if cnt_a[i]:
            cnt_facts[i] += cnt_a[i]
        for j in range(i+i, MAX, i):
            is_prime[j] = False
            if cnt_a[j]:
                cnt_facts[i] += cnt_a[j]
        primes.append(i)
    i += 1
if cnt_facts and max(cnt_facts.values()) <= 1:
    print('pairwise coprime')
    exit()
setwise = False
g = A[0]
for a in A:
    g = gcd(g, a)
if g == 1:
    setwise = True

if setwise:
    print('setwise coprime')
if not setwise:
    print('not coprime')

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
input = sys.stdin.readline
INF = float("inf")


def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n = n // i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table


# 処理内容
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()

    P = [True]*1000010
    pairwise = True
    for a in A:
        if P[a] == False:
            pairwise = False
            break
        
        table = prime_decomposition(a)
        for p in table:
            n = 1
            while p*n <= len(P)-1:
                P[p*n] = False
                n += 1

    setwise = True
    if reduce(math.gcd, A) != 1:
        setwise = False

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



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
NOTCOM = "not coprime"
SETWISE = "setwise coprime"
PAIRWISE = "pairwise coprime"

def calc_prime(N):
    prime, i = set(), 1
    while i * i <= N:
        if N % i == 0:
            yield i
            if i != N//i: yield N//i
        i += 1

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = list(set(A))
    cnt2 = 0
    cnt3 = 0
    allgcd = A[0]
    for a in A:
        allgcd = math.gcd(allgcd, a)
        if a % 2 == 0:
            cnt2 += 1
        if a % 3 == 0:
            cnt3 += 1
    if allgcd != 1:
        return NOTCOM
    
    if cnt2 >= 2 or cnt3 >= 2:
        return SETWISE

    allprime = set()
    for a in A:
        for t in calc_prime(a):
            if t in allprime and t != 1:
                return SETWISE
            allprime.add(t)
    return PAIRWISE

print(main())

Submission status: Accepted

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))
v = 0
for x in a:
    v = math.gcd(x, v)
if v > 1:
    print("not coprime")
else:
    #co or set
    primes = []
    primer = [True for i in range(10**6+1)]
    for p in range(2, 10**6+1):
        if primer[p] == True:
            primes.append(p)
            for i in range(2, 10**6+1):
                if p*i > 10**6:
                    break
                else:
                    primer[p*i] = False
    counter = [0 for i in range(10**6+1)]
    for num in a:
        counter[num] += 1
    pair = True
    for p in primes:
        res = 0
        for j in range(1, 10**6+1):
            if p*j > 10**6:
                break
            else:
                res += counter[p*j]
        if res > 1:
            pair = False
            break
    if pair:
        print("pairwise coprime")
    else:
        print("setwise coprime")