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
from functools import reduce

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

max_a = max(a)
d = list(range(max_a+1))
for i in range(2, int(max_a**0.5)+1):
    if d[i] == i:
        for k in range(2*i, max_a+1, i):
            if d[k] == k:
                d[k] = i

exist = [0] * len(d)
res = 'pairwise coprime'
for i in range(n):
    val = a[i]
    s = set()
    while val != 1:
        s.add(d[val])
        val //= d[val]

    for k in s:
        if exist[k]:
            res = 'setwise coprime'
            break
        exist[k] = 1
    else:
        continue
    break

if res == 'setwise coprime':
    if reduce(gcd, a) != 1:
        res = 'not coprime'

print(res)

Solution (Python):
from functools import lru_cache
import math

def main():
    n=int(input())
    a=list(map(int,input().split()))
    x=set()
    y=a[0]
    pair=True
    for i in a:
        if pair:
            p=set(prime_factorize(i))
            if len(x&p)>0:
                pair=False
            x|=p
        y=math.gcd(y, i)
    if pair:
        print("pairwise coprime")
    elif y==1:
        print("setwise coprime")
    else:
        print("not coprime")


@lru_cache(maxsize=None)
def primes(n:int) -> list:
    '''n以下の全素数をlistで返す'''
    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]]


@lru_cache(maxsize=None)
def is_prime(n: int) -> bool:
    '''引数nが素数であればTrue、そうでなければFalseを返す'''
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True


def prime_factorize(n: int) -> list:
    '''引数nの素因数分解結果のlistを返す。'''
    arr = []
    
    while n % 2 == 0:
        arr.append(2)
        n //= 2
    
    for f in primes(int(n**0.5)):
        while n % f == 0:
            arr.append(f)
            n //= f
    if n != 1:
        arr.append(n)
    return arr

if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
a=[int(x) for x in input().split()]
ma=max(a)
memo=[0]*ma

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

for i in a:
  memo[i-1]+=1

pair=True
for i in range(2,ma+1):
  cnt=0
  for j in range(i,ma+1,i):
    if 0<memo[j-1]:
      cnt+=1
  if 1<cnt:
    pair=False


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

if pair == False and g==1:
  print("setwise coprime")
elif pair == True and g==1:
  print("pairwise coprime")
else:
  print("not coprime")

Solution (Python):
from math import gcd
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
d=[0]*(10**6)
for i in a:
  d[i-1]+=1
num=2
while num<=10**6:
  if sum([d[i*num-1] for i in range(1,10**6//num+1)])>1:
      break
  num+=1
else:
  print('pairwise coprime')
  exit()
g=reduce(gcd,a)
if g==1:
  print('setwise coprime')
  exit()

print('not coprime')

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from math import gcd
from functools import reduce
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    M = max(A)

    if reduce(gcd, A) != 1:
        print("not coprime")
        return

    
    sieve = list(range(M + 1))
    primes = []
    for i in range(2, M + 1):
        if sieve[i] == i:
            primes.append(i)
        for p in primes:
            if sieve[i] < p or i * p > M:
                break
            sieve[i * p] = p

    
    f = list(range(M + 1))
    g = [1] * (M + 1)
    for i in range(2, M + 1):
        j = 0
        for j in range(i * i, M + 1, i * i):
            g[j] = i
        f[i] = f[i // g[i]]

    
    used = [False] * (M + 1)
    for a in map(lambda a : f[a], A):
        while a != 1:
            p = sieve[a]
            if used[p]:
                print("setwise coprime")
                return
            used[p] = True
            a //= p
    print("pairwise coprime")
resolve()

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from math import gcd
from functools import reduce
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    M = max(A)

    if reduce(gcd, A) != 1:
        print("not coprime")
        return

    
    sieve = list(range(M + 1))
    primes = []
    for i in range(2, M + 1):
        if sieve[i] == i:
            primes.append(i)
        for p in primes:
            if sieve[i] < p or i * p > M:
                break
            sieve[i * p] = p

    
    f = list(range(M + 1))
    g = [1] * (M + 1)
    for i in range(2, M + 1):
        j = 0
        while j <= M:
            g[j] = i
            j += i * i
        f[i] = f[i // g[i]]

    
    used = [False] * (M + 1)
    for a in A:
        a = f[a]
        while a != 1:
            p = sieve[a]
            if used[p]:
                print("setwise coprime")
                return
            used[p] = True
            a //= p
    print("pairwise coprime")
resolve()

Solution (Python):
import numpy as np
n=int(input())
a=list(map(int,input().split()))
g=np.gcd.reduce(a)
if g>1:
    print("not coprime")
    exit()
c=[0]*(10**6+1)
for i in a:
    c[i]+=1
if np.all([sum(c[i::i])<=1 for i in range(2,10**6+1)]):
    print("pairwise coprime")
else:
    print("setwise coprime")

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

num = 10**6
li = [0]*num
for k in a:
    li[k-1] += 1

i=2
while i<=num:
    if sum([li[k*i-1] for k in range(1,num//i+1)])>1:
        break
    i+=1
else:
    print("pairwise coprime")
    sys.exit()

import math
import functools
g = functools.reduce(math.gcd,a)
if g==1:
    print("setwise coprime")
    sys.exit()

print("not coprime")

Solution (Python):
def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def is_pairwise():
    C = [0] * (10**6 + 1)
    max_a = 0
    for a in A:
        C[a] += 1
        max_a = max(max_a, a)
    if sum(C[2::2]) > 1: return False
    for i in range(3, max_a + 1, 2):
        if sum(C[i::i]) > 1: return False
    return True

def solve():
    if is_pairwise(): return 0
    if gcd_all(A) == 1: return 1
    return 2

n = int(input())
A = [*map(int, input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Solution (Python):
def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def is_pairwise():
    MAX_A = 10**6
    C = [0] * (MAX_A + 1)
    max_a = 0
    for a in A:
        C[a] += 1
        max_a = max(max_a, a)
    if sum(C[2::2]) > 1: return False
    for i in range(3, max_a + 1, 2):
        if sum(C[i::i]) > 1: return False
    return True

def solve():
    if is_pairwise(): return 0
    if gcd_all(A) == 1: return 1
    return 2

n = int(input())
A = [*map(int, input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Solution (Python):
from functools import lru_cache
import math
def main():
    n=int(input())
    a=list(map(int,input().split()))
    pair,setwise=True,True
    x,y=set(),a[0]
    for i in a:
        if pair:
            ap=set(prime_factorize(i))
            if len(x & ap) > 0:
                pair=False
            x |= ap
        y=math.gcd(y, i)
    if pair:
        print("pairwise coprime")
    elif y == 1:
        print("setwise coprime")
    else:
        print("not coprime")

def prime_factorize(n: int) -> list:
    '''引数nの素因数分解結果のlistを返す。'''
    arr = []
    
    while n % 2 == 0:
        arr.append(2)
        n //= 2
    
    for f in primes(int(n**0.5)):
        while n % f == 0:
            arr.append(f)
            n //= f
    if n != 1:
        arr.append(n)
    return arr

@lru_cache(maxsize=None)
def primes(n:int) -> list:
    '''n以下の全素数をlistで返す'''
    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]]

@lru_cache(maxsize=None)
def is_prime(n: int) -> bool:
    '''引数nが素数であればTrue、そうでなければFalseを返す'''
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

if __name__ == "__main__":
    main()

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

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)
def calc():
  n=int(input())
  arr=list(map(int,input().split()))
  g=arr[0]
  cnt=[0]*(10**6+1)
  for val in arr:
    g=gcd(g,val)
    cnt[val]+=1
  for i in range(2,10**6+1):
    tmp=0
    for j in range(i,10**6+1,i):
      tmp+=cnt[j]
    if tmp>=2:
      break
  if i==10**6:
    print('pairwise coprime')
  elif g==1:
    print('setwise coprime')
  else:
    print('not coprime')
calc()

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

n=int(input())
arr=list(map(int,input().split()))
g=arr[0]
cnt=[0]*(10**6+1)
for val in arr:
  g=gcd(g,val)
  cnt[val]+=1
for i in range(2,10**6+1):
  tmp=0
  for j in range(i,10**6+1,i):
    tmp+=cnt[j]
  if tmp>=2:
    break
if i==10**6:
  print('pairwise coprime')
elif g==1:
  print('setwise coprime')
else:
  print('not coprime')

Solution (Python):
def gcd_all(a):
    from math import gcd
    g = 0
    for x in a: g = gcd(g, x)
    return g

def is_pairwise():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    if sum(C[2::2]) > 1: return False
    for i in range(3, MAX_A, 2):
        if sum(C[i::i]) > 1: return False
    return True

def solve():
    if is_pairwise(): return 0
    if gcd_all(A) == 1: return 1
    return 2

n = int(input())
A = [*map(int, input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Solution (Python):
def gcd_all(a):
    from math import gcd
    g = 0
    for x in a: g = gcd(g, x)
    return g

def is_pairwise():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    if sum(C[2::2]) > 1: return False
    for i in range(3, MAX_A, 2):
        if sum(C[i::i]) > 1: return False
    return True

def solve():
    if is_pairwise(): return 'pairwise'
    if gcd_all(A) == 1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Solution (Python):
def gcd_all(a):
    from math import gcd
    g = 0
    for x in a: g = gcd(g, x)
    return g

def is_pairwise():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    for i in range(2, MAX_A):
        if sum(C[i::i]) > 1: return False
    return True

def solve():
    if is_pairwise(): return 'pairwise'
    if gcd_all(A) == 1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Solution (Python):
n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    if sum(C[2::2]) > 1: pairwise = False
    for i in range(3, MAX_A, 2):
        if sum(C[i::i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')

Solution (Python):
n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for i in range(2, MAX_A):
        if sum(C[i::i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')

Solution (Python):
n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for i in range(2, MAX_A):
        if sum(C[i::i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')

Solution (Python):
from math import gcd
import time




def make_prime_arr(max_a):
    pri_arr = [0] * max_a
    
    for i in range(2, max_a):
        if(pri_arr[i] != 0):
            continue
        for j in range (i, max_a, i):
            pri_arr[j] = i
    
    
    return pri_arr



def is_pairwise(a_arr, pri_arr, max_a):
    flg_arr = [0] * (max_a)
    for a_ele in a_arr:
        x = a_ele
        y = 0
        while x != 1:
            if(pri_arr[y] != pri_arr[x]):
                flg_arr[pri_arr[x]] += 1
            if flg_arr[pri_arr[x]] > 1:
                return False
            y = x
            x = x // pri_arr[x]
            
    return True



def is_setwise(a_arr, N):
    entire_gcd = a_arr[0]
    for i in range(1, N):
        entire_gcd = gcd(entire_gcd, a_arr[i])
    if entire_gcd != 1:
        return False        
    return True


def main():
    N = int(input())
    a_arr = list(map(int, input().split(" ")))
    max_a = 10**6 + 1
    pri_arr = make_prime_arr(max_a)
    if is_pairwise(a_arr, pri_arr, max_a):
        print("pairwise coprime")
    elif is_setwise(a_arr, N):
        print("setwise coprime")
    else:
        print("not coprime")

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
sys.setrecursionlimit(10**9)

n = int(input())
a = list(map(int, input().split()))
ma = max(a)
p = [0]*(ma + 1)

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

pairwise = True
for i in range(2, ma+1):
  cnt = 0
  for j in range(i, ma+1, i):
    cnt += p[j]
  if cnt > 1:
    pairwise = False
    break
    
if pairwise:
  print("pairwise coprime")
else:
  temp = a[0]
  for i in a:
    temp = math.gcd(temp, i)
  if temp == 1:
    print("setwise coprime")
  else:
    print("not coprime")

Solution (Python):
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split()))



    def get_primenumber(number):  
        prime_list = []
        search_list = list(range(2, number + 1))
        
        while search_list[0] <= math.sqrt(number):
            
            
            head_num = search_list.pop(0)
            prime_list.append(head_num)
            
            search_list = [num for num in search_list if num % head_num != 0]
        
        prime_list.extend(search_list)
        return prime_list


    def prime_factor_table(n):
        table = [0] * (n + 1)
        for i in range(2, n + 1):
            if table[i] == 0:
                for j in range(i + i, n + 1, i):
                    table[j] = i
        return table

    def prime_factor(n, prime_factor_table):
        prime_count = collections.Counter()

        while prime_factor_table[n] != 0:
            prime_count[prime_factor_table[n]] += 1
            n //= prime_factor_table[n]
        prime_count[n] += 1

        return prime_count

    table = prime_factor_table(10**6+10)

    numset = set()
    for i in A:
        thedic = prime_factor(i, table)
        for l in thedic.keys():
            flag = True
            if l in numset and l != 1:
                flag = False
                break
        if flag:
            tmpset = set(thedic.keys())
            numset |= tmpset
        else:
            break
    if flag:
        print('pairwise coprime')
        sys.exit()
    else:
        flag = True
        theset = set(prime_factor(A[0], table).keys())
        for i in A[1:]:
            thedic = prime_factor(i, table)
            theset = theset & set(thedic.keys())
            if len(theset) == 0:
                print('setwise coprime')
                flag = False
                break
    if flag:
        print('not coprime')



if __name__ == '__main__':
    solve()

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



def is_pairwise_coprime():
    l = [0]*(10**6+1)
    for a in A:
        for j in range(2, int(a**(1/2))+2):
            if a % j == 0:
                if l[j]:
                    return False
                l[j] = 1
            while a % j == 0:
                a //= j
        if a != 1:
            if l[a]:
                return False
            l[a] = 1
    return True

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

def is_setwise_coprime():
    A_gcd = A[0]
    for a in A[1:]:
        A_gcd = gcd(A_gcd, a)
        if A_gcd == 1:
            break
    return (A_gcd == 1)

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

Solution (Python):
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()

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

    all_gcd = A[0]
    max_num = A[0]
    for a in A:
        all_gcd = gcd(all_gcd, a)
        max_num = max(max_num, a)
    if all_gcd != 1:
        print("not coprime")
        return

    
    min_prime = [i for i in range(max_num + 1)]
    for p in range(2, int(max_num**0.5) + 1):
        if min_prime[p] != p: continue
        for i in range(2 * p, max_num + 1, p): min_prime[i] = p

    
    used = [0] * (max_num + 1)
    for a in A:
        while a > 1:
            p = min_prime[a]
            if used[p]:
                print("setwise coprime")
                return
            while a % p == 0: a //= p
            used[p] = 1
    print("pairwise coprime")




if __name__ == "__main__":
    main()

Solution (Python):
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()

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

    all_gcd = A[0]
    max_num = A[0]
    for a in A:
        all_gcd = gcd(all_gcd, a)
        max_num = max(max_num, a)
    if all_gcd != 1:
        print("not coprime")
        return

    
    min_prime = [i for i in range(max_num + 1)]
    for p in range(2, int(max_num**0.5) + 1):
        if min_prime[p] != p: continue
        for i in range(2, max_num // p + 1): min_prime[i * p] = p

    used = [0] * (max_num + 1)
    for a in A:
        while a > 1:
            p = min_prime[a]
            if used[p]:
                print("setwise coprime")
                return
            while a % p == 0: a //= p
            used[p] = 1
    print("pairwise coprime")




if __name__ == "__main__":
    main()

Solution (Python):
import sys


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


def is_prime_MR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1 << 32 else [
        2, 3, 5, 7, 11, 13, 17
    ] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    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 find_factor_rho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):

        def f(x):
            return (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 is_prime_MR(g):
                return g
            elif is_prime_MR(n // g):
                return n // g
            return find_factor_rho(g)


def prime_factor(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 += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2**20:
            while n > 1:
                if is_prime_MR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = find_factor_rho(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


input = sys.stdin.buffer.readline

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

X = [0] * 1001001
for a in A:
    for p in prime_factor(a):
        if X[p]:
            print('setwise coprime')
            exit()
        X[p] = 1

print('pairwise coprime')

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
M = max(a)+1
if M == 2:
    print("pairwise coprime")
    exit()
count = [0]*(M)
prime = [2,3,5,7,11,13]
for i in range(14,int(M**0.5)+2):
    check = True
    for j in prime:
        if i%j == 0:
            check = False
            break
    if check:
        prime.append(i)
 
for i in a:
    for j in prime:
        if i < j:
            break
        if i%j==0:
            while i%j == 0:
                i //= j
            count[j] += 1
    if i > 1:
        count[i] += 1
 
ans = max(count)
 
if ans == 1:
    print("pairwise coprime")
elif ans == n:
    print("not coprime")
else:
    print("setwise coprime")

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

M = 10**6

import math

setwise = A[0]
for i in range(1,N):
    setwise = math.gcd(setwise,A[i])
    
PrimeFactorss = [[] for _ in range(M+1)]
for i in range(2, M+1):
    if len(PrimeFactorss[i]) == 0:
        for x in range(i, M+1, i):
            PrimeFactorss[x].append(i)
num_list = [0]*(M+1)

for i in range(N):
    num_list[A[i]] += 1

pairwise = [0]*(M+1)

n=M
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=list(primes)

for i in primes:
    for j in range(i,M+1,i):
        if num_list[j]==1:
            pairwise[i] += 1
        
ans = 0    
for i in pairwise:
    if i>1:
        ans += 1
        break
    
if setwise == 1 and ans == 0:
    print("pairwise coprime")
elif setwise == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
import math
n = int(input())
a = list(map(int, input().split()))
f = [0]*10**7
def fctr_d(n):
    c = 0
    r = int(n**0.5)
    for i in range(2, r+2):
        while n % i == 0:
            c += 1
            n = n//i
        if c != 0:
            if f[i] != 0:
                return False
            else:
                f[i] = True
                c = 0
    if n != 1:
        if f[n] != 0:
            return False
        else:
            f[n] = True
    return True


pairwise_flag = True
for i in range(n):
    m = a[i]
    if not fctr_d(m):
        pairwise_flag = False
        break

setwise_flag = True
gcd = a[0]
for i in range(1, n):
    gcd = math.gcd(gcd, a[i])
if gcd != 1:
    setwise_flag = False

if pairwise_flag:
    print("pairwise coprime")
else:
    if setwise_flag:
        print("setwise coprime")
    else:
        print("not coprime")

Solution (Python):
from collections import Counter
def prime_factorize(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
n = int(input())
input_list = list(map(int,input().split()))
num_count = Counter([prime for num in input_list for prime in prime_factorize(num)])
if len(num_count.values())==0:
    print("pairwise coprime")
    exit()
max_appear = max(num_count.values())
if max_appear == 1:
    print("pairwise coprime")
elif max_appear != n:
    print("setwise coprime")
else:
    print("not coprime")

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

def factorize(n):
    fct = []  
    b, e = 2, 0  
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

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

pc = True

fac = [0]*(10**6+1)
for a in A:
    lst = factorize(a)
    for p in lst:
        if not fac[p[0]]:
            fac[p[0]] = 1
        else:
            pc = False
            break
    if not pc:
        break
if pc:
    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')

Solution (Python):
from math import gcd

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D, A_max):
    p_count = [0] * (A_max + 1)
    for A in A_list:
        temp = A
        d = 0
        while temp != 1:
            if p_count[D[temp]] == 1 and d != D[temp]:
                return 0
            p_count[D[temp]] = 1
            d = D[temp]
            temp = temp // D[temp]
    return 1


N = int(input())
A_list = list(map(int, input().split(" ")))


A_max = max(A_list)


if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D, A_max) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Solution (Python):
from math import gcd

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        d = 0
        while temp != 1:
            if p_count[D[temp]] == 1 and d != D[temp]:
                return 0
            p_count[D[temp]] = 1
            d = D[temp]
            temp = temp // D[temp]
    return 1


N = int(input())
A_list = list(map(int, input().split(" ")))


A_max = max(A_list)


if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

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

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        d = 0
        while temp != 1:
            if p_count[D[temp]] == 1 and d != D[temp]:
                return 0
            p_count[D[temp]] = 1
            d = D[temp]
            temp = temp // D[temp]
    return 1


N = int(input())
A_list = list(map(int, input().split(" ")))


A_max = max(A_list)


if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Solution (Python):
import math


def primes(N):
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    return [i for i in range(N + 1) if p[i]]


N = int(input())
A = list(map(int, input().split()))
maxA = max(A) + 1
g, Ac = A[0], [0] * maxA
P = primes(maxA)

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

ans = "pairwise"
for p in P:
    if sum(Ac[p:maxA:p]) > 1:
        ans = "setwise"
for a in A:
    g = math.gcd(g, a)
print(ans if g == 1 else "not", "coprime")

Solution (Python):
MAX_A = 10**6 + 1
MAX_P = MAX_A // 2
is_prim = [i%2==1 for i in range(MAX_P)]
is_prim[1] = False; is_prim[2] = True
for i in range(3, MAX_P):
    if not is_prim[i]: continue
    for j in range(i+i, MAX_P, i): is_prim[j] = False

def solve():
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for p in [i for i in range(MAX_P) if is_prim[i]]:
        if sum(C[p::p]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')