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.

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): 
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    

    N = int(input())
    
    A = tuple(map(int, input().split())) 
    
    
    tot=0
    def primes(n):
        a = set()
        while n % 2 == 0:
            a.add(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.add(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.add(n)
        return a

    for a in A:
        tot=math.gcd(tot,a)
    if tot!=1:
        print("not coprime")
        return
    
    
    
    

    
    
    

    cur=set()
    for a in A:
        s=primes(a)
        if len(s&cur)!=0:
            print("setwise coprime")
            return 
        cur|=s

    print("pairwise coprime")


if __name__ == "__main__":
    main()

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

M = max(A)




P = [1 for i in range(M+1)]
for i in range(2, M+1):
    if P[i] == 1:
        for j in range(i, M+1, i):
            if P[j] == 1:
                P[j] = i
dic = {}
for a in A:
  t_dic = {}
  x = a
  while x > 1:
    if P[x] in t_dic:
      t_dic[ P[x] ] += 1
    else:
      t_dic[ P[x] ] = 1    
    x //= P[x]
  for k in t_dic.keys():
    if k in dic:
      dic[k] += 1
    else:
      dic[k] = 1

c = 0
for v in dic.values():
  c = max(c, v)

if c == len(A):
  print("not coprime")
elif c < 2:
  print("pairwise coprime")
else:
  print("setwise coprime")

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
M = max(A) + 1

counts = [0 for _ in range(M)]
for a in A:
  counts[a] += 1

integers = [1 for _ in range(M)]
integers[0] = 0
integers[1] = 0
max_count = 0
for i in range(M):
   if integers[i] >= 1:
    count = 0
    for j in range(i,M,i):
      count += counts[j]
      integers[j] = 0
    max_count = max(max_count,count)

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

Solution (Python):


import sys
from math import gcd
from collections import Counter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

dup = False
dup_key = None
counter = Counter(A)
for key, val in counter.items():
    if val > 1:
        dup = True
        if dup_key is None:
            dup_key = key
        else:
            dup_key = max(dup_key, key)


def max_gcd_pair(S):
    
    
    s = set(S)
    m = max(S)
    res = 1
    i = m
    while i > 0:
        a = i
        cnt = 0
        while a <= m: 
            if a in s:
                cnt += 1
            a += i
        if cnt >= 2:  
            res = i
            break
        i = i - 1
    return res


pair = max_gcd_pair(A)
if dup:
    pair *= dup_key

if pair == 1:
    print('pairwise coprime')
    sys.exit()


setw = A[0]
for j in range(N):
    setw = gcd(setw, A[j])
if setw == 1:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
import math
import collections
def main():

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

    d = dict()
    def prime_factor(n):
        if n % 2 == 0: d[2] = d.get(2, 0) + 1
        while n % 2 == 0:
            n //= 2

        i = 3
        while i * i <= n:
            if n % i == 0:
                d[i] = d.get(i, 0) + 1
            while n % i == 0:
                n //= i
            i += 2
        if n > 1:
            d[n] = d.get(n, 0) + 1
        return

    ispair = True
    isset = True

    d = dict()
    for v in A: prime_factor(v)
    

    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"

    return "not coprime"

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 1

counts = [0 for _ in range(M)]
for a in A:
  counts[a] += 1

integers = [1 for _ in range(M)]
integers[0] = 0
integers[1] = 0
max_count = 0
for i in range(M):
   if integers[i] >= 1:
    count = 0
    for j in range(i,M,i):
      count += counts[j]
      integers[j] = 0
    max_count = max(max_count,count)

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

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

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

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

    return arr
    
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a 
def multiple_gcd(a):
    ans = a[0]
    for i in range(1, len(a)):
        ans = gcd(ans, a[i])
    return ans

def pairwise_coprime_gcd():
    for i in range(N-1):
        for j in range(i+1, N):
            if gcd(A[i], A[j]) != 1:
                return 0
    return 1
def pairwise_coprime(A):
    prime = set()
    for i in range(N):
        fact = factorization(A[i])
        for x in fact:
            if x[0] in prime:
                return 0
            if x[0] != 1:
                prime.add(x[0])
    return 1

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

if pairwise_coprime(A) == 1:
    print('pairwise coprime')
elif multiple_gcd(A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

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

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

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

f = True
l = set()
for i in a:
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            if i in l:
                f = False
                break
            l.add(i)
        while i%j==0:
            i = i//j
        if i<2:
            break
    if i>1:
        if i in l:
            f = False
            break
        l.add(i)
        
if f:
    print('pairwise coprime')
else:
    print('setwise coprime')

Solution (Python):
from math import gcd
from functools import reduce
N = int(input())
*A, = map(int, input().split())

MAX_N = max(A)+5
primes = list(range(MAX_N+1))
for i in range(2, int(MAX_N**0.5)+1):
    if primes[i] < i:
        continue
    for j in range(2*i, MAX_N+1, i):
        primes[j] = i


def check():
    S = set()
    for a in A:
        T = set()
        while True:
            p = primes[a]
            if p != 1 and p in S:
                return False
            T.add(p)
            if p == a:
                break
            a //= p
        S |= T
    return True


if check() or all(a == 1 for a in A):
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
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):
        t = prime_factorize(A[i])
        for p, _ in t:
            if p in s:
                return False
            s.add(p)
    return True


N=int(input())
A=list(map(int, input().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')

Solution (Python):
from math import gcd


def eratosthenes(n):
    prime = []
    data = [i for i in range(2, n + 1)]
    while True:
        p = data[0]
        if n <= p ** 2:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return data


def factorize(N):  
    prime = set()
    for p in prime_list:
        if p * p > N:
            break
        while N % p == 0:
            N //= p
            prime.add(p)
    if N > 1:
        prime.add(N)
    return prime


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

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

prime_list = eratosthenes(10 ** 6)
num = set()
for ai in a:
    prime = factorize(ai)
    if len(prime & num) > 0:
        print('setwise coprime')
        break
    num |= prime
else:
    print('pairwise coprime')

Solution (Python):
N = int(input())
A = [int(s) for s in input().split()]

PRIME_LENGTH = (10**6 + 1)

prime_list = [[] for _ in range(PRIME_LENGTH)]

for i in range(2, PRIME_LENGTH):
    if not prime_list[i]:
        idx = i
        while (idx < PRIME_LENGTH):
            prime_list[idx].append(i)
            idx += i

vote = [0] * (PRIME_LENGTH)

for a in A:
    for v in prime_list[a]:
        vote[v] += 1

if max(vote) == len(A):
    print("not coprime")
elif sum(map(lambda x: x > 1, vote)) > 0:
    print("setwise coprime")
else:
    print("pairwise coprime")

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


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


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

    
    

    return arr






gcdall = A[0]
for i in range(1, N):
    gcdall = gcd(gcdall, A[i])


if gcdall > 1:
    print("not coprime")
    exit()

MAX = 10 ** 6 + 1
num = [False] * MAX
A = sorted(A)[::-1]
primeset = set()
for a in A:
    if a == 1:
        continue
    if num[a]:
        print("setwise coprime")
        exit()
    fact = factorization(a)
    for p, nn in fact:
        if p == 1:
            continue
        if p in primeset:
            continue
        primeset.add(p)
        for j in range(p, MAX, p):
            num[j] = True

print("pairwise coprime")

Solution (Python):
import os
import sys
from math import gcd

import numpy as np


def solve(inp):
    n = inp[0]
    aaa = inp[1:]

    g = 0
    for i in range(n):
        g = gcd(g, aaa[i])
    if g != 1:
        return -1

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

    one_count = (aaa == 1).sum()
    val = set(aaa)
    if len(val) + max(0, one_count - 1) < n:
        return 0

    for p in PRIMES:
        multiple_count = 0
        for a in val:
            b = a
            if b % p == 0:
                multiple_count += 1
                b //= p
                while b % p == 0:
                    b //= p
                if b == 1:
                    val.remove(a)
                else:
                    if b in val:
                        return 0
                    val.remove(a)
                    val.add(b)

        if multiple_count > 1:
            return 0

    return 1


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(['setwise coprime', 'pairwise coprime', 'not coprime'][ans])

Solution (Python):
from math import gcd

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]]


def main():
    n = int(input())
    al = list(map(int, input().split()))
    als = [0]*(10**6+1)
    for a in al:
        als[a] += 1

    ps = primes(10**6)
    for p in ps:
        cnt = 0
        for i in range(p,10**6+1,p):
            cnt += als[i]
        if cnt >= 2:
            break
    else:
        print('pairwise coprime')
        exit() 

    c_gcd = al[0]
    for a in al[1:]:
        c_gcd = gcd(c_gcd,a)
    
    if c_gcd == 1:
        print('setwise coprime')
    else:
        print('not coprime')


    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    

    
    
    
    
    
    
    
    
    
    
    



if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
input = sys.stdin.readline

from collections import Counter

class Osa_k:
    def __init__(self, n):
        self.n = n
        self.min_factor = [int(x) for x in range(n+1)]
        
        self.is_prime = [True] * (self.n + 1)
        self.is_prime[0] = False
        self.is_prime[1] = False
        for j in range(4, self.n+1, 2):
            self.is_prime[j] = False
            self.min_factor[j] = 2
        for i in range(3, int(self.n**0.5) + 1, 2):
            if not self.is_prime[i]:
                continue
            for j in range(i * 2, self.n + 1, i):
                self.is_prime[j] = False
                if self.min_factor[j] >= i:
                    self.min_factor[j] = i
    
    def calulate(self, x):
        ans = []
        while x > 1:
            key = self.min_factor[x]
            while x%key == 0:
                ans.append(key)
                x //= key
        counter = set(ans)
        return counter
        

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    key = a[0]
    sc = False
    for i in range(1, n):
        key = math.gcd(key, a[i])
    
    if key == 1:
        sc = True
    
    
    pc = True
    osak = Osa_k(10**6+1)
    
    sub = set()
    
    judge = dict()
    for i in range(n):
        key = osak.calulate(a[i])
        for v in key:
            if v in judge:
                pc = False
            judge[v] = 1
            
    
    if pc:
        print("pairwise coprime")
    elif sc:
        print("setwise coprime")
    else:
        print("not coprime")

    
    
    
    
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np

input = sys.stdin.buffer.readline


def primes_np(n):
    is_prime = np.ones(n + 1, dtype=bool)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        is_prime[i * 2:n + 1:i] = False
    return np.where(is_prime)[0].tolist()


N = int(input())
A = tuple(map(int, input().split()))
MAX = 10 ** 6


def pairwise(A):
    table = [0] * (10 ** 6 + 1)
    for a in A:
        table[a] += 1
    for p in primes_np(MAX):
        ct = 0
        for i in range(p, MAX + 1, p):
            ct += table[i]
        if ct > 1:
            return False
    return True


def setwise(A):
    return np.gcd.reduce(A) == 1


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

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


N = I()
A = LI()

from math import gcd

g = 0  
for i in range(N):
    g = gcd(g,A[i])

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

B = []
for i in range(N):
    if A[i] != 1:
        B.append(A[i])
N = len(B)


if N == 0:
    print('pairwise coprime')
    exit()

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


if N > 78498:  
    print('setwise coprime')
    exit()

C = [0]*(10**6+1)  

for i in range(N):
    b = B[i]
    for p in primes:
        if b % p == 0:
            if C[p] == 1:
                print('setwise coprime')
                exit()
            else:
                C[p] = 1
            while b % p == 0:
                b //= p
    if b != 1:
        if C[b] == 1:
            print('setwise coprime')
            exit()
        else:
            C[b] = 1

print('pairwise coprime')

Solution (Python):
N = int(input())
from math import gcd
prime = [0] * 2 + [1] * (10 ** 6 - 1)
A = list(map(int, input().split()))
A.sort()
g = 0
for a in A:
  g = gcd(g, a)
for i in range(2, 10 ** 2 + 1):
  if prime[i]:
    for j in range(2 * i, 10 ** 3 + 1, i):
      prime[j] = 0
P = [i for i in range(2, 10 ** 3 + 1) if prime[i]]
from bisect import bisect
A = A[bisect(A, 1):]
N = len(A)
x = [0] * (10 ** 6 + 1)
if N <= 80000:
  for a in A:
    for p in P:
      if a % p == 0:
        x[p] += 1
        while a % p == 0:
          a //= p
      if a == 1:
        break
    if a > 1:
      x[a] += 1
  if max(x) < 2:
    print('pairwise coprime')
    exit()
if g == 1:
  print('setwise coprime')
  
else:
  print('not coprime')

Solution (Python):
from collections import Counter


def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)


def check_pairwise_coprime(a):
    m = max(a)
    cnt_a = Counter(a)
    is_prime = [True] * (m + 1)
    for i in range(2, m // 2 + 1):
        if is_prime[i]:
            cnt = cnt_a[i]
            for j in range(2, m // i + 1):
                cnt += cnt_a[i * j]
                is_prime[i * j] = False
            if cnt > 1:
                return False
    return True


def check_setwise_coprime(a):
    gcd_all = a[0]
    for i in range(1, n):
        gcd_all = GCD(gcd_all, a[i])
    return gcd_all == 1


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

if check_pairwise_coprime(a):
    print('pairwise coprime')
elif check_setwise_coprime(a):
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
from collections import Counter


def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)


def check_pairwise_coprime(a):
    m = max(a)
    cnt_a = Counter(a)
    is_prime = [True] * (m + 1)
    for i in range(2, m // 2 + 1):
        if is_prime[i]:
            cnt = cnt_a[i]
            for j in range(2, m // i + 1):
                cnt += cnt_a[i * j]
                is_prime[i * j] = False
            if cnt > 1:
                return False
    return True


def check_setwise_coprime(a):
    gcd_all = a[0]
    for i in range(1, n):
        gcd_all = GCD(gcd_all, a[i])
    return gcd_all == 1


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

if check_pairwise_coprime(a):
    print('pairwise coprime')
elif check_setwise_coprime(a):
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
import sys
from functools import reduce
from operator import add


def _i(): return int(sys.stdin.readline().strip())


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


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


def main():
    n = _i()
    a = list(sorted(_ia()))
    r = a[0]
    for ai in a[1:]:
        r = gcd(r, ai)
        if r == 1:
            break
    else:
        return "not coprime"

    N = 10 ** 6 + 1
    f = [False] * N
    p = []
    k = {ai: 1 for ai in a}
    for i in range(2, N):
        if f[i]:
            continue
        p.append(i)

        tmp = 0
        if k.get(i) is not None:
            tmp += 1
        for j in range(2*i, N, i):
            f[j] = True
            if k.get(j) is not None:
                tmp += 1
                if tmp > 1:
                    return "setwise coprime"
    else:
        return "pairwise coprime"


if __name__ == "__main__":
    print(main())

Solution (Python):
n=int(input())
l=[*map(int,input().split())]
f=lambda p: exit(print(['pairwise','setwise','not'][p]+' coprime'))
from math import *
g=l[0]
for x in l: g=gcd(g,x)
if g>1: f(2)
from collections import *
C=Counter()
for x in l:
  for i in range(2,int(x**0.5)+1):
    if x%i<1:
      if C[i]: f(1)
      C[i]=1
    while x%i<1: x//=i
    if x<2: break
  if x>1:
    if C[x]: f(1)
    C[x]=1
f(0)

Solution (Python):
import sys
import math

def soinsu(dic, x):
  i = 2
  while i*i <= x:
    if x % i == 0 and i in dic.keys():
      return False
    
    while x % i == 0:
      dic.setdefault(i, 0)
      dic[i] += 1
      x //= i
      
    i += 1
      
      
  if x == 1:
    return True
  
  if x in dic.keys():
    return False
  
  dic.setdefault(x, 1)
  return True
    

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

flag = False
for i in range(n):
  if not soinsu(dic, a[i]):
    flag = True
    break

if not flag:
  print("pairwise coprime")
  sys.exit()
  
tmp = a[0]
for i in range(1,n):
  tmp = math.gcd(tmp, a[i])
  
if tmp == 1:
  print("setwise coprime")
else:
  print("not coprime")

Solution (Python):
import sys
input = sys.stdin.buffer.readline




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




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

	n = 333335
	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)

	


	B=set(range(1,333335))
	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()

Solution (Python):
import sys

from collections import defaultdict
from functools import lru_cache


@lru_cache(None)
def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


def merge_dict(d1, d2):
    for k, v in d2.items():
        d1[k] += v
    return d1


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


def prime_factorization(N: int) -> dict:
    primes = defaultdict(int)
    primes[1] = 1
    if N < 2:
        return primes
    i = 2
    while i * i <= N:
        while N % i == 0:
            primes[i] += 1
            N = N // i
        i += 1
    if N != 1:
        primes[N] = 1
    return primes


def main():
    n = int(input())
    A = [int(i) for i in input().split()]
    primes = defaultdict(int)
    is_pair_gcd = True
    set_gcd = A[0]
    for i in range(n):
        set_gcd = gcd(set_gcd, A[i])
        if is_pair_gcd:
            p = prime_factorization(A[i])
            for k, v in p.items():
                if k == 1:
                    continue
                if k in primes.keys():
                    is_pair_gcd = False
                else:
                    primes[k] += v

    if is_pair_gcd:
        print("pairwise coprime")
        return

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

    return


if __name__ == "__main__":
    main()

Solution (Python):
import math

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

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 setwise_coprime(a):
    b=a.copy()
    one=b.pop()
    for i in range(n-1):
        two=b.pop()
        one=math.gcd(one,two)
    if one==1:
        return True
    return False

def pairwise_coprime(an):
    frui=[0]*(10**6+1)
    for a in an:
        if a==1:
            continue
        soinnsuu_list=factorization(a)
        for i in soinnsuu_list:
            if frui[i]==1:
                return False
            for k in range(1,int(10**6/i)+1):
                frui[i*k]=1
    return True


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

Solution (Python):
n = int(input())
*A, = map(int, input().split())

m = max(A)
is_prime = [True] * (m + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, m + 1):
    for j in range(i * 2, m + 1, i):
        is_prime[j] = False
primes = [i for i in range(m + 1) if is_prime[i]]

Amap = {a: 0 for a in range(1, m + 1)}
for a in A:
    Amap[a] += 1


Pmap = {p: 0 for p in primes}
for p in primes:
    for a in range(p, m + 1, p):
        Pmap[p] += Amap[a]

try:
    score = max(Pmap.values())
except BaseException:
    print('pairwise coprime')
    exit()
if score == 1:
    print('pairwise coprime')
elif score != n:
    print('setwise coprime')
else:
    print('not coprime')