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):
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def prime_factorize(n):
    '''
    素因数分解のリストを返す。n == 1のとき[]になるので注意。
    :param n:int
    素因数分解する自然数
    :return: list
    素因数分解した結果。

    例
    n : 10
    primes : [[2, 1], [5, 1]]
    '''
    primes = {}
    for i in range(2, int(n ** (1 / 2)) + 1):
        if n % i != 0:
            continue
        num = 0
        while n % i == 0:
            num += 1
            n //= i
        primes[i] = num
    if n != 1:
        primes[n] = 1
    return primes

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


pairwise = False
prime_key = set(prime_factorize(A[-1]).keys())
break_flag = False
prime_flags = [False] * (10 ** 6 + 1)
for i in range(N):
    for key in prime_factorize(A[i]).keys():
        if prime_flags[key]:
            break_flag = True
            break
        else:
            prime_flags[key] = True
    if break_flag:
        break
else:
    pairwise = True
if pairwise:
    print('pairwise coprime')
    exit()
work = gcd(A[0], A[1])
for i in range(2, N):
    work = gcd(work, A[i])
if work != 1:
    print('not coprime')
else:
    print('setwise coprime')

Solution (Python):
import math
 
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
 
input()
d = None
u = set()
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print((r, 'not')[d > 1], 'coprime')

Solution (Python):
import math


def get_pseudo_input():
    N = 3
    A = [6, 10, 16]
    return N, A


def get_input():
    N = int(input())
    A = [int(x) for x in input().split()]
    return N, A


def sieve_of_eratosthenes(x: int):
    ret = [-1] * (x + 1)
    for i in range(1, x + 1):
        ret[i] = i
    p_max = int(math.sqrt(x))
    for p in range(2, p_max + 1):
        if ret[p] < p:  
            continue
        for i in range(p, x + 1, p):
            if ret[i] > p:
                ret[i] = p
    return ret


A_max = 10 ** 6
p_table = sieve_of_eratosthenes(A_max)

N, A = get_input()

p_nums = [0] * (A_max + 1)
p_nums[1] = N
max_p_nums = 0
for a in A:
    
    while a > 1:
        p = p_table[a]
        while a % p == 0:
            a = a // p
        
        p_nums[p] += 1
        if max_p_nums < p_nums[p]:
            max_p_nums = p_nums[p]

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

Solution (Python):
import math

input()
a = *map(int, input().split()),
         
N = max(a) + 1
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
 
d = None
u = set()
for x in a:
  d = math.gcd(d or x, x)
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print((r, 'not')[d > 1], 'coprime')

Solution (Python):
from math import gcd
from math import floor
from collections import defaultdict

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

class PrimeFactorization:
    '''1つの因数分解クエリをO(log(k))で実行する（初期化にO(N))
    >>> pf = PrimeFactorization(100)
    >>> pf.query(100)
    ((2, 2), (5, 2))
    
    '''
    
    
    
    
    
    
    from collections import defaultdict
    def __init__(self, Num=10**6):
        self.Num = Num
        self.D = [-1] * (Num+1)
        for i in range(2, Num+1):
            if self.D[i] != -1:
                continue
            self.D[i] = i
            for j in range(1, floor(Num/i)+1):
                if self.D[j*i] != -1:
                    continue
                else:
                    self.D[j*i] = i
    
    def query(self, k):
        ans = defaultdict(int)
        tmp = k
        while self.D[tmp] != -1:
            div = self.D[tmp]
            ans[div] += 1
            tmp = tmp//div
        return set(ans.keys())
      
pf = PrimeFactorization(10**6)
for ai in a:
    prime = pf.query(ai)
    
    if len(prime & num) > 0:
        print('setwise coprime')
        break
    num |= prime
else:
    print('pairwise coprime')

Solution (Python):
import math
 
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
 
input()
d = None
u = set()
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print((r, 'not')[d > 1], 'coprime')

Solution (Python):
import math

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 factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

Ps = primes(10 ** 6)
n = int(input())
As = list(map(int, input().split()))


gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)


pairwiseFlag = True
target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target |= primes

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

Solution (Python):
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
def gcd(a, b):
    while b: a, b = b, a % b
    return a

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


pairwise = False
prime_key = set(primeFactor(A[-1]).keys())
break_flag = False
prime_flags = [False] * (10 ** 6 + 1)
for i in range(N):
    for key in primeFactor(A[i]).keys():
        if prime_flags[key]:
            break_flag = True
            break
        else:
            prime_flags[key] = True
    if break_flag:
        break
else:
    pairwise = True
if pairwise:
    print('pairwise coprime')
    exit()
work = gcd(A[0], A[1])
for i in range(2, N):
    work = gcd(work, A[i])
if work != 1:
    print('not coprime')
else:
    print('setwise coprime')

Solution (Python):
import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

cons = 10 ** 6
is_prime = [True] * (cons + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(cons**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, cons + 1, i):
        is_prime[j] = False
Ps = [i for i in range(cons + 1) if is_prime[i]]










def factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)

pairwiseFlag = True
target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target |= primes

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

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


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


j = 0
a1 = set()
a2 = prime_factorize(A[0])
for a in A[1:]:
    tmp = prime_factorize(a)
    if a1 & tmp:
        j = 1
    a1 |= tmp
    a2 &= tmp
if a2:
    print('not coprime')
elif j:
    print('setwise coprime')
else:
    print('pairwise coprime')

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

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

def factorize(n):
    d = set()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d.add(m)
        m += 1
    if n > 1:
        d.add(n)
    return d

st = set()
for a in A:
    fac = factorize(a)
    if fac & st:
        print('setwise coprime')
        exit()
    st |= fac
print('pairwise coprime')

Solution (Python):
import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()











def eratosthenes(n):
    is_prime = [0, 0] + [1] * (n - 1)
    for i in range(int(n**0.5) + 1):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return [i for i, pi in enumerate(is_prime) if pi == 1]
Ps = eratosthenes(10 ** 6)

def factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)

pairwiseFlag = True
target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target |= primes

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

Solution (Python):
from math import gcd
from functools import reduce
import numpy as np

PC = True

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

MAX = A[0]+1
mp = [0]*MAX

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

for i in range(2,MAX):
  if sum(mp[i::i])>1:
    PC = False
    break

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

Solution (Python):
from collections import defaultdict
import math

INF = 10 ** 6 + 1
is_prime = [1] * INF

def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return

def f(n):
    yakusu = []
    if is_prime[n]:
        yakusu.append(n)
    else:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                yakusu.append(i)
                if i != n //i:
                    yakusu.append(n // i)
                break

    for i in yakusu:
        if i != 1:
            d[i] += 1

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

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
    f(A[i])

if tmp != 1:
    print('not coprime')
    exit()
eratorasu()
f(A[0])

for i, v in d.items():
    if v != 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')

Solution (Python):
import math
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else 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, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
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()
    return divisors
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
mod = 10**9 + 7



n = ini()
a = inl()
A = 10**6+1
b = [0] * A
ans = "pairwise coprime"

for i in a: 
    b[i] += 1

for i in range(2,A): 
    cnt = 0
    for j in range(i,A,i):
        cnt += b[j]
    if cnt >= 2:
        ans = "setwise coprime"
        break

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

print(ans)

Solution (Python):
from math import gcd


class Eratosthenes(): 
    def __init__(self, N): 
        self.fact = [i for i in range(N + 1)]
        for i in range(2, int(N**0.5) + 1):
            if self.fact[i] < i:
                continue
            for j in range(i ** 2, N + 1, i):
                self.fact[j] = i


    def factor(self, NUM): 
        PRIME = set()
        while NUM > 1:
            PRIME.add(self.fact[NUM])
            NUM //= self.fact[NUM]
        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()

era = Eratosthenes(max(a))
num = set()
for ai in a:
    prime = era.factor(ai)
    if len(prime & num) > 0:
        print('setwise coprime')
        break
    num |= prime
else:
    print('pairwise coprime')

Solution (Python):
import math
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else 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, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
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()
    return divisors
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
mod = 10**9 + 7



n = ini()
a = inl()
A = 10**6+5
b = [0] * A
ans = "pairwise coprime"

for i in a: 
    b[i] += 1

for i in range(2,A): 
    cnt = 0
    for j in range(i,A,i):
        cnt += b[j]
    if cnt >= 2:
        ans = "setwise coprime"
        break

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

print(ans)

Solution (Python):
from math import gcd
from functools import reduce


def facs(n):
    """試し割り法における割る数を生成する。"""
    yield 2
    for x in range(3, n, 2):
        yield x


def main():
    input()  
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 1
    histogram = [0] * MAX_A
    for x in array:
        histogram[int(x)] += 1

    for divider in facs(MAX_A):
        count = sum(histogram[divider::divider])
        if count > 1:
            break
    else:
        return 'pairwise coprime'

    gcd_total = reduce(gcd, array)
    if gcd_total == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


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

Solution (Python):
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        count=0
        while n % i==0:
            count+=1
            n = n//i
        if count!=0:
            ass.append((i,count))
    if n != 1:
        ass.append((n,1))
    return ass

def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)
S = set()
n = int(input())
A = list(map(int,input().split()))

for i in range(n):
  ass = prime_factor(A[i])
  la = len(ass)
  ls = len(S)
  S.update(ass)
  if len(S) - ls != la:
    break
else:
  print("pairwise coprime")
  exit()

SetGcd = A[0]
for i in range(n):
  SetGcd = gcd(SetGcd,A[i])
if SetGcd == 1:
  print("setwise coprime")
else:
  print("not coprime")

Solution (Python):
from math import gcd
from functools import reduce


def main():
    input()  
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 1
    histogram = [0] * MAX_A
    for x in array:
        histogram[int(x)] += 1

    
    primes = []
    not_primes = set()
    for a in range(2, MAX_A):
        if a in not_primes:
            continue
        primes.append(a)
        for b in range(a * 2, MAX_A, a):
            not_primes.add(b)

    for divider in primes:
        count = sum(histogram[divider::divider])
        if count > 1:
            break
    else:
        return 'pairwise coprime'

    gcd_total = reduce(gcd, array)
    if gcd_total == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


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

Solution (Python):
import math
 
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
 
input()
d = None
u = set()
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print((r, 'not')[d > 1], 'coprime')

Solution (Python):
import math
 
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
 
input()
d = None
u = set()
for x in map(int, input().split()):
  d = math.gcd(d or x, x);
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print(d > 1 and 'not' or r, 'coprime')

Solution (Python):
def gcd(a, b):
    if a < b:
        return gcd(b, a)
    while b > 0:
        a, b = b, a % b
    return a

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

checker = [0] * (10 ** 6 + 1)
x = a_list[0]
for a in a_list:
    x = gcd(x, a)
    checker[a] += 1

if all(sum(checker[d::d]) <= 1 for d in range(2, 10 ** 6 + 1)):
    print("pairwise coprime")
elif x == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
class Sieve:
    """
    N以下の素数を列挙するエラトステネスのふるいです。
    O(NloglogN)でできます。

    Attributes
    sieveList : その数の素因数のうち最小のものの配列
    primes : N以下の素因数のリスト
    """
    def __init__(self, N):
        self.sieveList = [-1 for _ in range(N+1)]
        self.sieveList[1] = 1
        self.primes = []

        for i in range(2, N+1):
            
            if self.sieveList[i] != -1:
                continue
            self.primes.append(i)
            for j in range(i, N+1, i):
                if self.sieveList[j] != -1:
                    continue
                self.sieveList[j] = i

    def getPrimes(self):
        return self.primes

    def getSieveList(self):
        return self.sieveList

class FastFactorization(Sieve):
    """
    高速素因数分解です。
    与えられたL個の数がA以下の時、
    エラトステネスでO(AloglogA)＋素因数分解でO(LlogA) = O(AloglogA+NlogA)でできます。
    """

    def __init__(self, N):
        """
        前処理でスーパークラスのエラトステネスを使ってN以下の素因数を列挙します。
        """
        super().__init__(N)
        self.N = N
        self.sieveList = self.getSieveList()

    def factorize(self, x):
        if x > self.N:
            raise ValueError("与えられた数がエラトステネスのリストの上限を超えている")
        p = set()
        
        while x > 1:
            divisor = self.sieveList[x]
            x //= divisor
            p.add(divisor)
            
        return p

import math
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))


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


maxNum = max(A)
factorizor = FastFactorization(maxNum)
factors = defaultdict(int)
isPairwise = True
for i in range(N):
    p = factorizor.factorize(A[i])
    for x in p:
        if factors[x]:
            isPairwise = False
            break
        else:
            factors[x] = 1

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

Solution (Python):
from math import *
from collections import *
n=int(input())
a=list(map(int,input().split()))
g=[0 for i in range(10**6+1)]
for i in a:
    g[i]+=1
flg=True
for i in range(2,10**6+1):
    check=0
    for j in range (1,(10**6)//i+1):
        check+=g[i*j]
    if check>1:
        flg=False
if flg:
    print("pairwise coprime")
else:
    tmp=a[0]
    for i in a:
        tmp=gcd(tmp,i)
    if tmp==1:
        print("setwise coprime")
    else:
        print("not coprime")

Solution (Python):
import math
 
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
 
input()
d = None
u = set()
for x in map(int, input().split()):
  d = math.gcd(d or x, x);
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print('not' if d > 1 else r, 'coprime')

Solution (Python):
import math

N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'

input()
d = None
u = set()
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print((r, 'not')[d > 1], 'coprime')

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

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

MAXA = 10**6
B = [0] * (MAXA+1)
for a in A:
    if a==1: continue
    if B[a]:
        print('setwise coprime')
        exit()
    B[a] = 1

for n in range(2,MAXA+1):
    c = 0
    for m in range(n,MAXA+1,n):
        c += B[m]
        if c > 1:
            print('setwise coprime')
            exit()

print('pairwise coprime')

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

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

    MAXA = 10**6
    B = [0] * (MAXA+1)
    for a in A:
        if a==1: continue
        if B[a]:
            print('setwise coprime')
            exit()
        B[a] = 1

    for n in range(2,MAXA+1):
        c = 0
        for m in range(n,MAXA+1,n):
            c += B[m]
            if c > 1:
                print('setwise coprime')
                exit()

    print('pairwise coprime')
solve()

Solution (Python):
import numpy as np


def main():
    int(input())
    a = np.array([int(i) for i in input().split()])
    m = a.max() + 1
    p = np.zeros(m, dtype=int)
    for i in range(2, m):
        if p[i] == 0:
            p[i::i] = i
    factors = set()
    for ai in a[a > 1]:
        f = set()
        while ai > p[ai]:
            f.add(p[ai])
            ai //= p[ai]
        f.add(ai)
        if factors & f:
            break
        factors |= f
    else:
        print("pairwise coprime")
        return
    if np.gcd.reduce(a) == 1:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

Solution (Python):
import math


def divisorGenerator(n):

    large_divisors = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            if i*i != n:
                large_divisors.append(n // i)
    for divisor in reversed(large_divisors):
        yield divisor

if __name__ == '__main__':

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

    gcd_ = math.gcd(A[0], A[1])
    for i in range(2, len(A)):
        gcd_ = math.gcd(gcd_, A[i])

    set_wise = False
    if gcd_ == 1:
        set_wise = True
    if not(set_wise):
        print("not coprime")
    else:
        pairwise = True
        divs = dict()
        for i in A:
            res = list(divisorGenerator(i))
            for el in res:
                if el != 1:
                    if not(el in divs):
                        divs[el] = 0
                    divs[el] += 1
                    if divs[el] > 1:
                        print("setwise coprime")
                        exit()
        print("pairwise coprime")

Solution (Python):
from collections import defaultdict
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)
    a.sort()
    return a



primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i])
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1



if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

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

Solution (Python):
from math import gcd


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    m = max(a)
    p = [0] * (m + 1)
    for i in range(2, m + 1):
        if p[i] == 0:
            for j in range(i, m + 1, i):
                p[j] = i
    factors = set()
    for ai in a:
        if ai == 1:
            continue
        f = set()
        while ai > p[ai]:
            f.add(p[ai])
            ai //= p[ai]
        f.add(ai)
        if factors & f:
            break
        factors |= f
    else:
        print("pairwise coprime")
        return
    g = a[0]
    for ai in a[1:]:
        g = gcd(ai, g)
        if g == 1:
            print("setwise coprime")
            return
    print("not coprime")


if __name__ == '__main__':
    main()