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 math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = LIST()
m = max(a)

c = [0]*(m+1)
for x in a:
    c[x] += 1

k = max(sum(c[i::i]) for i in range(2, m+1))

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

Submission status: Runtime Error

Solution code:
def eratosthenes2(n):
    lim=int(n**0.5)
    d=[i+1 for i in range(2,n,2)]
    D=[2]*(n+1)
    D[0]=D[1]=-1
    while True:
        p=d[0]
        if lim<p:
            for x in d:
                D[x]=x
            break
        D[p]=p
        d2=[]
        for x in d:
            if x%p!=0:
                d2.append(x)
            else:
                D[x]=p
        d=d2
    return D
    
N=int(input())
A=list(map(int,input().split()))
maxA=max(A)
D=eratosthenes2(maxA)
print(D)

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
A=list(map(int,input().split()))
maxA=max(A)
lim=int(np.sqrt(maxA))
d=[i+1 for i in range(2,maxA,2)]
D=[2]*(maxA+1)
D[0]=D[1]=-1
while True:
    p=d[0]
    if lim<p:
        for x in d:
            D[x]=x
        break
    D[p]=p
    d2=[]
    for x in d:
        if x%p!=0:
            d2.append(x)
        else:
            D[x]=p
    d=d2

count=[0]*(maxA+1)
for x in A:
    pre=x+1
    while x>1:
        if pre!=D[x]:
            count[D[x]]+=1
            pre=D[x]
        x//=D[x]
maxc=max(count)
if maxc==N:
    print('not coprime')
elif maxc==1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [0] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i] == 0:
            p.append(i)
            for j in range(i, n, i):
                if t[j] == 0:
                    t[j] = i

    for j in range(i+1, n):
        if t[j] == j:
            p.append(j)

    return p, t


# error_print(len(P))

@mt
def slv(N, A):
    P, T = eratosthenes(10**6+1)
    P = set(P)
    # random.shuffle(A)

    used = set()
    for a in A:
        while a != 1:
            p = T[a]
            if p in used:
                break
            while a % p == 0:
                a //= p
            used.add(p)
        if a != 1:
            break

    else:
        return 'pairwise coprime'

    g = 0
    for a in A:
        g = math.gcd(a, g)
    return 'setwise coprime' if g == 1 else 'not coprime'


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # P = eratosthenes(10**6+1)
    # N = len(P)
    # A = P[::-1]

    # error_print(N)
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [0] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i] == 0:
            p.append(i)
            for j in range(i, n, i):
                if t[j] == 0:
                    t[j] = i

    for j in range(i+1, n):
        if t[j] == j:
            p.append(j)

    print(t[:10])
    return p, t


# error_print(len(P))

@mt
def slv(N, A):
    P, T = eratosthenes(10**6+1)
    P = set(P)
    # random.shuffle(A)

    used = set()
    for a in A:
        while a != 1:
            p = T[a]
            if p in used:
                break
            while a % p == 0:
                a //= p
            used.add(p)
        if a != 1:
            break

    else:
        return 'pairwise coprime'

    g = 0
    for a in A:
        g = math.gcd(a, g)
    return 'setwise coprime' if g == 1 else 'not coprime'


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # P = eratosthenes(10**6+1)
    # N = len(P)
    # A = P[::-1]

    # error_print(N)
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [0] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(i, n, i):
                if t[j] == 0:
                    t[j] = i

    for j in range(i+1, n):
        if t[j] == j:
            p.append(j)

    return p, t


# error_print(len(P))

@mt
def slv(N, A):
    P, T = eratosthenes(10**6+1)
    P = set(P)
    # random.shuffle(A)

    used = set()
    for a in A:
        while T[a] != a:
            p = T[a]
            if p in used:
                break
            while a % p == 0:
                a //= p
            used.add(p)

        if a != 1:
            break

    else:
        return 'pairwise coprime'

    g = 0
    for a in A:
        g = math.gcd(a, g)
    return 'setwise coprime' if g == 1 else 'not coprime'


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # P = eratosthenes(10**6+1)
    # N = len(P)
    # A = P[::-1]

    # error_print(N)
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def eratosthenes2(n):
    lim=int(n**0.5)
    d=[i+1 for i in range(2,n,2)]
    D=[2]*(n+1)
    D[0]=0
    D[1]=1
    while True:
        p=d[0]
        if lim<p:
            for x in d:
                D[x]=x
            break
        D[p]=p
        for x in d:
            if x%p==0:
                D[x]=p
        d=[x for x in d if x%p!=0]
    return D
    
N=int(input())
A=list(map(int,input().split()))
maxA=max(A)
D=eratosthenes2(maxA)
count=[0]*(maxA+1)
for x in A:
    pre=x+1
    while x>1:
        if pre!=D[x]:
            count[D[x]]+=1
            pre=D[x]
        x=int(x/D[x])
maxc=max(count)
if maxc==N:
    print('not coprime')
elif maxc==1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Runtime Error

Solution code:
def eratosthenes2(n):
    lim=int(n**0.5)
    d=[i+1 for i in range(2,n,2)]
    D=[2]*(n+1)
    D[0]=0
    D[1]=1
    while True:
        p=d[0]
        if lim<p:
            for x in d:
                D[x]=x
            break
        D[p]=p
        d2=[]
        for x in d:
            if x%p!=0:
                d2.append(x)
            else:
                D[x]=p
        d=d2
    return D
    
N=int(input())
A=list(map(int,input().split()))
maxA=max(A)
D=eratosthenes2(maxA)
count=[0]*(maxA+1)
for x in A:
    pre=x+1
    while x>1:
        if pre!=D[x]:
            count[D[x]]+=1
            pre=D[x]
        x=int(x/D[x])
maxc=max(count)
if maxc==N:
    print('not coprime')
elif maxc==1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Runtime Error

Solution code:
def eratosthenes2(n):
    prime=[2]
    lim=int(n**0.5)
    d=[i+1 for i in range(2,n,2)]
    D=[2]*(n+1)
    D[0]=0
    D[1]=1
    while True:
        p=d[0]
        if lim<p:
            for x in d:
                D[x]=x
            prime=prime+d
            break
        prime.append(p)
        D[p]=p
        d2=[]
        for x in d:
            if x%p!=0:
                d2.append(x)
            else:
                D[x]=p
        d=d2
    return D
    
N=int(input())
A=list(map(int,input().split()))
maxA=max(A)
D=eratosthenes2(maxA)
count=[0]*(maxA+1)
for i in range(N):
    x=A[i]
    pre=x+1
    while x>1:
        if pre!=D[x]:
            count[D[x]]+=1
            pre=D[x]
        x//=D[x]
if max(count)==N:
    print('not coprime')
elif max(count)==1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Runtime Error

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

B = [0 for i in range(max(A)+1)]

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

def func(X):
  buf = set()
  while X>1:
    x = B[X]
    buf.add(x)
    while X%x==0:
      X = X//x
  return buf

set1 = func(A[0])
set2 = set(set1)
totallen = len(set1)
for a in A[1:]:
  set3 = func(a)
  totallen += len(set3)
  set1.union(set3)
  set2.intersection(set3)
if len(set2)==0:
  print("not coprime")
elif len(set1)==totallen:
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Runtime Error

Solution code:
import math,sys

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

ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n= 10**6+100
count=[0 for _ in range(max_n)]

def Era(nn):
    prime = []
    limit = math.sqrt(nn)
    data = [i + 1 for i in range(1, nn)]
    while True:
        p = data.pop(0)
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def fac(x,T):
    P_list=Era(x)
    F=True
    ii=0
    pp=P_list[ii]
    while  pp < math.sqrt(x)+1:
        if x%pp==0:
            if T[pp]>0:
                F=False
            T[pp]+=1
        ii+=1
        pp=P_list[ii]
    return F

flag=True
for each in Ns:
    flag_2=fac(each,count)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
else:       
    gcd_ans=Ns[0]
    for i in range(1,n):
        gcd_ans= math.gcd( gcd_ans , Ns[i])
    if gcd_ans==1:
        print(ans_s)
    else:
        print(ans_n)

Submission status: Runtime Error

Solution code:
import math,sys

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

ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n= 10**7+100
count=[0 for _ in range(max_n)]

def Era(nn):
    prime = []
    limit = math.sqrt(nn)
    data = [i + 1 for i in range(1, nn)]
    while True:
        p = data.pop(0)
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def fac(x,T):
    P_list=Era(x)
    F=True
    for p in P_list:
        if x%p==0:
            T[p]+=1
            if T[p]>0:
                F=False
    return F

flag=True
for each in Ns:
    flag_2=fac(each,count)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
else:       
    gcd_ans=Ns[0]
    for i in range(1,n):
        gcd_ans= math.gcd( gcd_ans , Ns[i])
    if gcd_ans==1:
        print(ans_s)
    else:
        print(ans_n)

Submission status: Runtime Error

Solution code:
import math,sys

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

ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n= 10**6+100
count=[0 for _ in range(max_n)]

def Era(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data.pop(0)
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def fac(x,T):
    P_list=Era(x)
    F=True
    for p in P_list:
        if x%p==0:
            T[p]+=1
            if T[p]>0:
                F=False
    return F

flag=True
for each in Ns:
    flag_2=fac(each,count)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
    sys.exit()

gcd_ans=Ns[0]
for i in range(1,n):
    gcd_ans= math.gcd( gcd_ans , Ns[i])

if gcd_ans==1:
    print(ans_s)
else:
    print(ans_n)

Submission status: Runtime Error

Solution code:
import math,sys

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


ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n=int(math.sqrt(10**6))+20
count=[0 for _ in range(max_n)]

def Era(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data.pop(0)
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def fac(x,T):
    P_list=Era(x)
    F=True
    for p in P_list:
        if x%p==0:
            T[p]+=1
            if T[p]>0:
                F=False
    return F
flag=True
for each in Ns:
    flag_2=fac(each,count)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
    sys.exit()

gcd_ans=Ns[0]
for i in range(1,n):
    gcd_ans= math.gcd( gcd_ans , Ns[i])

if gcd_ans==1:
    print(ans_s)
else:
    print(ans_n)

Submission status: Runtime Error

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

pairwise_flg = true
setwis_flg = true

for i in range(N-1):
  if gcd(A[i], A[i+1]) != 1:
    pairwise_flg = false
    break

if pairwise_flg == false:
  for i in range(N):
    for j in range(N):
      if i != j:
        if gcd(A[i],A[j]) !=1:
          setwis_flg = false
          break

if pairwise_flg == true:
  print('pairwise coprime')
elif setwis_flg == true:
  print('setwise coprime')
else:
  print('not coprime')


def gcd(a,b):
  if a == b:
    return a
  elif a > b :
    a,b = b, a
  for i range(a,1,-1):
    if a % i ==0 and b % i ==0:
      return i
    else
      return 1

Submission status: Runtime Error

Solution code:
from math import gcd
n=int(input())
l=list(map(int,input().split()))
mal=max(l)
e=[0 for i in range(mal+1)]

import numpy as np
def searchPrimeNum(N):
    ma = int(np.sqrt(N))
    searchList = [i for i in range(2,N+1)]
    primeNum = []
    while searchList[0] <= ma:
        primeNum.append(searchList[0])
        tmp = searchList[0]
        for i in searchList:
            if i%tmp==0:
                e[i]=tmp
        searchList = [i for i in searchList if i % tmp != 0]
        primeNum.extend(searchList)
    return primeNum
searchPrimeNum(mal)
#print(e)    
s=set()
f=1
for i in l:
  st = set()
  while i > 1:
    st.add(e[i])
    i//=e[i]
  if not s.isdisjoint(st):
    f=1
    break
  s |= st

if f==0:
    print('pairwise coprime')
    exit()
p=l[0]
for i in range(1,n):
    p=gcd(p,l[i])
if p==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
from math import gcd
n=int(input())
l=list(map(int,input().split()))
mal=max(l)
e=[0 for i in range(mal+1)]

import numpy as np
def searchPrimeNum(N):
    ma = int(np.sqrt(N))
    searchList = [i for i in range(2,N+1)]
    primeNum = []
    while searchList[0] <= ma:
        primeNum.append(searchList[0])
        tmp = searchList[0]
        for i in searchList:
            if i%tmp==0:
                e[i]=tmp
        searchList = [i for i in searchList if i % tmp != 0]
        primeNum.extend(searchList)
    return primeNum
searchPrimeNum(mal)
#print(e)
s=set([])
f=0
for i in range(n):
    p=l[i]
    t=set([])
    while e[p]!=0:
        t.add(e[p])
        p//=e[p]
    if p>=2:
        t.add(p)
    if len(s&t)>0:
        f=1
        break
    s=s|t

if f==0:
    print('pairwise coprime')
    exit()
p=l[0]
for i in range(1,n):
    p=gcd(p,l[i])
if p==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
import math

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

MAX = 1000005

is_prime = [1]*MAX
D = [None]*MAX
is_prime[0],is_prime[1] = 0,0

for i in range(2,MAX):
  if is_prime[i]:
    D[i] = i
    for j in range(i*2,MAX,i):
      is_prime[j] = 0
      D[j] = i
      
counts = [0]*MAX
pair = True

for a_i in a:
  while True:
    p = D[a_i]
    if counts[p]>0:
      pair = False
    counts[p] += 1
    if p == a_i:
      break
    else:
      a_i //= p

if pair:
  print('pairwise coprime')
else:
  g = a_i
  for a_i in a:
    g = math.gcd(a_i,g)
  if g == 1:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
import math

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

MAX = 1000005

is_prime = [1]*MAX
D = [None]*MAX
is_prime[0],is_prime[1] = 0,0

for i in range(2,MAX):
  if is_prime[i]:
    D[i] = i
    for j in range(i,MAX,i):
      is_prime[j] = 0
      D[j] = i
      
counts = [0]*MAX
pair = True

for a_i in a:
  while True:
    p = D[a_i]
    if counts[p]>0:
      pair = False
    counts[p] += 1
    if p == a_i:
      break
    else:
      a_i //= p

if pair:
  print('pairwise coprime')
else:
  g = 0
  for a_i in a:
    g = math.gcd(a_i,g)
  if g == 1:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
H, W, M = map(int,input().split())
P = [list(map(int, input().split())) for i in range(M)]
for p in P:
    p[0] -= 1
    p[1] -= 1
cnth = [0]*H
cntw = [0]*W
ans = 0
for p in P:
    cnth[p[0]] += 1
for p in P:
    cntw[p[1]] += 1
mxh = max(cnth)
mxw = max(cntw)
cntx = 0
for p in P:
    if cnth[p[0]] == mxh and cntw[p[1]] == mxw:
        cntx += 1
if cntx == cnth.count(mxh) * cntw.count(mxw):
    ans = mxh + mxw -1
else:
    ans = mxh + mxw
print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd

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

A=sorted(A)
ans=[0]*(A[-1]+1)
c=A[-1]
for i in A:
    c=gcd(c,i)
    for j in range(2, int(-(-i**0.5//1))+1):
        if i%j==0:
            ans[j]+=1
    ans[i]+=1   

ans.pop(0)
ans.pop(0)

if max(ans)==1:
    print('pairwise coprime')

elif c==1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
N = int(input())
A = [0]*(100001)
IIL = list(map(int, input().split()))
for a in IIL:
    A[a] += 1

# MFPF = Most Frequent Prime Factor
MFPF_n = 0
for i in range(2, 100001):
    n = i
    tmp = 0
    while n < 100001:
        tmp += A[n]
        n += i
    MFPF_n = max(MFPF_n, tmp)

if MFPF_n < 2:
    print('pairwise coprime')
elif MFPF_n - A[1] < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
N = int(input())
A = [0]*(100001)
for a in list(map(int, input().split())):
    A[a] += 1

# MFPF = Most Frequent Prime Factor
MFPF_n = 0
for i in range(2, 100001):
    n = i
    tmp = 0
    while n < 100001:
        tmp += A[n]
        n += i
    MFPF_n = max(MFPF_n, tmp)

if MFPF_n < 2:
    print('pairwise coprime')
elif MFPF_n - A[1] < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
MAX = 10**6+1

divs = [[] for _ in range(MAX)]
cnt = [0]*MAX

for i in range(2,n):
  m = i
  while m <= MAX:
    divs[m].append(i)
    m += i
    
pair = True
setwise = True

for i in range(n):
  for d in divs[a[i]]:
    if cnt[d] > 0:
      pair = False
    cnt[d] += 1
    
if pair:
  print('pairwise coprime')
else:
  for i in range(MAX):
    if cnt[i] == n:
      setwise = False
      break
  if setwise:
    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()))

h = True
checker = [0 for _i in range(10**6+1)]
for i in a:
    checker[i] += 1
    if sum(checker[i::i]) > 1:
        h = False
        break
    for j in range(i, 10**6+2, i):
        checker[j] += 1

if h == True:
    print('pairwise coprime')
else:
    r = a[0]
    for i in a:
        r = gcd(r, i)
    if r == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Runtime Error

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

checker = [0 for _i in range(10**6+1)]
h = True
for i in a:
    if i == 1:
        continue
    num = i
    if num%2==0:
        checker[2] += 1
        if checker[2] >= 2:
            h = False
            break
    
    for j in range(3, int(i**0.5)+1):
        if num%j == 0:
            checker[j] += 1
            if checker[j] >= 2:
                h = False
                break
            num //= j
    if num == i:
        checker[num] += 1:
        if checker[num] >= 2:
            h = False
            break
if h == True:
    print('pairwise coprime')
else:
    r = a[0]
    for i in a:
        r = gcd(r, i)
    if r == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Runtime Error

Solution code:
import math
import fractions


def make_prime_and_deleted_by_list(n):
    prime_list = [i for i in range(2, n+1)]
    deleted_by_list = [i for i in range(n+1)]
    pi = 0
    target_prime = prime_list[pi]
    while(target_prime < math.sqrt(n)):
        old_prime_list = prime_list.copy()
        prime_list = prime_list[:pi+1]
        for i in old_prime_list:
            if i % target_prime == 0:
                deleted_by_list[i] = target_prime
            else:
                if i > prime_list[pi]:
                    prime_list.append(i)
        pi += 1
        target_prime = prime_list[pi]
    return prime_list, deleted_by_list

def make_factor_list(n, deleted_by_list, factor_list):
    if n == 1:
        return factor_list
    else:
        factor = deleted_by_list[n]
        factor_list.append(factor)
        return make_factor_list(int(n/factor), deleted_by_list, factor_list)

def calc_gcd(As):
    ans = As[0]
    for i in range(1, len(As)):
        ans = fractions.gcd(ans, As[i])
    return ans
        
N = int(input())
As = list(map(int, input().split()))
_, d = make_prime_and_deleted_by_list(max(As))

As_factor_list = []
for A in As:
    As_factor_list.extend(set(make_factor_list(A, d, [])))

if len(set(As_factor_list)) == len(As_factor_list):
    print("pairwise coprime")

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

Submission status: Runtime Error

Solution code:
n=int(input())
1/(n>3)

Submission status: Runtime Error

Solution code:
c=[m:=0]*6**8
n,a=open(0)
for a in a.split():c[int(a)]+=1
print(('not','psaeitr'[any((m:=max(m,sum(c[i::i])))>1for i in range(2,6**8))::2]+'wise')[m<int(n)],'coprime')

print(('not','psaeitr'[any(c:=[max(0,sum(c[i::i])-1)for i in range(2,6**8)])::2]+'wise')[max(c)+1<int(n)],'coprime')

1/(max(c)+1==m)

Submission status: Runtime Error

Solution code:
n,*a=map(int,open(0).read().split())
m=6**8
c=[0]*m
p=[1,1]+c[:]
for i in range(m):
  if p[i]<1:
    for j in range(i,m,i):p[j]=i
for a in a:
  c[a]+=1
  while p[a]!=a:
    a//=p[a]
    c[a]+=1
1/(max(c[2:])<n)
print(('not','psaeitr'[max(c[2:])>1::2]+'wise')[max(c[2:])<n],'coprime')

Submission status: Runtime Error

Solution code:
n,*a=map(int,open(0).read().split())
m=6**8
c=[0]*m
p=[1,1]+c[:]
for i in range(m):
  if p[i]<1:
    for j in range(i,m,i):p[j]=i
for a in a:
  c[a]+=1
  while p[a]!=a:
    a//=p[a]
    c[a]+=1
1/(max(c[2:])==n)
print(('not','psaeitr'[max(c[2:])>1::2]+'wise')[max(c[2:])<n],'coprime')

Submission status: Runtime Error

Solution code:
n,*a=map(int,open(0).read().split())
m=max(a)+1
c=[0]*m
p=[1,1]+c[:]
for i in range(m):
  if p[i]<1:
    for j in range(i,m,i):p[j]=i
for a in a:
  c[a]+=1
  while p[a]!=a:
    a//=p[a]
    c[a]+=1
print(('not','psaeitr'[max(c[2:])>1::2]+'wise')[max(c)<n],'coprime')

Submission status: Runtime Error

Solution code:
import math

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

D = [i for i in range(1000001)]

for i in range(2,1001):
    if D[i] == i:
        for j in range(2,1+100000//i):
            D[i*j] = i

###
#print(D[:10])
###

det = True
P = []

for a in A:
    Q = []
    aa = a
    while aa > 1:
        Q.append(D[aa])
        aa //= D[aa]
    P = P + list(set(Q))
    ###
    #print(P)
    #print(Q)
    ###
    if len(P) != len(set(P)):
        det = False
        break
    P = set(P)

if det:
    print('pairwise coprime')

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

Submission status: Runtime Error

Solution code:
# coding: utf-8
from math import gcd

def getPrime(x):
    num_list=[i for i in range(2,x+1)]
    prime_list=[]
    D=[x+1 for i in range(x+1)]
    
    while num_list[0]<x**(1/2):
        p=num_list.pop(0)
        prime_list.append(p)
        for i in range(len(num_list)):
            if num_list[i]%p==0:
                if D[num_list[i]]>p:
                    D[num_list[i]]=p
        num_list = [e for e in num_list if e % p != 0]
    
    prime_list = prime_list + num_list
    for i in range(len(prime_list)):
        D[prime_list[i]] = prime_list[i]
    D[0]=1
    D[1]=1
    return D

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

pc_flg = True

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

prime_flg=[False for i in range(10**6+1)]

for i in range(N):
    num = A[i]
    primes = []
    while True:
        p = D[num]
        num = num//p
        primes.append(p)
        if num == 1:
            break
    for j in set(primes):
        if not(prime_flg[j]):
            prime_flg[j] = True
        else:
            if j != 1:
                pc_flg = False

if pc_flg:
    print("pairwise coprime")
elif x==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
# coding: utf-8
from math import gcd

def getPrime(x):
    num_list=[i for i in range(2,x+1)]
    prime_list=[]
    D=[x+1 for i in range(x+1)]
    
    while num_list[0]<x**(1/2):
        p=num_list.pop(0)
        prime_list.append(p)
        for i in range(len(num_list)):
            if num_list[i]%p==0:
                if D[num_list[i]]>p:
                    D[num_list[i]]=p
        num_list = [e for e in num_list if e % p != 0]
    
    prime_list = prime_list + num_list
    for i in range(len(prime_list)):
        D[prime_list[i]] = prime_list[i]
    D[0]=1
    D[1]=1
    return D

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

pc_flg = True

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

prime_flg=[False for i in range(10**6+1)]

for i in range(N):
    num = A[i]
    primes = []
    while True:
        p = D[num]
        num = num//p
        primes.append(p)
        if num == 1:
            break
    for j in set(primes):
        if not(prime_flg[j]):
            prime_flg[j] = True
        else:
            pc_flg = False

if pc_flg:
    print("pairwise coprime")
elif x==1:
    print("setwise coprime")
else:
    print("not coprime")