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):
from math import gcd

def sieve(n):
    res = [i for i in range(n+1)]
    for i in range(2, int(n**0.5) + 1):
        if res[i] < i:
            continue
        for j in range(i*i, n + 1, i):
            if res[j] == j:
                res[j] = i
    return res

def factor(n, min_factor):
    res = []
    while n > 1:
        res.append(min_factor[n])
        n //= min_factor[n]
    return res

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

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

D = sieve(10 ** 6)

flag1 = 0
flag2 = 1

GCD = A[0]

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

if GCD == 1:
    flag1 = 1

for i in range(N):
    L = factor(A[i], D)
    L = set(L)
    for j in L:
        if flag[j]:
            flag2 = 0
            break
        flag[j] = 1
    if not flag2:
        break

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

Solution (Python):

from math import gcd
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    max_A = max(A) + 10

    CNT = [0] * max_A
    for a in A:
        CNT[a] += 1

    bl = True
    for i in range(2, max_A):
        cnt = 0
        for j in range(i, max_A, i):
            cnt += CNT[j]
        if cnt > 1:
            bl = False
    if bl:
        print("pairwise coprime")
        return

    g = 0
    for i in range(N):
        g = gcd(g, A[i])
    if g == 1:
        print("setwise coprime")
        return

    print("not coprime")


if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import defaultdict
max = 10 ** 6
sieve = [None] * (max + 1)
for i in range(2, max + 1):
    if sieve[i] == None: 
        for ki in range(i, max + 1, i):
            sieve[ki] = i
def factors(n):
    while True:
        if sieve[n] is None:
            break
        yield sieve[n]
        n //= sieve[n]
used = defaultdict(lambda:0)

n = int(input())
a = map(int, input().split())
for ai in a:
    for factor in set(factors(ai)):
        used[factor] += 1
pairwise = True
setwise = True
for prime in used:
    if used[prime] > 1:
        pairwise = False
    if used[prime] == n:
        setwise = False
if pairwise:
    print("pairwise coprime")
elif setwise:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
from math import gcd
def preprocess(n):
    """
    n以下の自然数の高速素因数分解の前処理

    Parameters
    ----------
    n: int
        自然数

    Returns
    -------
    MinFactor:list
      高速素因数分解用のMinFactorテーブル
    """
    f = []
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    
    MinFactor = [-1]*(n+1)
    MinFactor[0] = 0
    MinFactor[1] = 1

    for i in range(2, n+1):
        if is_prime[i]:
            MinFactor[i] = i
            f.append(i)
            for j in range(i*2, n+1, i):
                is_prime[j] = False
                if MinFactor[j] == -1:
                    MinFactor[j] = i
    """
    return値
     1.素数か否かの判定結果:is_prime
     2.素数のリスト:f
     3.高速素因数分解用のMinFactorテーブル
    """
    return MinFactor

def prime_factorize(n,MinFactor):
    
    while n != 1:
        prime = MinFactor[n]
        
        while MinFactor[n] == prime:
            
            n //= prime
        cnt[prime] += 1
        
    

n = int(input())
a = list(map(int, input().split()))
a_max = max(a)
g = a[0]
for aa in a:
    g = gcd(g,aa)

mf = preprocess(a_max)
cnt = [0]*(a_max+1)
for aa in a:
    prime_factorize(aa,mf)

if g != 1:
    print("not coprime")
elif max(cnt) <= 1:
    print("pairwise coprime")
else:
    print("setwise coprime")

Solution (Python):
from functools import reduce

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

m = max(a)
d = [0] * (m + 1)
d[1] = 1
for i in range(2, m + 1):
    for j in range(i, m + 1, i):
        if d[j] == 0:
            d[j] = i

def prime_factorize(n):
    res = []
    if n == 1:
        return res
    while n > 1:
        res.append(d[n])
        n //= d[n]
    return res

def is_pairwise_coprime():
    exists = [0] * (m + 1)
    for ai in a:
        for p in set(prime_factorize(ai)):
            if exists[p]:
                return False
            exists[p] = 1
    return True

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

def is_setwise_coprime():
    return reduce(gcd, a) == 1


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

Solution (Python):
from functools import reduce

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

m = max(a)
d = [0] * (m + 1)
d[1] = 1
for i in range(2, m + 1):
    for j in range(i, m + 1, i):
        if d[j] == 0:
            d[j] = i

def prime_factorize(n):
    res = []
    if n == 1:
        return res
    while n > 1:
        res.append(d[n])
        n //= d[n]
    return res

def is_pairwise_coprime():
    exists = [0] * (m + 1)
    for ai in a:
        for p in set(prime_factorize(ai)):
            if exists[p]:
                return False
            exists[p] = 1
    return True

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

def is_setwise_coprime():
    return reduce(gcd, a) == 1


if is_pairwise_coprime():
    print('pairwise coprime')
elif is_setwise_coprime():
    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 = [i for i in range(m + 1)]
    for i in range(3, m + 1):
        for j in range(2, int(i**.5 + 1) + 1):
            if i % j == 0:
                p[i] = j
                break
    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()

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



"""






















using namespace std;

using int64 = long long;




using int128 = __int128_t;

int128 power(int128 base, int128 e, int128 mod) {
  int128 res = 1;
  base %= mod;
  while (e) {
    if (e & 1) (res *= base) %= mod;
    (base *= base) %= mod;
    e >>= 1;
  }
  return res;
}

bool is_prime(int64 n) {
  if (n < 2 || ~n & 1) return n == 2;
  int s = __builtin_ctzll(n - 1);
  int64 d = (n - 1) >> s;
  for (int64 base : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
    int128 x = base % n;
    if (!x) continue;
    x = power(x, d, n);
    if (x == 1 || x == n - 1) continue;
    bool ok = false;
    for (int i = 0; i < s - 1; ++i) {
      (x *= x) %= n;
      if (x == n - 1) {
        ok = true; break;
      }
    }
    if (!ok) return false;
  }
  return true;
}

int64 binary_gcd(int64 x, int64 y) {
  if (x < 0) x = -x;
  if (y < 0) y = -y;
  if (!x) return y;
  if (!y) return x;
  int s = __builtin_ctzll(x | y);
  x >>= __builtin_ctzll(x);
  do {
    y >>= __builtin_ctzll(y);
    if (x > y) std::swap(x, y);
    y -= x;
  } while (y);
  return x << s;
}

template <class T>
inline std::vector<T> connect(const std::vector<T> &a,
                              const std::vector<T> &b) {
  std::vector<T> c(a.size() + b.size());
  std::merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
  return c;
}

template <class T>
std::vector<T> factor(T n) {
  if (n <= 1) return {};
  if (is_prime(n)) return {n};
  if (~n & 1) return connect({2}, factor(n >> 1));
  for (T c = 1;; ++c) {
    T x = 2, y = 2, d;
    do {
      x = ((int128)x * x + c) % n;
      y = ((int128)y * y + c) % n;
      y = ((int128)y * y + c) % n;
      d = binary_gcd(x - y, n);
    } while (d == 1);
    if (d < n) return connect(factor(d), factor(n / d));
  }
}

template <class T>
std::vector<std::pair<T, int>> RunLengthEncoding(const std::vector<T>& vec) {
  std::vector<std::pair<T, int>> ret;
  int sz = vec.size();
  int beg = 0;
  while (beg < sz) {
    int ed = beg;
    while (ed + 1 < sz && vec[beg] == vec[ed + 1]) ++ed;
    int len = ed - beg + 1;
    ret.emplace_back(vec[beg], len);
    beg = ed + 1;
  }
  return ret;
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vector<int> a(n); for (int& e : a) cin >> e;
  vector<int> cnt(1010101, 0);
  bool p_coprime = true;
  for (int e : a) {
    auto v = RunLengthEncoding(factor(e));
    for (auto p : v) {
      if (cnt[p.first] > 0) {
        p_coprime = false; break;
      }
      ++cnt[p.first];
    }
    if (!p_coprime) break;
  }

  if (p_coprime) {
    cout << "pairwise coprime" << endl;
  } else {
    int g = 0;
    for (int e : a) g = binary_gcd(g, e);
    if (g == 1) {
      cout << "setwise coprime" << endl;
    } else {
      cout << "not coprime" << endl;
    }
  }

  return 0;
}
"""

import base64
import subprocess


exe_bin = "e??420s

exe_bin = base64.b85decode(exe_bin)

with open("./kyomu", 'wb') as f:
    f.write(exe_bin)

subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

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
        self.prime_list = [i for i, pi in enumerate(self.fact[2:], 2) if pi == 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
L = 10**6 + 1

N = int(input())
A = list(map(int, input().split()))
memo = [0] * L
flag = 0 

for a in A:
    memo[a] += 1

for i in range(2, L):
    if sum(memo[i::i]) > 1:
        flag = 1
        break

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

if flag == 0:
    answer = 'pairwise coprime'
elif flag == 1 and g == 1:
    answer = 'setwise coprime'
else:
    answer = 'not coprime'

print(answer)

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
        self.prime_list = [i for i, pi in enumerate(self.fact[2:], 2) if pi == i]


    def factor(self, NUM):  
        PRIME = set()
        for p in self.prime_list:
            if p * p > NUM:
                break
            while NUM % p == 0:
                NUM //= p
                PRIME.add(p)
        if NUM > 1:
            PRIME.add(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):
from math import gcd
from collections import defaultdict

upper = 10**6
N = int(input())
A = list(map(int, input().split()))
num = defaultdict(int)

g = 0
for a in A:
    g = gcd(g, a)
    num[a] += 1

isStopped = False
for i in range(2, upper+1):
    x = 0
    for j in range(i, upper+1, i):
        x += num[j]
    if x >= 2:
        isStopped = True
        break

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

Solution (Python):


import math
from functools import reduce

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

if reduce(math.gcd, a) > 1:
    print("not coprime")
    exit()

def factors(n):
    """Return the list of prime factors of n."""
    fac = set()
    sqrtn = math.sqrt(n)
    d = 2
    while d <= sqrtn:
        if n % d == 0:
            fac.add(d)
            n //= d
        else:
            d += 1
    if n > 1:
        fac.add(n)
    return fac

count = [0] * (10 ** 6 + 1)
for x in a:
    for f in factors(x):
        count[f] += 1
        if count[f] > 1:
            print("setwise coprime")
            exit()
print("pairwise coprime")

Solution (Python):
from math import gcd


class Eratosthenes(): 
    def __init__(self, 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
        self.prime_list = [i for i, pi in enumerate(is_prime) if pi == 1]


    def factor(self, NUM):  
        PRIME = set()
        for p in self.prime_list:
            if p * p > NUM:
                break
            while NUM % p == 0:
                NUM //= p
                PRIME.add(p)
        if NUM > 1:
            PRIME.add(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):
n = int(input())
a = list(map(int,input().split()))


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


g = a[0]
for x in a[1:]:
    g = gcd(g, x)

if g > 1:
    print('not coprime')
    exit()


exist = [False] * (10**6+1)
for x in a:
    if x % 2 == 0:
        if exist[2]:
            print('setwise coprime')
            exit()
        while x % 2 == 0:
            x //= 2
        exist[2] = True
    div = 3
    while div * div <= x:
        if x % div == 0:
            if exist[div]:
                print('setwise coprime')
                exit()
            while x % div == 0:
                x //= div
            exist[div] = True
        div += 2
    if x > 1:
        if exist[x]:
            print('setwise coprime')
            exit()
        exist[x] = True
print('pairwise coprime')

Solution (Python):
from math import gcd
N=int(input())
A=list(map(int,input().split()))
wa=[-1]*1000001
pr=[]
t=0
for i in range(2,1000001):
    if wa[i]>=0:
        continue
    pr.append(i)
    wa[i]=t
    for j in range(i**2,1000001,i):
        if wa[j]==-1:
            wa[j]=t
    t+=1
lp=len(pr)
l=[0]*lp
g=gcd(A[0],A[1])
for i in A:
    g=gcd(g,i)
if g>1:
    print("not coprime")
    exit()
for i in A:
    t=i
    for j in range(wa[i],lp):
        pj=pr[j]
        if pj>t:
            break
        if t%pj==0:
            if l[j]:
                print("setwise coprime")
                exit()
            l[j]=1
            while 1:
                t//=pj
                if t%pj:
                    break
print("pairwise coprime")

Solution (Python):
from math import gcd


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]


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






from math import gcd





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





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

def isPrime(x):
    for i in range(2, int(x**0.5)+1):
        if x%i == 0:
            return False
    return True

def div_primes(x):
    ret = {}
    for i in range(2, int(x**0.5)+1):
        tmp = 0
        while x%i == 0:
            tmp += 1
            x //= i
        if tmp > 0:
            ret[i] = tmp
    if x > 1:
        ret[x] = 1
    return ret





g = A[0]
for i in range(1,N):
    g = gcd(g,A[i])
if g > 1:
    print("not coprime")
else:
    mylist = [True for _ in range(10**6+1)]
    mylist[0] = mylist[1] = False
    primes = {}
    for i in range(2, len(mylist)):
        if mylist[i]:
            primes[i] = 0
            for j in range(i*2, len(mylist), i):
                mylist[j] = False
    flag = True
    for a in A:
        if a in primes:
            if primes[a] == 0:
                primes[a] = 1
            else:
                flag = False
                break
        else:
            divs = div_primes(a)
            for k in divs.keys():
                if primes[k] == 0:
                    primes[k] = 1
                else:
                    flag = False
                    break
            else:
                continue
            break
    if flag:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


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


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



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


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


from collections import Counter


class FastFactorization:
    def __init__(self, N: int):
        '''構築O(NloglogN)、クエリO(logN)'''
        self.N = N
        self.min_prime = self._make_minimum_prime()

    def _make_minimum_prime(self):
        
        min_prime = [x for x in range(self.N + 1)]
        
        
        for i in range(2, int(self.N ** 0.5) + 1):
            if min_prime[i] == i:  
                for j in range(2 * i, self.N + 1, i):  
                    if min_prime[j] == j:
                        min_prime[j] = i
        return min_prime

    def query(self, x: int):
        
        
        if x == 1:
            return Counter()  

        
        arr = []
        tmp = x
        while tmp != 1:
            p = self.min_prime[tmp]
            tmp //= p
            arr.append(p)
        return Counter(arr)


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from math import gcd


N = a_int()
A = ints()

fact = FastFactorization(max(A))






g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  
for a in A:
    g_set = gcd(g_set, a)
    if flg:
        for p, n in fact.query(a).items():
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n








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

Solution (Python):
import sys
import math
import fractions
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]



def prime_fact(n):
    if n == 1:
        return {1: 1}

    prime_dict = {}
    for i in range(2, int(n**0.5)+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()

    if max(A) == 1:
        print("pairwise coprime")
        exit()

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()

    SA = set(A)
    if len(SA) >= 90000:
        print("setwise coprime")
        exit()

    p_cnt = defaultdict(int)
    cnt = 0
    for a in A:
        if a == 1:
            continue
        AP = prime_fact(a)
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == "__main__":
    main()

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

    M = 10**6+1
    mp = [0]*M
    for a in A:
        mp[a] += 1

    pairwise = 1
    for i in range(2,M):
        if sum(mp[i::i])>1:
            pairwise = 0
            break

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

if __name__ == '__main__':
    main()

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

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

M = 10**6+1
mp = [0]*M
for a in A:
    mp[a] += 1

pairwise = 1
for i in range(2,M):
    if sum(mp[i::i])>1:
        pairwise = 0
        break

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

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    from math import gcd
    
    
    
    
    n = 10**6 + 5
    
    D=[1]*(n+1) 

    
    is_prime = [True]*(n+1)
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            D[i-1]=i
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                if D[j-1]==1: 
                    D[j-1]=i
                j += i

    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    P=[[]for _ in range(n)]
    
    
    for i in range(2,n):
        if is_prime[i-1]:
            P[i-1].append(i)
        else:
            now=i
            while now >= 2:
                
                P[i-1].append(D[now-1])
                now=now//D[now-1]

    
    
    
    N=I()
    A=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    flag=1
    for i in range(N):
        a=A[i]
        S=set(P[a-1])
        
        for p in S:
            if dd[p]:
                flag=0
                break
            dd[p]+=1
    

            
    if flag:
        print("pairwise coprime")
    else:
        g=A[0]
        for i in range(1,N):
            g=gcd(g,A[i])
        if g==1:
            print("setwise coprime")
        else:
            print("not coprime")
                
            
    

main()

Solution (Python):
from math import gcd


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]


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