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

def gcdall(a):
	rt = 0
	for i in a:
		rt = math.gcd(rt, i)
		if rt == 1:
			break
	return rt

#GCD(ai, aj)=1 がすべてとは, aの中の素因数に共通のものがないということ

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

def sieve(n):
	ret = set()
	divlis = [-1]*(n+1)  # 何で割ったかのリスト(初期値は-1)
	flag = [True]*(n+1)
	flag[0] = False
	flag[1] = False
	ind = 2
	while ind <= n:
		if flag[ind]:
			ret.add(ind)
			ind2 = ind**2
			while ind2 <= n:
				flag[ind2] = False
				divlis[ind2] = ind
				ind2 += ind
		ind += 1
	#何で割ったかのリストを取得したいとき, divlisも出力する
	return ret

targ = sieve(n)

def pairwise(a):
	t = set()
	mode = True
	for i in a:
		if i == 1:
			continue
		if i in targ:
			if i in t:
				mode = False
				break
			else:
				t.add(i)
		else:
			k = makediv(i)
			for j in k:
				if j == 1:
					continue
				if j not in t:
					t.add(j)
				else:
					mode = False
					break
		if not mode:
			break
	return mode

if gcdall(a) == 1:
	if pairwise(a):
		print("pairwise coprime")
	else:
		print("setwise coprime")
else:
	print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd
import collections

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 = tuple(map(int,input().split()))

g = a[0]
for ai in a:
  g = gcd(g,ai)
if g != 1:
  print('not coprime')
  exit()
b = {}
s = 0
for ai in a:
  c = collections.Counter(prime_factorize(ai))
  for k,v in c.items():
    if k in b:
      print('setwise coprime')
      exit()
    else:
      b[k] = v
print('pairwise coprime')

Submission status: Accepted

Solution code:
from functools import reduce
from collections import defaultdict
import sys
import math

input = sys.stdin.readline

# 素因数分解O(√n)


def primeFactor(n):
    res = defaultdict(lambda: 0)
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res[i] += 1
            n = n // i
    if n != 1:
        res[n] = 1
    return res


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    primes = defaultdict(lambda: 0)
    setp = True
    pairs = True
    if gcd(*A) != 1:
        setp = False
        pairs = False
    else:
        for i in range(N):
            pf = primeFactor(A[i])
            for k in pf.keys():
                primes[k] += 1
                if primes[k] != 1:
                    pairs = False
            if not pairs:
                break
    if pairs:
        print('pairwise coprime')
    elif setp:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def sieve_eratosthenes(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes

NB = int(input())
B = list(map(int,input().split()))
A = []
for i in range(NB):
    if B[i]!=1:
        A.append(B[i])
N = len(A)

if N==0:
    print("pairwise coprime")
else:
    P = sieve_eratosthenes(10**6)
    Ps = []
    for i in range(10**6):
        if P[i]==1:
            Ps.append(i)
    PN = len(Ps)

    if N>PN+10:
        if NB-N>0:
            print("setwise coprime")
        else:
            print("not coprime")
    else:
        flag = 0
        pf={}
        for i in range(N):
            pf1 = {}
            m=A[i]
            for i in range(2,int(m**0.5)+1):
                while m%i==0:
                    pf1[i]=pf1.get(i,0)+1
                    m//=i
            if m>1:pf1[m]=1
            for i in pf1.keys():
                pf[i]=pf.get(i,0)+1
                if pf[i]>1:
                    flag = 1
        if flag==0:
            print("pairwise coprime")
        else:
            import fractions
            ans = A[0]
            for i in range(1, N):
                ans = fractions.gcd(ans, A[i])
            if ans==1 or N!=NB:
                print("setwise coprime")
            else:
                print("not coprime")

Submission status: Accepted

Solution code:
from sys import stdin

rInt       = lambda : int(stdin.readline().strip("\n"))
rIntArray  = lambda : [int(x) for x in stdin.readline().split()]

rString    = lambda : stdin.readline().strip("\n")
rStrArray  = lambda : [x for x in stdin.readline().split()]

# for _ in range(rInt()):

maxn = 10**6

n = rInt()
arr = rIntArray()

pairwise = True

present = [0]*(maxn + 1)
for i in arr: present[i] += 1

for i in range(2, maxn + 1):
	cnt = 0
	for j in range(i, maxn + 1, i):
		cnt += present[j]
	if cnt > 1:
		pairwise = False

from math import gcd
g = 0
for i in arr: g = gcd(g, i)

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

Submission status: Accepted

Solution code:
import math
import random


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve2(N, A):
    gcd = A[0]
    answer = 'pairwise coprime'
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            if math.gcd(A[i], A[j]) != 1:
                answer = 'setwise coprime'
            gcd = math.gcd(gcd, math.gcd(A[i], A[j]))
    if gcd > 1:
        return 'not coprime'
    return answer


def solve():
    N = read_int()
    A = read_ints()
    gcd = A[0]
    for a in A[1:]:
        gcd = math.gcd(gcd, a)
    if gcd > 1:
        return 'not coprime'

    is_prime = [True]*(10**6+1)
    B = [False]*(10**6+1)
    for a in A:
        if B[a] and a > 1:
            return 'setwise coprime'
        B[a] = True

    for p in range(2, 10**6+1):
        if is_prime[p]:
            count = B[p]
            for q in range(2*p, 10**6+1, p):
                is_prime[q] = False
                count += B[q]
            if count > 1:
                return 'setwise coprime'
    return 'pairwise coprime'


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
mod = 10**9 + 7
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    primes = []
    isprime = [True for i in range(1001)]
    for i in range(2, 1001):
        if isprime[i]:
            primes.append(i)
            for j in range(i * i, 1001, i):
                isprime[j] = False
    x = a[0]
    f = True

    cnt = [0 for i in range(1000001)]
    for val in a:
        x = gcd(x, val)
        i = 0
        while i < len(primes) and primes[i] ** 2 <= val:
            if val % primes[i] == 0:
                cnt[primes[i]] += 1
                while val % primes[i] == 0:
                    val //= primes[i]
            i += 1
        if val > 1:
            cnt[val] += 1
    for i in range(2, 1000001):
        if cnt[i] > 1:
            f = False
            break
    if f:
        print('pairwise coprime')
    elif x == 1:
        print('setwise coprime')
    else:
        print('not coprime')



t = 1
while t > 0:
    solve()
    t -= 1

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
a = [int(i) for i in input().split()]

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

s = set(a)
a.sort()
m = a[-1]
isPrime = [False]*(m+1)
for i in range(2,m+1):
    if isPrime[i]: continue
    flag = False
    for j in range(i,m+1,i):
        isPrime[j] = True
        if j in s:
            if flag:
                print("setwise coprime")
                exit()
            flag = True
print("pairwise coprime")

Submission status: Accepted

Solution code:
import math
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
m=max(a)+1
g=a[0]
d=dict()
for i in a:
    g=math.gcd(g,i)
    if i in d:
        d[i]+=1
    else:
        d[i]=1
if g>1:
    print("not coprime")
else:
    p=[0]*(m)
    ch=0
    for i in range (2,m):
        if p[i]==1:
            continue
        p[i]=1
        ans=0
        for j in range (i,m,i):
            if j in d:
                ans+=d[j]
        if ans>1:
            ch=1
            break
    if ch==1:
        print("setwise coprime")
    else:
        print("pairwise coprime")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
a = [int(item) for item in input().split()]

smallest_factor = [-1] * (10**6 + 10) 
for i in range(2, n+1):
    if smallest_factor[i] != -1:
        continue
    base = i
    j = 2
    while base * j <= (10**6 + 1):
        smallest_factor[base * j] = i
        j += 1

factor_count = [0] * (10**6 + 10)
is_pairwise = True
for item in a:
    if item == 1:
        continue
    pset = set() 
    while smallest_factor[item] != -1:
        pset.add(smallest_factor[item])
        item //= smallest_factor[item]
    pset.add(item)
    for p in pset:
        factor_count[p] += 1

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

Submission status: Accepted

Solution code:
# Python3 program to find prime factorization 
# of a number n in O(Log n) time with 
# precomputation allowed. 
import math as mt 

MAXN = 1000001

# stores smallest prime factor for 
# every number 


# Calculating SPF (Smallest Prime Factor) 
# for every number till MAXN. 
# Time Complexity : O(nloglogn) 
def sieve(): 
    spf = [0 for i in range(MAXN)] 
    spf[1] = 1
    for i in range(2, MAXN): 
		
		# marking smallest prime factor 
		# for every number to be itself. 
        spf[i] = i 

	# separately marking spf for 
	# every even number as 2 
    for i in range(4, MAXN, 2): 
        spf[i] = 2

    for i in range(3, mt.ceil(mt.sqrt(MAXN))): 
		
		# checking if i is prime 
        if (spf[i] == i): 
			
			# marking SPF for all numbers 
			# divisible by i 
            for j in range(i * i, MAXN, i): 
				
				# marking spf[j] if it is 
				# not previously marked 
                if (spf[j] == j): 
                    spf[j] = i 
    return spf

# A O(log n) function returning prime 
# factorization by dividing by smallest 
# prime factor at every step 
def getFactorization(x,spf): 
	ret = set()
	while (x != 1): 
		ret.add(spf[x]) 
		x = x // spf[x] 

	return ret 

# # Driver code 

# # precalculating Smallest Prime Factor 
# sieve() 
# x = 12246
# print("prime factorization for", x, ": ", 
# 								end = "") 

# # calling getFactorization function 
# p = getFactorization(x) 

# for i in range(len(p)): 
# 	print(p[i], end = " ") 

# This code is contributed 
# by Mohit kumar 29 


def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor,gcd
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    # from random import random
    # N = int(random()*10**6)
    # A = []
    # for i in range(N):
    #     A.append(1+int(random()*10**6))

    spf = sieve()
    primes = set()
    PairWise = True
    for a in A:
        p = getFactorization(a,spf)
        if len(p & primes) > 0:
            PairWise = False
            break
        primes |= p
    else:
        print('pairwise coprime')
        return

    all_gcd = A[0]
    for a in A:
        all_gcd = gcd(all_gcd,a)
        if all_gcd == 1:
            print('setwise coprime')
            return
    print('not coprime')

    


    
main()

Submission status: Accepted

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

P=primes(10**6)

def f(n):
    arr = []
    temp = n
    j=0
    while P[j]**2<=temp:
        i=P[j]
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
        j=j+1

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

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

    return arr


B=[0]*(10**6+10)
n=int(input())
A=list(map(int,input().split()))
for i in range(n):
  if A[i]==1:
    continue
  D=f(A[i])
  for j in range(len(D)):
    B[D[j][0]]+=1
f=0
for i in range(10**6+5):
  if B[i]>1:
    f=1
if f==0:
  print("pairwise coprime")
  exit()
for i in range(10**6+5):
  if B[i]>=n:
    f=0
if f==1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd


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


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

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

Submission status: Accepted

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

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))
import math
from functools import reduce

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

n = int(input())
a = lmp()
agcd = gcd(a)
used = set()
flag = True
for i in range(n):
    tar = a[i]
    if tar == 1:
        pass
    else:
        f = factorization(tar)
        for j in range(len(f)):
            if f[j][0] not in used:
                used.add(f[j][0])
            else:
                flag = False
                break
        if not flag:
            break
if flag:
    print("pairwise coprime")
elif agcd == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = 10**6
    table = [0 for _ in range(N+1)]
    prime = [True] * (N+1)
    for i in range(2, N+1):
        if not prime[i]:
            continue
        else:
            table[i] = i
            num = i + i
            while num < N:
                prime[num] = False
                table[num] = i
                num += i

    def factorize(n):
        ans = []
        while not prime[n]:
            ans.append(table[n])
            n = n // table[n]
        ans.append(n)
        return ans
    n = I()
    A = LI()
    coprime = True
    c = collections.Counter()
    memo = {}
    for a in A:
        soinsu = factorize(a)
        memo[a] = soinsu
        for s in soinsu:
            c[s] += 1
    for a in A:
        soinsu = memo[a]
        for s in soinsu:
            c[s] -= 1
        for s in soinsu:
            if s == 1:
                continue
            if c[s] > 0:
                coprime = False
                break
    def gcd(a, b):
        if b == 0:
            return a
        return gcd(b, a % b)

    if coprime:
        print("pairwise coprime")
        return

    setwise = False
    m = A[0]
    for a in A[1:]:
        m = gcd(a, m)
    if m == 1:
        setwise = True

    if setwise:
        print("setwise coprime")
        return

    print("not coprime")
    return





main()

Submission status: Accepted

Solution code:
n=int(input())
l=[*map(int,input().split())]
from math import *
g=l[0]
for x in l:
  g=gcd(g,x)
if g>1: exit(print('not coprime'))
from collections import *
d=Counter()
b=0
for x in l:
  if x%2<1:
    if d[2]:
      b=1
      break
    d[2]=1
  while x%2<1: x//=2
  for i in range(3,int(x**0.5)+1,2):
    if x%i<1:
      if d[i]:
        b=1
        break
      d[i]=1
    while x%i<1: x//=i
    if x<2: break
  if x>1:
    if d[x]:
      b=1
      break
    d[x]=d.get(x,0)+1
print(['pair','set'][b]+'wise coprime')

Submission status: Accepted

Solution code:
def pf(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()))
b = [0]*1000001
for i in range(n):
    x = pf(a[i])
    x = list(set(x))
    for j in x:
        b[j] += 1
#print(b)
tnp = 0
for i in range(1000001):
    if (b[i]>1):
        tnp += 1
        break
if (tnp==0):
    print("pairwise coprime")
    exit()
        
for i in range(1000001):
    if (b[i]==n):
        print("not coprime")
        exit()
print("setwise coprime")

Submission status: Accepted

Solution code:
def max(a,b):
    if a>b:
        return a
    else:
        return b

def min(a,b):
    if a>b:
        return b
    else:
        return a

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

from collections import defaultdict
def factorize(n,dd):
    #print(int(n**0.5))
    for i in range(2,int(n**0.5)+1):
        flag=True
        while n%i==0 and n>0:
            if flag:
                if dd[i]>0:
                    return False
                else:
                    flag=False
            dd[i]+=1
            n//=i
    if n>1:
        if dd[n]>0:
            return False
        dd[n]+=1
    #print(dd)
    return True

def gcdl(A):
    if len(A)==2:
        return gcd(A[0],A[1])
    elif len(A)==1:
        return A[0]
    else:
        return gcd(gcdl(A[:len(A)//2]),gcdl(A[len(A)//2:]))

import sys

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

def main():
    N = int(input())

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

    B = [a for a in A if a!=1]

    if len(B)<=1:
        print("pairwise coprime")
    else:
        N = len(B)
        if N>78498:
            if len(B)!=len(A):
                print("setwise coprime")
            else:
                print("not coprime")
        else:
            dd = defaultdict(int)
            flag=True
            for b in B:
                if factorize(b,dd)==False:
                    flag=False
                    break
            if flag:
                print("pairwise coprime")
            else:
                if len(B)!=len(A):
                    print("setwise coprime")
                elif gcdl(B)==1:
                    print("setwise coprime")
                else:
                    print("not coprime")        
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]

def make_sfp(N):
    F = [False] * (N + 1)
    P = [10 ** 7] * (N + 1)
    for i in range(2, N + 1):
        if F[i]:
            continue

        P[i] = i
        for j in range(i, N + 1, i):
            F[j] = True
            P[j] = min(P[j], i)
    return P


def dev_p(P, n):
    S = set()
    while n != 1:
        S.add(P[n])
        n //= P[n]
        
    return S


def main():
    N = int(input())
    A = read_list()
    D = dict()
    P = make_sfp(max(A))

    for a in A:
        S = dev_p(P, a)
        for s in S:
            D[s] = D.setdefault(s, 0) + 1
    
    is_pairwise = True
    for v in D.values():
        if v == N:
            print("not coprime")
            return
        elif v >= 2:
            is_pairwise = False
    
    print("pairwise coprime" if is_pairwise else "setwise coprime")
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def pair (inp):
    from collections import Counter
    z=max(inp)
    arr=[1]*(z+1)
    c=Counter(inp)
    c[1]=0
    if max(c.values())>=2:
        return -1
    for i in range(2,z+1):
        if arr[i]==1:
            k=2
            if c[i]>=1:
                f=1
            else:
                f=0
            while k*i<len(arr):
                arr[k*i]=0
                if c[k*i]!=0:
                    f+=c[k*i]
                k+=1
            if f>=2:
                return -1
    return 1
def gcd (a,b):
    if a%b==0:
        return b
    if b%a==0:
        return a
    if a>b:
        return gcd(b,a%b)
    if b>a:
        return gcd(a,b%a)
n=int(input())
arr=list(map(int,input().split()))
if pair(arr)==1:
    print ('pairwise coprime')
else:
    k=arr[0]
    for i in range(1,len(arr)):
        k=gcd(k,arr[i])
        if k==1:
            break
    if k==1:
        print ('setwise coprime')
    else:
        print ('not coprime')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

#solve
def solve():
    n = II()
    a = LI()
    x = 1
    if 1 in a:
        x = 0
    a = [i for i in a if i != 1]
    M = 10 ** 6 + 1
    p = [True] * M
    p[0] = False
    p[1] = False
    d = [-1] * M
    for xi in range(2, M):
        if p[xi]:
            d[xi] = xi
            for i in range(xi * 2, M, xi):
                p[i] = False
                if d[i] == -1:
                    d[i] = xi
    res = defaultdict(int)
    flg = 0
    for ai in a:
        tmp = []
        if d[ai] == -1:
            res[ai] = 1
            tmp = [ai]
        else:
            while d[ai] != -1:
                tmp.append(d[ai])
                ai = ai // d[ai]
        for t in set(tmp):
            if res[t]:
                flg = 1
            res[t] = 1
        if flg:
            break
    else:
        print("pairwise coprime")
        return
    g = a[0]
    for i in a:
        g = math.gcd(g, i)
    if g == 1 or x == 0:
        print("setwise coprime")
        return
    print("not coprime")
    
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math as mt
n=int(input())
l=list(map(int,input().split()))
gd=l[0]
sv=[0]*(10**6+1)
for i in range(2,len(sv)):
  if not sv[i]:
    sv[i]=i
    for j in range(2*i,len(sv),i):
      sv[j]=i
an="not coprime"
for i in range(n):
      gd=mt.gcd(gd,l[i])
if gd!=1:
	print(an)
else:
    an="setwise coprime"
    pos=1
    vis=[0]*(10**6+2)
    for i in range(n):
      cr=l[i]
      while cr>1:
          dv=sv[cr]
          if vis[dv]:
            pos=0;break
          while cr%dv==0:
            cr//=dv
          vis[dv]=1
    if pos:
      an="pairwise coprime"
    print(an)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
g = a[0]
for i in range(n):
    g = math.gcd(g, a[i])
if g != 1:
    print('not coprime')
    quit()
p = [0] * (10**6+1)
prime = []
cnt = 0
for i in range(2, 10**6 + 1):
    if p[i] == 0:
        prime.append(i)
        cnt += 1
        for j in range(i, 10**6 + 1, i):
            p[j] += 1

tmp = [0] * (10**6 + 1)
for i in range(n):
    tmp[a[i]] = 1
for i in prime:
    cnt = 0
    for j in range(i, 10**6+1, i):
        if tmp[j]:
            cnt += 1
    if cnt > 1:
        print('setwise coprime')
        quit()
print('pairwise coprime')

Submission status: Accepted

Solution code:
import math
n = int(input())
lis = list(map(int,input().split()))
lis.sort()
num = lis[0]
for nu in lis:
    num = math.gcd(num,nu)
exist = [0 for i in range(10**6+1)]
if num != 1:
    print("not coprime")
    exit()
for nu in lis:
    if nu != 1:
        for i in range(2,math.ceil(math.sqrt(nu))+1):
            if nu % i == 0:
                if exist[i] == 1:
                    print("setwise coprime")
                    exit()
                else:
                    exist[i] = 1
                    while nu % i == 0:
                        nu //= i
        if nu != 1:
            if exist[nu] == 1:
                print("setwise coprime")
                exit()
            exist[nu] = 1
print("pairwise coprime")

Submission status: Accepted

Solution code:

max_val = int(1e+6+1)
def make_kago(x):
    kago = [0 for _ in range(x+1)]
    sosuu = []
    for i in range(2,x+1):
        if kago[i] != 0:
            continue
        sosuu.append(i)
        for j in range(i, x+1, i):
            if kago[j] == 0:
                kago[j] = i
    return kago, sosuu

kago, sosuu = make_kago(max_val)

def prime_factorization(x):
    if x==0:
        return None
    soinsuu = []
    while x!=1:
        soinsuu.append(kago[int(x)])
        x = x/kago[int(x)]
    
    soinsuu_dict = dict()
    for i in range(len(soinsuu)):
        if soinsuu[i] not in soinsuu_dict:
            soinsuu_dict[soinsuu[i]] = 1
        else:
            soinsuu_dict[soinsuu[i]]+=1
    return soinsuu_dict

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

exists = [0 for _ in range(int(1e+6+1))]

complete_ok = True
exist_one = False

for i, A in enumerate(As):
    if A == 1:
        continue
    soinsuu_dict = prime_factorization(A)
    keys = list(soinsuu_dict.keys())
    for key in keys:
        if exists[key] != 0:
            complete_ok = False
        exists[key] += 1

part_ok = False
for i in range(len(exists)):
    if exists[i] == len(As):
        part_ok = True

if complete_ok == True:
    print("pairwise coprime")
elif part_ok == False:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
#素因数分解
def Prime_Factorization(N):
    if N<0:
        R=[[-1,1]]
    else:
        R=[]

    N=abs(N)
    k=2
    while k*k<=N:
        if N%k==0:
            C=0
            while N%k==0:
                C+=1
                N//=k
            R.append([k,C])
        k+=1

    if N!=1:
        R.append([N,1])
    if not R:
        R.append([N,1])

    return R
#================================================
from math import gcd
N=int(input())
A=list(map(int,input().split()))

#Pairwise?
P=set()
F=True
for a in A:
    K=Prime_Factorization(a)
    for (p,_) in K:
        if p in P and p!=1:
            F=False
            break
        else:
            P.add(p)

    if not F:
        break

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

#Setwise?
g=A[0]
for a in A:
    g=gcd(g,a)

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