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 numpy as np
N=int(input())
A=list(map(int,input().split()))
cnt=[0]*(10**6+1)
for a in A:cnt[a]+=1

if np.gcd.reduce(A)!=1:
  print("not coprime")
elif np.all([sum(cnt[i::i])<=1 for i in range(2,10**6+1)]):
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Accepted

Solution code:
def main():
    from math import gcd
    MINFact = [-1] * (10**6 + 10)
    MINFact[0] = 0
    MINFact[1] = 1

    def Eratosthenes(sup: int) -> set:
        primes = [True for i in range(sup+1)]
        primes[0] = False
        primes[1] = False
        for i in range(2, sup+1):
            if primes[i]:
                MINFact[i] = i
                mul = 2
                while i*mul <= sup:
                    primes[i*mul] = False
                    if MINFact[i*mul] == -1:
                        MINFact[i*mul] = i
                    mul += 1

    def prime_factor(n):
        while n != 1:
            prime = MINFact[n]
            while MINFact[n] == prime:
                n //= prime
            B[prime] += 1

    _ = int(input())
    A = [int(i) for i in input().split()]
    g = A[0]
    for a in A:
        g = gcd(g, a)
    Eratosthenes(10**6 + 5)
    B = [0]*(10**6 + 5)
    for a in A:
        prime_factor(a)
    # 素因数分解したのをBにいれる
    # 1より大きいのがあったら gcd != 1 のペアが存在する
    if g != 1:
        print("not coprime")
    elif max(B) <= 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def prime(n):
    nums = [True]*n
    primes = []
    for i in range(2,n):
        if nums[i]:
            primes.append(i)
            for j in range(2*i,n,i):
                nums[j] = False
    return primes

def main():
    n = int(input())
    Alist = list(map(int,input().split()))
    A = set(Alist)

    Amax = max(A)
    primes = set(prime(Amax+1))
    ct = 1
    if (1 not in A and len(A) != n) or (1 in A and len(A)-1 != n-Alist.count(1)):
        ct = 2
    for p in primes:
        g = set(())
        temp = p
        while temp <= Amax:
            g.add(temp)
            temp+=p
        
        k = len(g & A)
        if k > ct:
            ct = k
    

    if (1 not in A) and (len(A)==1 or ct == len(A)):
        print("not coprime")
    elif ct == 1 or A=={1}:
        print("pairwise coprime")
    else:
        print("setwise coprime")
main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
import math
import bisect
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
if A==[1]*N:
  print('pairwise coprime')
  exit()
a=A[0]
d=a
if A[0]!=1:
  D={}
  x=0
  for i in range(N):
    if d!=1:
      d=math.gcd(d,A[i])
    c=A[i]
    if x==0:
      F=factorization(A[i])
      for a,b in F:
        if a not in D:
          D[a]=1
        else:
          x=1
        #互いに素じゃない二組がある  
    if x==1 and d==1:
      break

  if x==1 and d==1:
    print('setwise coprime')
  elif x==0 and d==1:
    print('pairwise coprime')
  else:
    print('not coprime')
else:
  l=bisect.bisect_right(A,1)
  A=A[l:]
  D={}
  x=0
  for i in range(len(A)):
    F=factorization(A[i])
    for a,b in F:
      if a not in D:
        D[a]=1
      else:
        x=1
    if x==1:
      break
    
  if x==1:
    print('setwise coprime')
  else:
    print('pairwise coprime')

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	nn=II()
	A=LI()
	ans="pairwise coprime"

	n = 500005
	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=set(primes)

	#print(primes)


	B=set(range(1,5*10**5+5))
	C=set()
	for i in A:
		a=set()
		while i%2==0:
			a.add(2)
			i//=2
		f=3
		while f*f<=i:
			if i in primes:
				break
			elif i%f==0:
				a.add(f)
				i//=f
			else:
				f+=2
		if i!=1:
			a.add(i)
		B&=a
		if C&a:
			ans="setwise coprime"
		C|=a

	if B:
		ans="not coprime"

	print(ans)





















if __name__ == "__main__":
	main()

Submission status: Accepted

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


def func(A):
    is_A = [0] * (10**6+1)
    for a in A:
        is_A[a] += 1
    if any(x > 1 for x in is_A[2:]):
        return False
    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:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    targets = LI()
    MAX_INT = max(targets) + 1
    counter = cl.Counter(targets)
    targets = set(targets)
    is_pw = True

    num_1 = counter[1]
    if num_1 > 1:
        N -= num_1 - 1

    if len(targets) != N:
        is_pw = False

    if len(targets) == 1:
        if 1 in targets:
            print("pairwise coprime")
            return
        print("not coprime")
        return

    for i in range(2, MAX_INT):
        origin = i
        kosuu = 0
        while origin <= MAX_INT:
            if origin in targets:
                kosuu += 1
            origin += i

        if kosuu <= 1:
            continue
        elif kosuu < len(targets):
            is_pw = False
        else:
            print("not coprime")
            return

    if is_pw:
        print("pairwise coprime")
        return
    print("setwise coprime")


main()

Submission status: Accepted

Solution code:
import sys
import math

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def gcd(a, b):
	return math.gcd(a, b)
	
def is_pc(al):
	mm=((10**6)+5)
	dd = [0]* mm
	kk = [-1]* mm
	
	for v in al:
		dd[v] += 1
	
	for i, _ in enumerate(kk):
		if i <= 1:
			continue
		if kk[i]==-1:
			n=1
			nd = 0
			while i*n < mm:
				kk[i*n]=1
				nd += dd[i*n]
				n+=1
		if nd >= 2:
			return False
	return True

def main():
	n = int(input())
	#b , c = tin()
	#s = input()	
	al = lin()
	
	pc = 'pairwise coprime'
	sc = 'setwise coprime'
	nc = 'not coprime'
	if is_pc(al):
		return pc
	v=al[0]
	for vv in al:
		v = gcd(v, vv)
	if v == 1:
		return sc
	return nc
	
				
		
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import copy

def resolve():
    readline=sys.stdin.readline
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    n=len(arr)
    be=[0]*(10**6+1)
    xxx=n
    for i in range(n):
        be[arr[i]]+=1
    is1=True
    is2=True
    for i in range(2,10**6+1):
        x = i
        found=0
        while x <= 10**6:
            found+=be[x]
            x += i
        if found >= 2:
            is1=False
        if found == xxx:
            is2=False
    if is1==True:
        print("pairwise coprime")
    elif is2==True:
        print("setwise coprime")
    else:
        print("not coprime")

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

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

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

ps = set()
for i,m in enumerate(sieve_eratosthenes(1000000)):
    if m == 1:
        ps.add(i)

from collections import defaultdict
import math

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
one = False
for i in range(n):
    if a[-1] == 1:
        a.pop()
        one = True
        n -= 1
    else:
        break

if n==0 or n==1:
    print("pairwise coprime")
    exit()

a.sort()

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

if g == 1:
    if n > len(ps):
        print("setwise coprime")
    else:
        d = defaultdict(int)
        for i in range(n):
            f = factorization(a[i])
            for x, y in f:
                d[x] += 1
        for i in d.values():
            if i != 1:
                print("setwise coprime")
                exit()
        print("pairwise coprime")

else:
    if one:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

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


def judge_pairwise(array):
    prime_set = set()
    for num in array:
        if num == 1:
            continue

        if num in prime_set:
            return False

        for div in range(2, int(num ** 0.5) + 1):
            if num % div == 0:
                while num % div == 0:
                    num //= div
                if div in prime_set:
                    return False
                else:
                    prime_set.add(div)

        if num != 1:
            if num in prime_set:
                return False
            else:
                prime_set.add(num)

    return True


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

pairwiseFlag = judge_pairwise(a)

total = a[0]
for num in a:
    total = gcd(total, num)
if total == 1:
    setwiseFlag = True
else:
    setwiseFlag = False

if pairwiseFlag is True:
    print("pairwise coprime")
elif setwiseFlag is True:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = set()
for i in a:
    if i==1:
        continue
    ns = set()
    for j in range(2, 10**3):
        if i%j!=0:
            continue
        while i%j==0:
            i//=j
        ns.add(j)
        if i==1:
            break
    else:
        ns.add(i)
    if len(ns&s)>0:
        break
    s |= ns
else:
    print('pairwise coprime')
    exit(0)

def gcd_base(a, b):
    while b!=0:
        a, b = b, a%b
    return a

def gcd(num_list):
    ans = 0
    for i in num_list:
        ans = gcd_base(ans, i)
    return ans

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

Submission status: Accepted

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

def get_count(p):
  integers = [1 for _ in range(p+1)]
  integers[0] = 0
  integers[1] = 0
  counts = [0 for _ in range(p+1)]
  for a in A:
    counts[a] += 1
  answer = 0
  for i in range(p+1):
    if integers[i] >= 1:
      count = 0
      for j in range(i,p+1,i):
        count += counts[j]
        integers[j] = 0
      answer = max(answer,count)
  return answer

count = get_count(max(A))
if count == N:
  answer = 'not coprime'
elif count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

Submission status: Accepted

Solution code:
import math
from functools import reduce

def gcd_list(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=list(map(int, input().split(" ")))
check = [False for i in range(10 ** 6 + 1)]
pairwise = True
for i in a:
  temp = (factorization(i))
  for j, _ in temp:
    if temp == [[1, 1]]:
      continue
    if check[j] == True:
      pairwise = False
      break
    else:
      check[j] = True
  else:
    continue
  break
if pairwise:
  print("pairwise coprime")
else:
  if gcd_list(a) == 1:
    print("setwise coprime")
  else:
    print("not coprime")

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n=I()
    lis=LI()
    nums=[i for i in range(10**6+1)]
    spf=[-1 for i in range(10**6+1)]
    i=2
    while i<=10**3:
        if spf[i]>=0:
            i+=1
        for j in range(1,(10**6)//i+1):
            if spf[i*j]==-1:
                spf[i*j]=i
        i+=1
    #print(spf[10**5:10**5+100])
    for i in range(10**6+1):
        if spf[i]<0:
            spf[i]=i
    #print(spf[10**5:10**5+100])
    dic=defaultdict(lambda :0)
    for i in range(n):
        x=lis[i]
        key=set()
        while x>1:
            u=spf[x]
            x//=u
            key.add(u)
        for z in key:
            dic[z]+=1
    flag=True
    #print(dic)
    for z in dic.keys():
        if dic[z]==n:
            print("not coprime")
            sys.exit()
        if dic[z]>1:
            flag=False
        
    if flag==True:
        print("pairwise coprime")
        sys.exit()
    print("setwise coprime")
                
        
            
        
            
            

            
            
            

    
            
            
            
            
        
        
        
    
        
            
        
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
max_A = max(A)
# happend_numbers = [False]*(max_A+1)  # 0~NのN+1個
happend_numbers = defaultdict(int)
for a in A:
    happend_numbers[a] += 1
    # happend_numbers[a] = True

for i in range(2, max_A+1):
    true_count = 0
    for j in range(i, max_A+1, i):
        # if happend_numbers[j]:
        true_count += happend_numbers[j]
    if true_count >= 2:
        break
else:
    print("pairwise coprime")
    exit()

now = A[0]
for a in A[1:]:
    now = gcd(a, now)
if now == 1:
    print("setwise coprime")
    exit()
print("not coprime")

Submission status: Accepted

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

  divisors.sort()
  divisors.pop(0)
  return divisors

def is_prime(n):
  for i in range(2, n + 1):
    if i * i > n:
      break
    if n % i == 0:
      return False
  return n != 1

N = input()
A = list(map(int, input().split()))
A = sorted(A)
gcd = functools.reduce(math.gcd, A)

dp = []
if 2 <= gcd:
  print("not coprime")
else:
  isPC = True
  for a in A:
    if is_prime(a):
      dp.append(a)
    else:
      divs = make_divisors(a)
      for d in divs:
        if d in dp:
          isPC = False
          break
        dp.append(d)

    if not isPC:
      break
  if isPC:
    print("pairwise coprime")
  else:
    print("setwise coprime")

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, As):
    import math
    primes = [0] * (max(As) + 1)
    pairwise_flg = True
    for x in As:
        i = 2
        while x != 1:
            if x % i == 0:
                if primes[i] != 0:
                    pairwise_flg = False
                    break
                primes[i] = 1
                while x % i == 0:
                    x = x // i
            else:
                i += 1
                if i > math.sqrt(x):
                    if primes[x] != 0:
                        pairwise_flg = False
                    else:
                        primes[x] = 1
                    break
        if not pairwise_flg:
            break
    if pairwise_flg:
        print('pairwise coprime')
        return

    tmp = math.gcd(As[0], As[1])
    for A in As:
        tmp = math.gcd(tmp, A)
    if tmp == 1:
        print('setwise coprime')
        return

    print('not coprime')


if __name__ == '__main__':
    N = int(input())
    As = [int(i) for i in input().split()]
    # # test
    # import random
    # N = 10 ** 6
    # As = [random.randint(1, 10 ** 6) for _ in range(N)]
    solve(N, As)

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce

def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        result.append((p, e))
    return result


def f():
    s = set()
    for i in range(N - 1, -1, -1):
        t = prime_factorize(A[i])
        for p, _ in t:
            if p in s:
                return False
            s.add(p)
    return True


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

prime_table = make_prime_table(10 ** 6)
if f():
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import math

def main():
    N = int(input())
    As = list(map(int, input().split()))
    pairwise_flag = True
    setwise_flag = True
    cnt_not1 = 0
    for a in As:
        if a > 1:
            cnt_not1 += 1
    if cnt_not1 > 78498:
        pairwise_flag = False
    
    L = 1000 + 1
    isPrime = [True] * L
    isPrime[0] = isPrime[1] = False
    primes = []
    for n in range(2, L):
        if isPrime[n]:
            primes.append(n)
            isPrime[2*n::n] = [False] * ((L-n-1) // n)

    or_factor = 0
    or_factor_over1000 = set()
    all_gcd = None
    for i, a in enumerate(As):
        digit = 1
        factor = 0
        x = a
        if pairwise_flag:
            for p in primes:
                if p > x:
                    break
                if x % p == 0:
                    factor += digit
                    x //= p

                while x % p == 0:
                    x //= p
                digit <<= 1

        if i > 0:
            all_gcd = math.gcd(all_gcd, a)
            if pairwise_flag:
                if or_factor & factor:
                    pairwise_flag = False
                or_factor |= factor
                if x > 1:
                    if x in or_factor_over1000:
                        pairwise_flag = False
                    or_factor_over1000.add(x)
        else:
            all_gcd = a
            or_factor |= factor
            if x > 1:
                or_factor_over1000.add(x)
    if pairwise_flag:
        print('pairwise coprime')
    elif all_gcd > 1:
        print('not coprime')
    else:
        print('setwise coprime')

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    maxA = max(A)
    if maxA == 1:
        print('pairwise coprime')
        return
    prime = [i % 2 != 0 for i in range(maxA+1)]
    prime[2] = True
    f = [False] * (maxA+1)
    for i in range(3, int(maxA**.5)+1):
        if prime[i] == False:
            continue
        p = i * 2
        while p <= maxA:
            prime[p] = False
            p += i

    def gcd(x, y):
        if y == 0:
            return x
        return gcd(y, x % y)

    pairwise_coprime = A[0]
    setwise_coprime = A[0]
    for An in A[1:]:
        setwise_coprime = gcd(setwise_coprime, An)
        if setwise_coprime == 1:
            break
    
    for An in A:
        if An == 1:
            continue
        # print('An = {}'.format(An))
        if f[An]:
            if setwise_coprime == 1:
                print('setwise coprime')
                return
            else:
                print('not coprime')
                return
        elif prime[An]:
            f[An] = True
        else:
            for i in range(2, An // 2 + 1):
                if prime[An]:
                    if f[An]:
                        if setwise_coprime == 1:
                            print('setwise coprime')
                            return
                        else:
                            print('not coprime')
                            return
                    else:
                        f[An] = True
                        break
                if f[An]:
                    if setwise_coprime == 1:
                        print('setwise coprime')
                        return
                    else:
                        print('not coprime')
                        return
                elif An % i == 0:
                    # print('i={}'.format(i))
                    if f[i]:
                        if setwise_coprime == 1:
                            print('setwise coprime')
                            return
                        else:
                            print('not coprime')
                            return
                    f[i] = True
                    while An % i == 0:
                        An //= i
                    if An == 1:
                        break
        # print(f)
    print('pairwise coprime')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import time
A=time.time()
p=[1 for i in range(1001)]
p[0]=0
p[1]=0
for i in range(2,1001):
    if p[i]==1:
        for j in range(2,1001):
            if i*j<=1000:
                p[i*j]=0
#print(p[:25])
Prime=[]
for i in range(1001):
    if p[i]==1:
        Prime.append(i)

#print(Prime)
#print(len(Prime))
N=int(input())
L=list(map(int,input().split()))

def gcd(a,b):
    if b>a:
        a,b=b,a
    while a%b!=0:
        a,b=b,a%b
    return b
    
X=L[0]
for i in range(1,N):
    X=gcd(X,L[i])
    if X==1:
        break
if X>1:
    print("not coprime")
    exit()
        
D={}

for I in L:
    B=time.time()
    if B-A>1.9:
        print("pairwise coprime")
        exit()
    for j in Prime:
        if I%j==0:
            if j not in D:
                D[j]=1
            else:
                print("setwise coprime")
                exit()
            while I%j==0:
                I//=j
    if I!=1:
        if I not in D:
            D[I]=1
        else:
            print("setwise coprime")
            exit()
#print(D)

print("pairwise coprime")

Submission status: Accepted

Solution code:
def prime(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
pp=prime(10**3)
p=[]
for i in range(2,1001):
  if pp[i]:
    p.append(i)
n=int(input())
a=list(map(int,input().split()))
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

g=a[0]
for i in a[1:]:
  g=gcd(g,i)
if g==1:
  mm=[0 for i in range(10**6+1)]
  f=True
  for i in a:
    if mm[i] and i!=1:
      f=False
      break
    mm[i]=1
    si=i**0.5
    for j in range(168):
      if p[j]>si:
        break
      if i%p[j]==0 and i!=p[j]:
        if mm[p[j]]:
          f=False
          break
        mm[p[j]]=1
        t=i//p[j]
        if mm[t] and t!=p[j]:
          f=False
          break
        mm[t]=1
    if not f:
      break
  if f:
    print("pairwise coprime")
  else:
    print("setwise coprime")
else:
  print("not coprime")

Submission status: Accepted

Solution code:
from functools import reduce
import math
def gcd(x,y):
    if x%y==0:
        return y
    else:
        return (gcd(y, x%y))

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

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

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

    return arr

def ans(n, a):
    div = {}
    for i in range(n):
        k = (factorization(a[i]))
        for j in k:
            if j==1:
                pass
            elif j not in div:
                div[j]=1
            else:
                return True
    return False
    

n = int(input())
a = list(map(int, input().split()))
gcd = reduce(math.gcd, a)
if gcd !=1:
    print("not coprime")
else:
    if ans(n, a):
        print("setwise coprime")
    else:
        print("pairwise coprime")

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().rstrip()

def euc(a,b):

    while b!=0:
        a,b =b,a%b

    return a

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

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

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



def main():

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

    PS =set()

    current =A[0]
    for i in range(N-1):
        current =euc(current,A[i+1])
        if current ==1:
            break

    else:
        print("not coprime")
        exit()


    for i in range(N):
        if A[i]==1:
            continue
        aa =factorization(A[i])
        for i in aa:
            if i in PS:
                print("setwise coprime")
                exit()
            else:
                PS.add(i)

    print("pairwise coprime")
    exit()



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
N = int(input())
A = list(map(int, input().split()))
A_max = max(A)
if A_max == 1:
    print("pairwise coprime")
    sys.exit()
dp = [0]*(A_max+10)
K = [0]*(A_max+10)
p = 0
s = 0
for i in range(N):
    K[A[i]] += 1
for i in range(2, A_max+1):
    c = 0
    if dp[i] == 0:
        dp[i] = 1
        for j in range(i, A_max+1, i):
            dp[j] = 1
            c += K[j]
        if c >= 2:
            p = 1
        if c == N:
            s = 1
if p == 0:
    print("pairwise coprime")
elif s == 0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from collections import Counter 
import sys

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

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

A.sort()
if A[0] != 1:
    d = prime_factorize(A[0])
    dlist = list(Counter(d).keys())
    for i in dlist:
        for j in range(1,N):
            if A[j] % i != 0:
                break
            if j == N-1:
                print("not coprime")
                sys.exit()


cnt = [0] * (10 ** 6)
for i in A:
    a = prime_factorize(i)
    alist = list(Counter(a).keys())
    for j in alist:
        cnt[j] += 1
        if cnt[j] >= 2:
            print("setwise coprime")
            sys.exit()

print("pairwise coprime")