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: Runtime Error

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
setA = set(A)

#pairwiseかどうかを調べる
memo = [1]*(10**6+1)
memo[0] = 0
memo[1] = 0
for i in range(2,10**6+1):
    if memo[i] == 1:
        flag = False
        if i in setA:
            flag = True
        for j in range(i*2,10**6+1,i):
            if j in setA:
                if flag:
                    break
                else:
                    flag = True
            memo[j] = 0
        else:
            continue
        break
elif len(setA) == len(A):
    print("pairwise coprime")
    exit()



#setwise coprimeを判断
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

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

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

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

cut = [0 for _ in range(MAX+1)]
for i in range(2, MAX+1, 2):
    if cut[i] != 0:
        continue
    for j in range(i, MAX+1, i):
        cut[j] = i

if reduce(math.gcd, A) != 1:
    print('not coprime')
    exit()

already = set()
for a in A:
    now = set()
    while a != 1:
        if cut[a] in already:
            print('setwise coprime')
            exit()
        a //= cut[a]
        now.add(cut[a])
    already |= now

print('pairwise coprime')

Submission status: Runtime Error

Solution code:
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] == 1:
            u += 1
        k += 1
    if u == n:
        ans = -1
    elif u > 1:
        ans = min(ans,0)
elif ans == 1:
    print('pairwise coprime')
elif ans == 0:
    print('setwise coprime')
elif a[0] == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def soinsubunkai_e(n,m): #高速素因数分解 m[n]=nを割ることの出来る最小の素数
    a = set()
    i = 1
    while n>1:
        a.add(m[n])
        n=n//m[n]
    nokori=n
    a.add(nokori)
    return a

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def era(n): #b[n]=nを割ることの出来る最小の素数　の配列を生成　エラトステネスの篩
    b=[i for i in range(n+1)]
    for i in range(2,int(math.sqrt(n)+10)):
        j=1
        temp=i*j
        while temp<=n:
            b[temp]=min(i,b[temp])
            temp+=i
    return b


def main():
    #l,r,d=map(int,input().split())
    n=int(input())
    a=list(map(int,input().split()))
    sosu=[]
    memo = defaultdict(int)
#    ccc=era(10**6)
    ans=0
    for i in range(n):
        if a[i]!=1:
            temp=set(soinsubunkai(a[i]))
        else:
            temp={}
        for j in temp:
            memo[j]+=1
        memo.pop(1,None)
        if max(memo.values())>=2:
            ans=1
            break
    if ans==1:
        temp2=math.gcd(a[0],a[1])
        if n>=3:
            for i in range(2,n):
                temp2=math.gcd(temp2,a[i])
        if temp2==1:
            ans=2


    memo.pop(1,None)
 #   print(sosu)
 #   print(memo)
 #   print(memo.values())
    if len(memo)>=1:
        mmm=max(memo.values())
    else:
        mmm=1
    if mmm<=1 and ans==0:
        print("pairwise coprime")
    elif ans==1:
        print("not coprime")
    elif mmm<n or ans==2:
        print("setwise coprime")
    else:
        print("not coprime")








if __name__ == "__main__":

    main()

Submission status: Runtime Error

Solution code:

def find_gcd(x, y): 
    while(y): 
        x, y = y, x % y 
    return x 
def fun(l):
  num1=l[0] 
  num2=l[1] 
  gcd=find_gcd(num1,num2) 

  for i in range(2,len(l)):
    gcd=find_gcd(gcd,l[i])
  if gcd==1:
    print("setwise coprime")
    return 1
  for i range(len(l)-1):
    gcd=find_gcd(l[i],l[i+1])
    if gcd!=1:
      break;
  else:
    print("pairwise coprime")
    return 1
n=int(input())
l=[]
for in range(n):
  temp=int(input())
  l.append(temp)
x=fun(l)
if x!=1:
  print("not coprime")

Submission status: Runtime Error

Solution code:
# ABC_177_E_3.py

# 解説を見て高速素因数分解を実装する

D = [0]*(10**6+1)
L = [True]*(10**6+1)
L[0] = False
L[1] = False
D[1] = 1
for i in range(2, 10**6+1):
    if L[i]:
        D[i] = i
        for j in range(i*2, 10**6+1, i):
            L[j] = False
            D[j] = i


def egcd(a, b):
    if a == 0:
        return b
    else:
        g = egcd(b % a, a)
        return g


def factorization(n):
    if n == 1:
        return {1}
    ans = set()
    ans.add(D[n])
    factorization(n//D[n])
    return ans


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

s = set()
for i in range(N):
    tmp = factorization(A[i])-{1}
    if tmp & s != set():
        break
    s.add(tmp)
else:
    print('pairwise coprime')
    exit()

L1 = A
while len(L1) > 1:
    l = len(L1)//2
    tmp = [0]*l
    for i in range(l):
        tmp[i] = egcd(L1[2*i], L1[2*i+1])
    if len(L1) % 2 == 1:
        tmp.append(L1[-1])
    L1 = tmp

if L1[0] == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
n = int(input())
*a,=map(int, input().split())
mapa=[0]*(10**6+1)

n0 = 10**6
primes = [0]*(n0+1)
for i in range(2, int(n0**0.5+1)):
    if primes[i]==0:
        x=i
        multi=1
        while x<=n0:
            if primes[x]==0:
                primes[x]=i
            x//=multi
            multi+=1
            x*=multi

def func(m):
    while m>1:
        mapa[primes[m]]+=1
        pm=primes[m]
        while m>1 and m%pm==0:
            m//=pm

for ai in a:
    func(ai)

tmp=max(mapa)

if tmp==n:
    print('not coprime')
elif tmp>1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict

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


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


# Nの素因数分解を辞書で返す
def prime_fact(n, ela):
    if n == 1:
        return {1: 1}


    prime_dict = {}
    for i in ela:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela2 = [i for i, b in enumerate(ela) if b]

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

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

    SA = set(A)
    SA = SA.discard(1)
    if len(SA) >= 90000:
        print("not coprime")
        exit()

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela2)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

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



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

from math import gcd

def factorN(n):
    n1 = n + 1
    A = [2, 0] * ((n1+1)//2)
    for i in range(3, n1, 2):
        if A[i]: continue
        for j in range(i, n1, 2*i):
            A[j] = i

    def factor(n):
        if n == 1:
            return [(1, 1)]
        ans = []
        a, i = A[n], 1
        while n > 1:
            n //= a
            b = A[n]
            if a == b:
                i += 1
            else:
                ans.append((a, i))
                a = b
                i = 1

        return ans

    return factor

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = list(it)
    M = A[-1]
    M1 = M + 1

    dp = [0] * M1

    g1 = A[0]
    f1 = factorN(max(A))
    for i, a in enumerate(A):
        g1 = gcd(g1, a)

        for x, _ in f1(a):
            if x == 1: continue
            if dp[x]:
                for i in range(i+1, N):
                    a = A[i]
                    g1 = gcd(g1, a)
                    if g1 == 1:
                        print("setwise coprime")
                        return
                print("not coprime")
                return
            dp[x] = 1

    print("pairwise coprime")

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

from math import gcd

def factorN(n):
    n1 = n + 1
    A = [2, 0] * ((n1+1)//2)
    for i in range(3, n1, 2):
        if A[i]: continue
        for j in range(i, n1, 2*i):
            A[j] = i

    def factor(n):
        if n == 1:
            return [(1, 1)]
        ans = []
        a, i = A[n], 1
        while n > 1:
            n //= a
            b = A[n]
            if a == b:
                i += 1
            else:
                ans.append((a, i))
                a = b
                i = 1

        return ans

    return factor

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = list(it)
    M = A[-1]
    M1 = M + 1

    dp = [0] * M1

    g1 = A[0]
    f1 = factorN(max(A))
    for i, a in enumerate(A):
        g1 = gcd(g1, a)

        for x, _ in f1(a):
            if dp[x]:
                for i in range(i+1, N):
                    a = A[i]
                    g1 = gcd(g1, a)
                    if g1 == 1:
                        print("setwise coprime")
                        return
                print("not coprime")
                return
            dp[x] = 1

    print("pairwise coprime")

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

from math import gcd

def factorN(n):
    n1 = n + 1
    A = [2, 0] * ((n1+1)//2)
    for i in range(3, n1, 2):
        if A[i]: continue
        for j in range(i, n1, 2*i):
            A[j] = i

    def factor(n):
        ans = []
        a, i = A[n], 1
        while n > 1:
            n //= a
            b = A[n]
            if a == b:
                i += 1
            else:
                ans.append((a, i))
                a = b
                i = 1

        return ans

    return factor

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = list(it)
    M = A[-1]
    M1 = M + 1

    dp = [0] * M1

    g1 = A[0]
    f1 = factorN(max(A))
    for i, a in enumerate(A):
        g1 = gcd(g1, a)

        for x, _ in f1(a):
            if dp[x]:
                for i in range(i+1, N):
                    a = A[i]
                    g1 = gcd(g1, a)
                    if g1 == 1:
                        print("setwise coprime")
                        return
                print("not coprime")
                return
            dp[x] = 1

    print("pairwise coprime")

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
insu_list=[0]*(10**6)

iti=True

for i in a:
    if i!=1:
        iti=False

if iti:
    print("pairwise coprime")
    exit()
# n以下の素数リスト
def prime_list(n):
    a=[2]
    k=3
    while k<=n:
        for i in a:
            if k%i==0:
                break
        if k<i**2:
            a.append(k)
        k+=2
    return a

sosuu=prime_list(10**3+5)

for i in a:
    for j in sosuu:
        if i%j==0:
            insu_list[j]+=1
        if i<j:
            break
    if 10**3+5<i:
        insu_list[i]+=1

if max(insu_list)<=1:print("pairwise coprime")
elif max(insu_list)<n:print("setwise coprime")
else:print("not coprime")

Submission status: Runtime Error

Solution code:
def resolve():
    import math
    n = int(input())
    a = list(map(int, input().split()))
    a = list(set(a))
    a = sorted(a)
    for i in range(1, len(a)):
        ggcd = math.gcd(ggcd, a[i])
        if ggcd == 1:
            break
    if ggcd != 1:
        print("not coprime")
    else:
      print("test")
resolve()

Submission status: Runtime Error

Solution code:
n = int(input())
*a,=map(int, input().split())
mapa=[0]*(10**6+1)

n0 = 10**6
primes = [0]*(n0+1)
for i in range(2, int(n0**0.5+1)):
    if primes[i]==0:
        x=i
        multi=1
        while x<=n0:
            if primes[x]==0:
                primes[x]=i
            x//=multi
            multi+=1
            x*=multi

def func(m):
    while m>1:
        mapa[primes[m]]+=1
        while m>1 and m%primes[m]==0:
            m//=primes[m]

for ai in a:
    func(ai)

tmp=max(mapa)
# print(mapa[:20])
if tmp==n:
    print('not coprime')
elif tmp>1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
from math import sqrt
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
M = 10 ** 6
num = [i+1 for i in range(M)]
num[0] = 0
for i in range(1, M):
  if num[i] == i + 1:
    if i + 1 > sqrt(M):
      break
    n = 2 * (i + 1)
    while n <= M:
      num[n-1] = min(num[n-1], i + 1)
      n += (i + 1)
primes = [p+1 for p in range(M) if num[p] == p+1]
l = len(primes)
B = [0 for i in range(l)]
t = 0
for i in range(N):
  j = num[A[i]-1]
  a = A[i]
  while a > 1:
    if a % j == 0:
      B[j] += 1
      if B[j] >= 2:
        t = 1
    while a % j == 0:
      a //= j
    j += 1
if t == 0:
  print("pairwise coprime")
else:
  p = A[0]
  for i in range(1, N):
    p = gcd(p, A[i])
  if p == 1:
    print("setwise coprime")
  else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
N = int(input())
A = tuple(map(int, input().split()))
def p(n):
    is_prime = [True if i%2 == 1 else False for i in range(0, n+1) ]
    is_prime[0] = False
    is_prime[1] = False
    is_prime[2] = True # 2は素数
    for i in range(3, int(n**0.5) + 1, 2):
        if not is_prime[i]:
            continue
        # iの倍数は素数ではないとする
        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]]

primes = p(max(A))
fact_counts = dict()
for a in A:
    aa = a*a
    for p in primes:
        if p > aa:
            continue
        if a%p == 0:
            fact_counts.setdefault(p, 0)
            fact_counts[p] += 1
pairwise = True
for c in fact_counts.values():
    if c > 1:
        pairwise = False
        break

if pairwise:
    print('pairwise coprime')
else:
    if max(fact_counts.values()) == N:
        print('not coprime')
    else:
        print('setwise coprime')

Submission status: Runtime Error

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

MAXN = 100#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
import math
import fractions
from collections import deque
from collections import defaultdict

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


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


# Nの素因数分解を辞書で返す
def prime_fact(n, ela):
    if n == 1:
        return {1: 1}


    prime_dict = {}
    for i in ela:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela2 = [i for i, b in enumerate(ela) if b]

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

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

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue

        cnt += 1
        if cnt >= 90000:
            print("not coprime")
            exit()

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela, ela2)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

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



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

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


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


# Nの素因数分解を辞書で返す
def prime_fact(n, ela):
    if n == 1:
        return {1: 1}


    prime_dict = {}
    for i in ela:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela2 = [i for i, b in enumerate(ela) if b]

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

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

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue

        cnt += 1
        if cnt >= 90000:
            print("not coprime")
            exit()

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela, ela2)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

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



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from math import sqrt
N = int(input())
A = list(map(int, input().split()))
M = 10 ** 6
num = [i+1 for i in range(M)]
num[0] = 0
for i in range(1, M):
  if num[i] == i + 1:
    if i + 1 > sqrt(M):
      break
    n = 2 * (i + 1)
    while n <= M:
      num[n-1] = min(num[n-1], i + 1)
      n += (i + 1)
primes = [p+1 for p in range(M) if num[p] == p+1]
l = len(primes)
B = [0 for i in range(l)]
for i in range(N):
  j = num[A[i]-1]
  while A[i] > 1:
    if A[i] % j == 0:
      B[j] += 1
    while A[i] % j == 0:
      A[i] //= j
    j += 1
x = 1
y = 1
for i in range(l):
  if B[i] >= 2:
    x = 0
  if B[i] == N:
    y = 0
if x == 1:
  print("pairwise coprime")
elif y == 1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Runtime Error

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

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)

def erat():
    end = 10 ** 6
    t = [False if i == 0 or i == 1 else True for i in range(end)]
    ret = [0 for i in range(end)]

    for i in range(2, end):
        if t[i]:
            for j in range(i * 2, end, i):
                t[j] = False
                if not ret[j]:
                    ret[j] = i
            ret[i] = i
    return ret

tmp = A[0]
for i in A[1:]:
    tmp = gcd(tmp, i)
isS = True if tmp == 1 else False
isP = True

e = erat()

D = dict(iter([(i, False) for i in range(10 ** 6)]))
for i in A:
    tmp = set()
    while i != 1:
        tmp.add(e[i])
        i //= e[i]
    for i in tmp:
        if D[i]:
            isP = False
            break
        else:
            D[i] = True
    if not isP:
        break

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

Submission status: Runtime Error

Solution code:
from math import gcd


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

# setwise validation
tmp = 0
for a in A:
    tmp = gcd(tmp, a)
isSetwise = (tmp == 1)


# pairwise validation
M = 10 ** 6
A = set(A)
isPairwise = True
for i in range(2, M):
    cnt = 0
    ni = 0
    while (ni := ni + i) <= M:
        cnt += (ni in A)
    isPairwise &= (cnt <= 1)

# check
if isPairwise:
    ans = 'pairwise coprime'
elif isSetwise:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

Submission status: Runtime Error

Solution code:
#ceilevenoddformula
import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations
#map(int,input().split())
#int(x) for x in input().split()
def gcd(a, b) : 
    if (a == 0) : 
        return b 
      
    if (b == 0) : 
        return a   
    k = 0
      
    while(((a | b) & 1) == 0) : 
        a = a >> 1
        b = b >> 1
        k = k + 1
          
 
    while ((a & 1) == 0) : 
        a = a >> 1
  
    # From here on, 'a' is always odd.  
    while(b != 0) : 
          
        # If b is even, remove all  
        # factor of 2 in b  
        while ((b & 1) == 0) : 
            b = b >> 1
  
        # Now a and b are both odd. Swap if 
        # necessary so a <= b, then set  
        # b = b - a (which is even). 
        if (a > b) : 
          
            # Swap u and v. 
            temp = a 
            a = b 
            b = temp 
  
        b = (b - a) 
      
    # restore common factors of 2  
    return (a << k) 


def primeFactors(n,l): 
    q=set()    
    f=0
    while n % 2 == 0: 
    	if l[2] and f==0:
    		return False
    	l[2]=True
    	n = n / 2     
    	f=1 

    for i in range(3,int(math.sqrt(n))+1,2): 
    	f=0
        while n % i== 0:
        	if l[i] and f==0:
        		return False
        	l[i]=True
        	n = n / i 
        	f=1
              
    if n > 2: 
    	if l[n]:
    		return False
    	l[n]=True

    #l=l.union(q)
    return True

n=int(input())
l=[int(x) for x in input().split()]
#l.sort()
d={i:False for i in range(1,max(l)+1)}
ans=1
for i in range(n):
	f=primeFactors(l[i],d)
	if not f:
		ans=0
		break



if ans:
	print('pairwise coprime')
else:
	a=l[0]
	b=l[1]
	gc=gcd(a,b)
	for i in range(2,n):
		gc=gcd(gc,l[i])
		if gc==1:
			break
	if gc==1:
		print('setwise coprime')
	else:
		print('not coprime')

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

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


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


# Nの素因数分解を辞書で返す
def prime_fact(n, ela, ela2):
    if n == 1:
        return {1: 1}
    if ela[n]:
        return {n: 1}

    prime_dict = {}
    for i in ela2:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela2 = [i for i, b in enumerate(ela) if b]

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


    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue

        cnt += 1
        if cnt >= 90000:
            print("not coprime")
            exit()

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela, ela2)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

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



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

n = int(input())
a_list = list(map(int, input().split()))
prime_list = [0] * math.floor(a_list[n - 1] ** 0.5)

def is_coprime(num):
    for i in range(2, math.ceil(num ** 0.5)):
        if num % i == 0:
            if prime_list[i] == 1:
                return True
            else:
                prime_list[i] += 1
    return False

for i in range(n):
    if is_coprime(a_list[i]):
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()
print("pairwise coprime")