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.



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Accepted

Solution code:
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)
    #[(p1,n1),(p2,n2),...]の形で返す
    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()

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
#!/usr/bin/env python
#pyrival orz
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")
# region fastio

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

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
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)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

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

######Combination######
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

######Factorization######
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

#####MakeDivisors######
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

#####MakePrimes######
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

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

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

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

#####ChangeBase#####
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]

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

#############
# Main Code #
#############
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")

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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
    # a prime factor of N
    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))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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")

Submission status: Runtime Error

Solution code:
# import itertools
import math
import functools import reduce
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# import heapq
# from collections import deque

N = int(input())
# S = input()
# n, *a = map(int, open(0))
# N, M = map(int, input().split())
A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# 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 gcd_list(numbers):
    return reduce(math.gcd, numbers)

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


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

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

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

A_max = A[-1]
prime = [[] for _ in range(A_max + 1)]
for i in range(2,A_max + 1):
    if prime[i] == []:
        n = i
        while n <= A_max:
            prime[n].append(i)
            n += i

li = [0] * (A_max + 1)
for a in A:
    for p in prime[a]:
        li[p] += 1

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

Submission status: Runtime Error

Solution code:
    from math import gcd
    def lcm(a,b):
        return a*b//gcd(a,b)

    def main():
        n = int(input())
        A = list(map(int,input().split()))
        LCM = 1
        GCD = A[-1]
        flag = True
        for a in A[::-1]:
            if gcd(LCM,a) > 1:
                flag = False
                break
            LCM = lcm(LCM,a)
            GCD = gcd(GCD,a)
        if flag:
            print("pairwise coprime")
        elif GCD == 1:
            print("setwise coprime")
        else:
            print("not coprime")
        return

    if __name__ == "__main__":
        main()

Submission status: Runtime Error

Solution code:
import math

def eratosthenes():
    erat = [0 for _ in range(max(a)+1)]
    lim = int(math.sqrt(max(set_a)))
    for i in range(2, lim+1):
        cnt = 0
        if not erat[i]:
            for res in range(i, max(set_a)+1, i):
                if res in set_a:
                    cnt += 1
                erat[i] = i
                if cnt > 2:
                    break
        else:
            continue
        break
    return cnt


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

ans = eratosthenes()

if max(ans.values()) == 1 and len(set_a) == n:
    print('pairwise coprime')
else:
    res = a[0]
    for i in range(n):
        res = math.gcd(res, a[i])
    if res == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Runtime Error

Solution code:
# import numpy as np
import sys, math, heapq
from functools import reduce
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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


def era(N):
    A = list(range(2, N + 1))
    p = list()
    while A[0] ** 2 <= N:
        tmp = A[0]
        p.append(tmp)
        A = [e for e in A if e % tmp != 0]
    return p + A


plist = era(max(A))


def fctr1(n):
    f = []
    c = 0
    r = int(n ** 0.5)
    # for i in range(2, r + 2):
    for i in plist:
        if i >= r + 2:
            break
        while n % i == 0:
            c += 1
            n = n // i
        if c != 0:
            f.append([i, c])
            c = 0
    if n != 1:
        f.append([n, 1])
    return f


fctA = [fctr1(a) for a in A]
pfactors = defaultdict(int)
is_pc = True
for fcta in fctA:
    if not (is_pc):
        break
    for p in fcta:
        pn = p[0]
        if pfactors[pn] > 0:
            is_pc = False
            break
        else:
            pfactors[pn] += 1
if is_pc:
    print("pairwise coprime")
else:
    is_sc = reduce(gcd, A) == 1
    if is_sc:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Runtime Error

Solution code:
import math

def eratosthenes():
    cnt = dict()
    lim = int(math.sqrt(max(set_a)))
    for i in range(2, lim+1):
        for res in range(i, max(set_a)+1, i):
            if res in set_a:
                cnt[res] = cnt.get(res, 0) + 1
    return cnt


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

ans = eratosthenes()

if max(ans.values()) == 1 and len(set_a) == n:
    print('pairwise coprime')
else:
    res = a[0]
    for i in range(n):
        res = math.gcd(res, a[i])
    if res == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Runtime Error

Solution code:
from collections import *
def gcd(a,b):
    if a%b==0:return(b)
    else:return(gcd(b,a%b))

def soinsuu(n):
    visited=defaultdict(int)
    for i in range(2,round(n**.5)+1):
        while n%i==0:
            n//=i
            visited[i]+=1
    if n>1:
        visited[n]+=1
    return(visited)

N=int(input())
A=list(map(int,input().split()))
A=[soinsuu(a) for a in A]
visited=set()
flg=False
for a in A:
    for i in a:
        if i in visited:
            flg=True
            break
        else:
            visited.add(i)

    if flg:
        break
else:
    print("pairwise coprime")
    exit()

n=a[0]
for a in A[1:]:
    n=gcd(n,a)



if n>1:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Runtime Error

Solution code:
from collections import *
def gcd(a,b):
    if a%b==0:return(b)
    else:return(gcd(b,a%b))

def soinsuu(n):
    visited=defaultdict(int)
    for i in range(2,round(n**.5)+1):
        while n%i==0:
            n//=i
            visited[i]+=1
    if n>1:
        visited[n]+=1
    return(visited)

N=int(input())
A=list(map(int,input().split()))
A=[soinsuu(a) for a in A]
visited=set()
flg=False
for a in A:
    for i in a:
        if i in visited:
            flg=True
            break
        else:
            visited.add(i)

    if flg:
        break
else:
    print("pairwise coprime")
    exit()

visited=soinsuu(A[0])
for a in A[1:]:
    for i in a:
        visited[i]-=data[i]

if [i for i in visited if visited[i]>0]:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
from math import sqrt
from collections import Counter

def gen_primes(X):
    D = [0] * (X+1)
    is_prime = [True for _ in range(0, X+1)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for n in range(2, int(sqrt(X))+1):
        if is_prime[n]:
            primes.append(n)
            j = n*2
            D[n] = n
            while j <= X:
                is_prime[j] = False
                if D[j] == 0:
                    D[j] = n
                j += n
    for n in range(int(sqrt(X)), X+1):
        if is_prime[n]:
            D[n] = n
            primes.append(n)
    return primes, D


def solve(A):
    N = len(A)
    primes, D = gen_primes(10**6)
    C = Counter()

    for a in A:
        a_ = a
        while a > 1:
            d = D[a]
            while a % d == 0:
                a //= d
            C[d] += 1
        
    M = max(v for k, v in C.items())
    if M <= 1:
        print("pairwise coprime")
    elif M != N:
        print("setwise coprime")
    else:
        print("not coprime")

N = int(input())
A = [int(x) for x in input().split()]
solve(A)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
from math import sqrt

def gen_primes(X):
    D = [0] * (X+1)
    is_prime = [True for _ in range(0, X+1)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for n in range(2, int(sqrt(X))+1):
        if is_prime[n]:
            primes.append(n)
            j = n*2
            D[n] = n
            while j <= X:
                is_prime[j] = False
                if D[j] == 0:
                    D[j] = n
                j += n
    for n in range(int(sqrt(X)), X+1):
        if is_prime[n]:
            D[n] = n
            primes.append(n)
    return primes, D


def solve(N, A):
    primes, D = gen_primes(10**6)
    C = [0] * len(primes)

    for a in A:
        while a > 1:
            d = D[a]
            while a % d == 0:
                a //= d
            C[d] += 1
        
    M = max(C)
    if M <= 1:
        print("pairwise coprime")
    elif M != N:
        print("setwise coprime")
    else:
        print("not coprime")

N = int(input())
A = [int(x) for x in input().split()]
solve(N, A)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
from math import sqrt

def gen_primes(X):
    D = [0] * (X+1)
    is_prime = [True for _ in range(0, X+1)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for n in range(2, int(sqrt(X))+1):
        if is_prime[n]:
            primes.append(n)
            j = n*2
            D[n] = n
            while j <= X:
                is_prime[j] = False
                if D[j] == 0:
                    D[j] = n
                j += n
    for n in range(int(sqrt(X)), X+1):
        if is_prime[n]:
            D[n] = n
            primes.append(n)
    return primes, D


def solve(N, A):
    primes, D = gen_primes(10**6)
    C = [0] * len(primes)

    for a in A:
        while a != 1:
            d = D[a]
            while a % d == 0:
                a //= d
            C[d] += 1
        
    M = max(C)
    if M <= 1:
        print("pairwise coprime")
    elif M != N:
        print("setwise coprime")
    else:
        print("not coprime")

N = int(input())
A = [int(x) for x in input().split()]
solve(N, A)