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

N=int(input())
A = list(map(int,input().split()))
 
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

if gcd_list(A) > 1:
    print("not coprime")
    sys.exit()

D = [i for i in range(max(A)+1)] 
p = 2
 
while(p*p<=max(A)):
    if D[p]==p:
        for i in range(2*p,max(A)+1,p):
            if D[i]==i:
                D[i]=p
 
    p+=1
    
prime = set()
for a in A:
    tmp=D[a]
    L=set()
    while(a>1):
        a=a//tmp
        L.add(tmp)
        tmp=D[a]

    for l in L:
        if l in prime:
            print("setwise coprime")
            sys.exit()
        else:
            prime.add(l)

print("pairwise coprime")

Solution (Python):
import sys

N=int(input())
A = list(map(int,input().split()))
 
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

if gcd_list(A) > 1:
    print("not coprime")
    sys.exit()

D = [i for i in range(max(A)+1)] 
p = 2
 
while(p*p<=max(A)):
    if D[p]==p:
        for i in range(p*p,max(A)+1,p):
            if D[i]==i:
                D[i]=p
 
    p+=1
    
prime = set()
for a in A:
    tmp=D[a]
    L=set()
    while(a>1):
        a=a//tmp
        L.add(tmp)
        tmp=D[a]

    for l in L:
        if l in prime:
            print("setwise coprime")
            sys.exit()
        else:
            prime.add(l)

print("pairwise coprime")

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
class Sieve: 
    def __init__(self,n): 
        self.primes=[]
        self.f=[0]*(n+1) 
        self.f[0]=self.f[1]=-1
        self.f_lis = [0]*(n+1)
        for i in range(2,n+1): 
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,n+1,i):
                if not self.f[j]:
                    self.f[j]=i  
    def prime_fact(self,A): 
        for x in A:
            while x!=1:
                p=self.f[x]
                x//=p
                if x % p > 0:
                    if self.f_lis[p] > 0: return False
                    self.f_lis[p] += 1
        return True

import math
from functools import reduce
def gcd_all(numbers):
    return reduce(math.gcd, numbers)

def main():
    n = int(input())
    A = list(map(int,input().split())) 
    Sieve_a = Sieve(max(A)+1)
    if Sieve_a.prime_fact(A):
        print("pairwise coprime")
    elif gcd_all(A) == 1:
        
        print("setwise coprime")   
    else:
        print("not coprime")

if __name__=='__main__':
    main()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def primeFactorization(n):
    D = list(range(n + 1))
    for i in range(2, int(n ** 0.5) + 1):
        if D[i] == i:
            for j in range(i, n + 1, i):
                if D[j] == j:
                    D[j] = i
    return D

def resolve():
    N = I()
    A = LI()

    
    is_pc = True
    D = primeFactorization(max(A))
    pf = set()
    for i in A:
        tmp = i
        cnt = collections.Counter()
        while tmp != 1:
            cnt[D[tmp]] += 1
            tmp //= D[tmp]
        fact = set(cnt.keys())
        if pf & fact:
            is_pc = False
            break
        else:
            pf |= fact
    
    
    is_sc = False
    if not is_pc:
        gcd = A[0]
        for i in A[1:]:
            gcd = math.gcd(i, gcd)
        if gcd == 1:
            is_sc = True

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

if __name__ == '__main__':
    resolve()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a.sort()
dp = [0 for i in range(a[-1])]
p = [0 for i in range(a[-1])]
for i in range(n):
    p[a[i]-1] += 1
ans = 1
for i in range(2,a[-1]+1):
    if dp[i-1] == 1:
        continue
    u = 0
    k = 1
    while i*k <= a[-1]:
        dp[i*k-1] = 1
        if p[i*k-1] != 0:
            u += p[i*k-1]
        k += 1
    if u == n:
        ans = -1
    elif u > 1:
        ans = min(ans,0)
if ans == 1:
    print('pairwise coprime')
elif ans == 0:
    print('setwise coprime')
elif a[0] == 1:
    print('setwise coprime')
else:
    print('not coprime')

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

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

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

D = [i for i in range(max(A)+1)]
p = 2

while(p*p<=max(A)):
    if D[p]==p:
        for i in range(2*p,len(D),p):
            if D[i]==i:
                D[i]=p

    p+=1

prime = set()
for a in A:
    tmp=D[a]
    L=set()
    while(a>1):
        a=a//tmp
        L.add(tmp)
        tmp=D[a]
    
    for l in L:
        if l in prime:
            
            
            print("setwise coprime")
            exit()
        else:
            prime.add(l)


print("pairwise coprime")

Solution (Python):
import sys
import numpy as np
i4 = np.int32
i8 = np.int64
u4 = np.uint32

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    from numba import njit
    from numba.types import Array, int32, int64, uint32
    cc = CC('my_module')

    @njit
    def get_factorization(n):
        """
        nまでの割り切れる最小の素数を返す。
        """
        sieve_size = (n - 1) // 2
        sieve = np.zeros(sieve_size, u4)
        for i in range(sieve_size):
            if sieve[i] == 0:
                value_at_i = i*2 + 3
                for j in range(i, sieve_size, value_at_i):
                    if sieve[j] == 0:
                        sieve[j] = value_at_i
        return sieve


    @cc.export('solve', (Array(uint32, 1, 'C'),))
    @njit('(u4[::-1],)', cache=True)
    def solve(A):
        a = np.sort(A)
        p_max = a[-1]
        p = get_factorization(p_max)
        primes_num = 1
        for i in range(p.shape[0]):
            if i*2 + 3 == p[i]:
                primes_num += 1
        a_start = 0
        while a[a_start] == 1:
            a_start += 1
            if a_start == a.shape[0]:
                return 0
        a = a[a_start:]
        if len(a) > primes_num:
            return 1
        check = np.zeros(p_max + 1, u4)
        for d in a:
            if d & 1 == 0:
                check[2] += 1
                d //= 2
                while d & 1 == 0:
                    d //= 2
            prev = 2
            while d > 1:
                i = (d - 3) // 2
                f = p[i]
                if f > prev:
                    check[f] += 1
                    prev = f
                d //= f

        if check.max() > 1:
            return 1
        else:
            return 0

    cc.compile()
    exit(0)

else:
    from my_module import solve


def main(in_file):
    stdin = open(in_file)
    stdin.readline()
    A = np.fromstring(stdin.readline(), u4, sep=' ')
    ans = solve(A)
    if ans:
        g = np.gcd.reduce(A)
        if g > 1:
            ans = 2
        else:
            ans = 1
    p = ['pairwise coprime', 'setwise coprime', 'not coprime']
    print(p[ans])


main(0)

Solution (Python):
import numpy as np
from numba import njit
i4 = np.int32
i8 = np.int64
u4 = np.uint32


@njit
def get_factorization(n):
    """
    nまでの割り切れる最小の素数を返す。
    """
    sieve_size = (n - 1) // 2
    sieve = np.zeros(sieve_size, u4)
    for i in range(sieve_size):
        if sieve[i] == 0:
            value_at_i = i*2 + 3
            for j in range(i, sieve_size, value_at_i):
                if sieve[j] == 0:
                    sieve[j] = value_at_i
    return sieve


@njit('(u4[::-1],)', cache=True)
def solve(A):
    a = np.sort(A)
    p_max = a[-1]
    p = get_factorization(p_max)
    primes_num = 1
    for i in range(p.shape[0]):
        if i*2 + 3 == p[i]:
            primes_num += 1
    a_start = 0
    while a[a_start] == 1:
        a_start += 1
        if a_start == a.shape[0]:
            return 0
    a = a[a_start:]
    if len(a) > primes_num:
        return 1
    check = np.zeros(p_max + 1, u4)
    for d in a:
        if d & 1 == 0:
            check[2] += 1
            d //= 2
            while d & 1 == 0:
                d //= 2
        prev = 2
        while d > 1:
            i = (d - 3) // 2
            f = p[i]
            if f > prev:
                check[f] += 1
                prev = f
            d //= f

    if check.max() > 1:
        return 1
    else:
        return 0


def main(in_file):
    stdin = open(in_file)
    stdin.readline()
    A = np.fromstring(stdin.readline(), u4, sep=' ')
    ans = solve(A)
    if ans:
        g = np.gcd.reduce(A)
        if g > 1:
            ans = 2
        else:
            ans = 1
    p = ['pairwise coprime', 'setwise coprime', 'not coprime']
    print(p[ans])


if __name__ == '__main__':
    main('/dev/stdin')

Solution (Python):
import numpy as np
from numba import njit
i4 = np.int32
i8 = np.int64
u4 = np.uint32


@njit
def get_factorization(n):
    """
    nまでの割り切れる最小の素数を返す。
    """
    sieve_size = (n - 1) // 2
    sieve = np.zeros(sieve_size, u4)
    for i in range(sieve_size):
        if sieve[i] == 0:
            value_at_i = i*2 + 3
            for j in range(i, sieve_size, value_at_i):
                if sieve[j] == 0:
                    sieve[j] = value_at_i
    return sieve


@njit
def solve(A):
    a = np.sort(A)
    p_max = a[-1]
    p = get_factorization(p_max)
    primes_num = 1
    for i in range(p.shape[0]):
        if i*2 + 3 == p[i]:
            primes_num += 1
    a_start = 0
    while a[a_start] == 1:
        a_start += 1
        if a_start == a.shape[0]:
            return 0
    a = a[a_start:]
    if len(a) > primes_num:
        return 1
    check = np.zeros(p_max + 1, u4)
    for d in a:
        if d & 1 == 0:
            check[2] += 1
            d //= 2
            while d & 1 == 0:
                d //= 2
        prev = 2
        while d > 1:
            i = (d - 3) // 2
            f = p[i]
            if f > prev:
                check[f] += 1
                prev = f
            d //= f

    if check.max() > 1:
        return 1
    else:
        return 0


def main(in_file):
    stdin = open(in_file)
    stdin.readline()
    A = np.fromstring(stdin.readline(), u4, sep=' ')
    ans = solve(A)
    if ans:
        g = np.gcd.reduce(A)
        if g > 1:
            ans = 2
        else:
            ans = 1
    p = ['pairwise coprime', 'setwise coprime', 'not coprime']
    print(p[ans])


if __name__ == '__main__':
    main('/dev/stdin')

Solution (Python):
import sys
input = sys.stdin.readline
 
MAX = pow(10,6)

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


import math
N = int(input())
A = list(map(int,input().split()))
GCD = math.gcd(A[0],A[1])
for i in range(2,N):
  GCD = math.gcd(GCD,A[i])
  if GCD == 1:
    break
if GCD != 1:
  print("not coprime")
  exit()
A.sort()
SET = set([])
for x in A:
  SL = factorization(x)
  for yakusu in SL:
    if yakusu not in SET:
      SET.add(yakusu)
    else:
      print("setwise coprime")
      exit()
print("pairwise coprime")

Solution (Python):
import sys
input = sys.stdin.readline
 
MAX = pow(10,6)

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


import math
N = int(input())
A = list(map(int,input().split()))
GCD = math.gcd(A[0],A[1])
for i in range(2,N):
  GCD = math.gcd(GCD,A[i])
  if GCD == 1:
    break
if GCD != 1:
  print("not coprime")
  exit()

SET = set([])
for x in A:
  SL = factorization(x)
  for yakusu in SL:
    if yakusu not in SET:
      SET.add(yakusu)
    else:
      print("setwise coprime")
      exit()
print("pairwise coprime")

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

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

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

MAXN = 10**6 + 9
D = [i for i in range(MAXN+1)]
p = 2
while(p*p <=MAXN):
    if D[p]==p:
        for q in range(2*p,MAXN+1,p):
            if D[q]==q:
                D[q]=p
    p+=1

st = set()
for a in A:
    tmp = set()
    while(a>1):
        tmp.add(D[a])
        a //=D[a]
    for p in tmp:
        if p in st:
            print("setwise coprime")
            exit()
        st.add(p)

print("pairwise coprime")

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7

n=I()
A=LI()
l=A[0]
num=[0]*(10**6+1)
for i in range(1,n):
    num[A[i]]+=1
    l=gcd(l,A[i])



if l!=1:
    print("not coprime")
    exit()


for j in range(2,10**6):
    ret=0
    for k in range(j,10**6+1,j):
        ret+=num[k]
    if ret>1:
        print("setwise coprime")
        exit()

print("pairwise coprime")

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
MAX_A = max(a)
divide_minimam_prime = [i for i in range(MAX_A + 1)]
is_prime = [True for i in range(MAX_A + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(2,int(MAX_A**0.5) + 1):
    if is_prime[div]:
        
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= MAX_A:
            is_prime[k] = False
            if divide_minimam_prime[k] == k:
                divide_minimam_prime[k] = div
            k += div

pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(divide_minimam_prime[k])
        div = divide_minimam_prime[k]
        while k % div == 0 and k > 1:
            k = k // div
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    pr = [0]*(max(a)+1)
    flag = True
    for num in a:
        pr[num] += 1
    for i in range(2, max(a)+1):
        count = sum(pr[i::i])
        if count == N:
            print("not coprime")
            exit()
        elif count > 1:
            flag = False
    if flag:
        print("pairwise coprime")
    else:
        print("setwise coprime")

if __name__ == "__main__":
    main()

Solution (Python):
def main():

    import os
    import sys
    from io import BytesIO, IOBase
    
    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")
    mod = 10**9 + 7

    import sys
    input = lambda: sys.stdin.readline().rstrip("\r\n")

    from math import gcd

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

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

    primes = set()

    flag = 1

    for i in a:
        prime_factors = set(prime_factorize(i))
        for j in prime_factors:
            if j in primes:
                flag = 0
            else:
                primes.add(j)


    if flag:
        print('pairwise coprime')
        sys.exit()
                
    
    import math
    from functools import reduce
    
    def gcd(*numbers):
        return abs(reduce(math.gcd, numbers))
    
    if gcd(*a) == 1:
        print('setwise coprime')
    else:
        print('not coprime')

main()

Solution (Python):
def main():

    import sys
    input = lambda: sys.stdin.readline().rstrip("\r\n")

    from math import gcd

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

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

    primes = set()

    flag = 1

    for i in a:
        prime_factors = set(prime_factorize(i))
        for j in prime_factors:
            if j in primes:
                flag = 0
            else:
                primes.add(j)


    if flag:
        print('pairwise coprime')
        sys.exit()
                
    
    import math
    from functools import reduce
    
    def gcd(*numbers):
        return abs(reduce(math.gcd, numbers))
    
    if gcd(*a) == 1:
        print('setwise coprime')
    else:
        print('not coprime')

main()

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



MAXX = 10**6 + 1
MAXZ = int(math.sqrt(MAXX)+2)
furui = [[] for _ in range(MAXX)]

furui[1].append(1)
count = [0]*MAXX
for i in range(2, MAXX):
    if len(furui[i]) == 0:
        for k in range(i, MAXX, i):
            furui[k].append(i)

setwise = True
pairwise = True
for i in range(N):
    if not setwise and not pairwise: break
    for fu in furui[num[i]]:
        count[fu] += 1
        if fu > 1 and count[fu] >= N:
            setwise = False
            pairwise = False
            break
        elif fu > 1 and count[fu] > 1:
            pairwise = False

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

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

from math import gcd

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

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

primes = set()

flag = 1

for i in a:
    prime_factors = set(prime_factorize(i))
    for j in prime_factors:
        if j in primes:
            flag = 0
        else:
            primes.add(j)


if flag:
    print('pairwise coprime')
    sys.exit()
            
 
import math
from functools import reduce
 
def gcd(*numbers):
    return abs(reduce(math.gcd, numbers))
 
if gcd(*a) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
import math
a=A[0]
for i in range(1,N):
  a=math.gcd(a,A[i])
def f():
  a=A[0]
  for i in range(1,N):
    a=math.gcd(a,A[i])
  if a==1:
    print("setwise coprime")
    exit()
  else:
    print("not coprime")
    exit()
  
D=[0]*(10**6+1)
for i in range(2,10**6+1):
  for j in range(2*i,10**6+1,i):
    if D[j]==0:
      D[j]=i
for i in range(10**6+1):
  if D[i]==0:
    D[i]=i

s=set()
import copy
for i in range(N):
  tmp=set()
  k=A[i]
  while k>1:
    tmp.add(D[k])
    k=k//D[k]
  for i in tmp:
    if i in s:
      f()
    else:
      s.add(i)


print("pairwise coprime")

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

from math import gcd
n = int(input())
a = list( map(int, input().split()))


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

MAXN = 10**6+10

def eratosthenes3(limit):
    sieve = [i for i in range(limit+1)]
    p = 2
    while p*p <= limit:
        if sieve[p] == p:
            for q in range(2*p,limit+1,p):
                if sieve[q] == q:
                    sieve[q] = p
        p += 1

    return sieve

sieve = eratosthenes3(MAXN)

st = set()
for aa in a:
    tmp = set()
    while aa > 1:
        tmp.add(sieve[aa])
        aa //= sieve[aa]
    for p in tmp:
        if p in st:
            print('setwise coprime')
            exit()
        st.add(p)
print('pairwise coprime')

Solution (Python):
def abc177_e():
    n = int(input())
    A = [int(x) for x in input().split()]

    def prime_factorize(n:int)->set:
        ''' nの素因数分解 '''
        arr = []
        while n % 2 == 0:
            arr.append(2)
            n = n // 2
        f = 3
        while f*f <= n:
            if n%f == 0:
                arr.append(f)
                n = n // f
            else:
                f += 2
        if n != 1:
            arr.append(n)
        return set(arr)

    import math
    gcd_all = A[0]
    factors = [0]*(10**6 + 1)
    pairwise = True

    for ai in A:
        gcd_all = math.gcd(gcd_all, ai)
        for p in prime_factorize(ai):
            if factors[p]: pairwise = False
            factors[p] = 1

    if pairwise: ans = 'pairwise coprime'
    elif gcd_all == 1: ans = 'setwise coprime'
    else: ans = 'not coprime'
    print(ans)

if __name__ == '__main__':
    abc177_e()

Solution (Python):
from math import gcd

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

prime = list(range(max(A) + 1))

for i in range(2, len(prime)):
    if prime[i] != i:
        continue
    for j in range(i, len(prime), i):
        if prime[j] != j:
            continue
        prime[j] = i

used = set()
pc = True
for a in A:
    used_this = set()
    while a != 1:
        div = prime[a]
        if div in used:
            pc = False
            break
        used_this.add(div)
        a //= div
    used.update(used_this)

if pc:
    print('pairwise coprime')
    exit()

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

Solution (Python):
from math import gcd
MAX = 10**6

sieve = [i for i in range(MAX+1)]

p = 2
while p * p <= MAX:
    if sieve[p] == p:
        for i in range(p*2, MAX+1, p):
            if sieve[i] == i:
                sieve[i] = p
    p += 1


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

for a in A:
    tmp = set()
    b = a
    while b != 1:
        tmp.add(sieve[b])
        b //= sieve[b]
    pf.append(tmp)


soin = [0] * (10 ** 6 + 1)
for f in pf:
    for n in f:
        soin[n] += 1

if max(soin[2:]) <= 1:
    print('pairwise coprime')
    exit()


setwise = A[0]

for a in A:
    setwise = gcd(setwise, a)
    
if setwise == 1:
    print('setwise coprime')
else:
    print('not coprime')

Solution (Python):
import math
n = int(input())
a = list(map(int, input().split()))
nmax = 10**6

check = [0]*(nmax + 5)
for i in a:
    check[i] += 1

pairwise = True
for i in range(2, nmax + 5):
    cnt = 0
    for j in range(i, nmax + 5, i):
        cnt += check[j] 
    if cnt > 1:
        pairwise = False

if pairwise == True:
    print('pairwise coprime')
    exit()

x = 0
for i in a:
    x = math.gcd(x,i)
if x == 1:
    print('setwise coprime')
else:
    print('not coprime')

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

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5) 
    data = [i + 1 for i in range(2, n, 2)] 
    while True:
        p = data[0]
        if limit < p: 
            return prime + data
        prime.append(p) 
        data = [e for e in data if e % p != 0] 

MAX = pow(10,6)


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



import math
N = int(input())
A = list(map(int,input().split()))
GCD = math.gcd(A[0],A[1])
for i in range(2,N):
  GCD = math.gcd(GCD,A[i])
  if GCD == 1:
    break
if GCD != 1:
  print("not coprime")
  exit()
A.sort()
SET = set([])
for x in A:
  SL = factorization(x)
  for yakusu in SL:
    if yakusu not in SET:
      SET.add(yakusu)
    else:
      print("setwise coprime")
      exit()
print("pairwise coprime")

Solution (Python):

def gen_factorization(N):
    tables=[-1]*(N+1)
    for i in range(2,N+1):
        if tables[i]!=-1:continue
        tmp=i
        while tmp<=N:
            tables[tmp]=i
            tmp+=i
    def fuctorization(n):
        if n==1:return {1:1}
        elif n<0:n=abs(n)
        if n>N:return "error"
        ans={}
        while n!=1:
            tmp=tables[n]
            
            
            ans.setdefault(tmp,0)
            ans[tmp]+=1
            n//=tmp
        return ans
    return fuctorization

N=int(input())
f=gen_factorization(10**6+10)
A=list(map(int,input().split()))
primes={}
for i in A:
  d=f(i)
  for j in d:
    primes.setdefault(j,0)
    primes[j]+=1
primes[1]=1
ansMax=max(primes.values())

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