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
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():
    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
    
    from math import gcd
    N=I()
    A=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    flag=1
    
    for i in range(N):
        a=A[i]
        ret=primeFactor(a)
        for p,pn in ret.items():
            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
n = int(input())
a = list(map(int, input().split()))
u = 0
for i in a:
    u = gcd(u, i)
if u != 1:
    print('not coprime')
    exit()
vis = [False] * (10 ** 6 + 1)
for i in a:
    vis[i] = True
cnt = [0] * (10 ** 6 + 1)
for i in range(1, 10 ** 6 + 1):
    for j in range(1, 10 ** 6 + 1):
        if i * j > 10 ** 6:
            break
        if vis[i * j]:
            cnt[i] += 1
if max(cnt[2:]) <= 1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Solution (Python):


import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():

    def gcd(x, y):
        """greatest common divisor of x and y"""
        while y:
            x, y = y, x % y
        return x

    N = 1000000+2
    cnt = [0]*N

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

    for x in a:
        cnt[x]+=1

    for i in range(2,N):
        c=0
        for j in range(i,N,i):
            c+=cnt[j]
        if c>=2:
            break
    else:
        print("pairwise coprime")
        exit(0)

    g=a[0]
    for x in a:
        g=gcd(g,x)
        if g==1:
            print("setwise coprime")
            exit(0)

    print("not coprime")


BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from math import gcd
    input = sys.stdin.readline

    NN = 10**6
    prime = [[] for _ in range(NN+1)]
    is_prime = [1] * (NN+1)
    is_prime[1] = 0
    for i in range(2, NN+1):
        if not is_prime[i]:
            continue
        prime[i].append(i)
        for j in range(2, NN+1):
            if i*j > NN:
                break
            is_prime[i*j] = 0
            prime[i*j].append(i)

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

    P = 1
    g = A[0]
    seen = [0] * (NN+1)
    for a in A:
        g = gcd(g, a)
        for p in prime[a]:
            if seen[p]:
                P = 0
            seen[p] = 1
    if g != 1:
        print("not coprime")
    else:
        if P == 1:
            print("pairwise coprime")
        else:
            print("setwise coprime")


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from math import gcd
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mx = max(a)
table = [0] * (mx + 1)
for x in a: table[x] += 1
g = 0
for x in a: g = gcd(g, x)
for i in range(2, mx + 1):
  c = 0
  for j in range(i, mx + 1, i): c += table[j]
  if c > 1:
    if g == 1: print("setwise coprime")
    else: print("not coprime")
    exit(0)
print("pairwise coprime")

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



from collections import Counter

def gcd(a,b):
    while b:
        a, b = b, a%b
    return a
M = 10**6 + 8
prime = [0]*M
for i in range(2, M):
    if prime[i]:
        continue
    for j in range(i, M, i):
        if not prime[j]:
            prime[j] = i

def pd(x):
    C = Counter()
    while x > 1:
        C[prime[x]] += 1
        x //= prime[x]
    return C


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

D = Counter()

for a in A:
    c = pd(a)
    for k in c.keys():
        D[k] += 1


res = A[0]
for a in A:
    res = gcd(res, a)
ans = None
if all(a == 1 for a in A) or max(D.values()) == 1:
    ans = 'pairwise coprime'
elif res == 1:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()
a = na()

f = [0] * 1000001
for v in a:
    f[v] += 1
for i in range(2, 500001):
    for j in range(i*2, 1000001, i):
        f[i] += f[j]

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

if max(f[2:]) <= 1:
    print("pairwise coprime")
else:
    x = 0
    for v in a:
        x = gcd(x, v)
    if x == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Solution (Python):
from sys import exit
from math import gcd
n = int(input())
a = list(map(int, input().split()))
g = gcd(a[0], a[1])
for i in range(2, n):
	g = gcd(g, a[i])
if g > 1:
	print("not coprime")
	exit()

MAX = 1000001
nxt = [i for i in range(MAX)]
for i in range(2, MAX):
	if nxt[i] < i:
		continue
	for j in range(i, MAX, i):
		nxt[j] = min(nxt[j], i)

fac = set()
ok = True
for x in a:
	tmp = set()
	while x > 1:
		tmp.add(nxt[x])
		x //= nxt[x]
	for p in tmp:
		if p in fac:
			ok = False
			break
		fac.add(p)
	if not ok:
		break
print("pairwise coprime" if ok else "setwise coprime")

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

N = int(input())
A = map(int, input().split())
M = 10**6
smallest_prime = [0] * (M+1)
for i in range(2, M+1):
    if smallest_prime[i] == 0:
        smallest_prime[i] = i
        for j in range(i*i, M+1, i):
            smallest_prime[j] = i

cnt = [0] * (M+1)
for a in A:
    while a > 1:
        p = smallest_prime[a]
        cnt[p] += 1
        while a % p == 0:
            a //= p

if all(c <= 1 for c in cnt):
    print('pairwise coprime')
elif all(c < N for c in cnt):
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
def gcd(x, y):
  b = max(x, y)
  s = min(x, y)
  r = b % s
  while r != 0:
    b = s
    s = r
    r = b % s
  return s

def lcm(x, y):
  return (x * y) // gcd(x,y)

import math
def prime(x):
  p = {}
  last = math.floor(x ** 0.5)
  if x % 2 == 0:
    cnt = 1
    x //= 2
    while x & 1 == 0:
      x //= 2
      cnt += 1
    p[2] = cnt
  for i in range(3, last + 1, 2):
    if x % i == 0:
      x //= i
      cnt = 1
      while x % i == 0:
        cnt += 1
        x //= i
      p[i] = cnt
  if x != 1:
    p[x] = 1
  return p

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

R = {}
F = True
for i in A:
  p = prime(i)
  for j in p.keys():
    if j in R:
      F = False
      break
    else:
      R[j] = 1
  else:
    continue
  break

if F:
  print("pairwise coprime")
  exit()

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

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

Solution (Python):
from math import gcd

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


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

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

pair = True

for i in range(2,10**6+1):
    check = 0
    for j in range(1,(10**6)//i+1):
        check += data[i*j]
    if check>1:
        pair = False

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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


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)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


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


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N = I()
A = IL()

g = A[0]
for a in A[1:]:
  g = gcd(g,a)
  
if g != 1:
  print("not coprime")
  exit()
else:
  bag = DD(int)
  for a in A:
    if a == 1: continue
    for p,n in factorization(a):
      if bag[p]:
        print("setwise coprime")
        exit()
      else:
        bag[p] = 1
  print("pairwise coprime")

Solution (Python):
from math import gcd

N=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(N):
  if A[i]!=1:
    B.append(A[i])
F1=1
F2=0
X=A[0]
for i in range(N):
  X=gcd(X,A[i])
if X==1:
  F2=1
def f(x):
  r=[]
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      r.append(i)
      while x%i==0:
        x//=i
  if x!=1:
    r.append(x)
  return r

D=dict()
if len(B)>=80000:
  if F2:
    print('setwise coprime')
  else:
    print('not coprime')
  exit()
for i in range(len(B)):
  B[i]=f(B[i])
  for j in range(len(B[i])):
    if D.get(B[i][j],0):
      F1=0
      break
    D[B[i][j]]=1
  if F1==0:
    break
if F1:
  print('pairwise coprime')
elif F2:
  print('setwise coprime')
else:
  print('not coprime')

Solution (Python):
from math import gcd

n = int(input())


def p(x):
    a = []
    i = 2
    while True:
        if x % i == 0:
            j = 0
            while x % i == 0:
                x //= i
                j += 1
            a.append((i, j))
        if i * i > x:
            break
        i += 1
    if x != 1:
        a.append((x, 1))
    return a


pp = set()
a = [int(i) for i in input().split()]

j = 0
for i in a:
    j = gcd(j, i)
ok1 = j == 1

ma = 2*10**6
table = [0]*ma
for i in a:
    table[i] += 1
ok2 = True
for i in range(2,ma):
    s = 0
    for j in range(i,ma,i):
        s += table[j]
    if s>1:
        ok2 = False

if ok2:
    print("pairwise coprime")
else:
    if ok1:
        print("setwise coprime")
    else:
        print("not coprime")

Solution (Python):
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]


from collections import defaultdict as ddic, Counter, deque
import heapq, bisect, itertools
MOD = 10 ** 9 + 7

def solve(N, A):
    from fractions import gcd
    g  = A[0]
    for x in A:
        g=  gcd(g,x)
    if g > 1:
        return "not coprime"

    seen = set()
    for x in A:
        saw = set()
        while x % 2 == 0:
            x //= 2
            saw.add(2)
        d = 3
        while d*d <= x:
            while x%d == 0:
                saw.add(d)
                x //= d
            d += 2
        if x > 1:
            saw.add(x)

        for p in saw:
            if p in seen:
                return "setwise coprime"
        seen |= saw

    return "pairwise coprime"

N= rri()
A = rrm()

print solve(N, A)

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def is_pair_copr(A):
    U = 1 << 20
    div_p = np.arange(U)
    for p in range(2, U):
        if div_p[p] != p:
            continue
        div_p[p::p] = p
    used = np.zeros(U, np.bool_)

    for x in A:
        while x > 1:
            p = div_p[x]
            while x % p == 0:
                x //= p
            if used[p]:
                return False
            used[p] = True
    return True

def main(A):
    U = 1 << 20
    
    pair = is_pair_copr(A)
    g = np.gcd.reduce(A)
    se = g == 1
    if pair:
        return 'pairwise coprime'
    if se:
        return 'setwise coprime'
    return 'not coprime'

A = np.array(read().split(), np.int64)[1:]

print(main(A))

Solution (Python):


import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*a = map(int,read().split())

M = 10**6
r = [0]*(M+1)
for i in a:
    r[i] += 1


isp = True
for x in range(2,M+1):
    c = sum(r[x::x])
    if c == n:
        print("not coprime")
        exit()
    if c >= 2:
        isp = False
else:
    if isp:
        print("pairwise coprime")
    else:
        print("setwise coprime")