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:
import math
(_,), a  = [list(map(int, s.split())) for s in open(0)]

def fast_prime_factorize(num):
    prime_factor_sets = [set() for _ in range(num+1)]
    for i in range(2, int(math.sqrt(num)) + 2):
        if len(prime_factor_sets[i]) == 0:
            for j in range(i, num+1, i):
                prime_factor_sets[j].add(i)
    return prime_factor_sets

def get_prime_factor_set(prime_factor_sets, x):
    y = prime_factor_sets[x]
    if len(y) == 0 and x != 1:
        y = {x}
    return y


prime_factor_sets = fast_prime_factorize(max(a))

g = get_prime_factor_set(prime_factor_sets, a[0]).copy()
l = set()
s = 0
for x in a:
    y = get_prime_factor_set(prime_factor_sets, x)
    g &= y
    l |= y
    s += len(y)

if len(g) != 0:
    ans = 'not coprime'
elif len(l) != s:
    ans = 'setwise coprime'
else:
    ans = 'pairwise coprime'
print(ans)

Submission status: Runtime Error

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=prime_set
  return s

check=set()

if setwise_coprime(a)==1:
  s=erast(1000000)
  s.sort()
  for i in range(n):
    if a[i]!=1:
      for j in range(len(s)):
        if s[j]>a[i]:
          break
        if a[i]%s[j]==0:
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
            
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Runtime Error

Solution code:
# E

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

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

def fast_factorization_init(N):
    res=list(range(N))
    for i in range(2,N):
        if i*i>N:
            break
        for j in range(i*i,N,i):
            if res[j]==j:
                res[j]=i
        if res[i]<i:
            continue
    return res            
    
min_factors=fast_factorization_init(N)
def fast_factorization(n):
    res=[]
    while n>1:
        res.append(min_factors[n])
        n//=min_factors[n]
    return res

res2=1
P=[]
for i in range(N):
    if i!=0:
        res1=gcd(A[i],res1)
    else:
        res1=A[0]
    fact=fast_factorization(A[i])
    if res2!=0:
        for p in P:
            if A[i]%p==0:
                res2=0
                break
    for p in fact:
        P.append(p)
if res2==1:
    print('pairwise coprime')
elif res1==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
# E

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

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

def fast_factorization_init(N):
    res=list(range(N))
    for i in range(2,N):
        if i*i>N:
            break
        for j in range(i*i,N,i):
            if res[j]==j:
                res[j]=i
        if res[i]<i:
            continue
    return res            
    
min_factors=fast_factorization_init(10**5)
def fast_factorization(n):
    res=[]
    while n>1:
        res.append(min_factors[n])
        n//=min_factors[n]
    return res

res2=1
P=[]
for i in range(N):
    if i!=0:
        res1=gcd(A[i],res1)
    else:
        res1=A[0]
    fact=fast_factorization(A[i])
    if res2!=0:
        for p in P:
            if A[i]%p==0:
                res2=0
                break
    for p in fact:
        P.append(p)
if res2==1:
    print('pairwise coprime')
elif res1==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
def prime_factorize(n):
    global a
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a = set(a)
    a = list(a)

N = input()
t = [int(s) for s in input().split()]
pairwise = int(1)
setwise = int(0)
lent = int(len(t))
p = set(t)
t = list(p)
lenp = int(len(t))
a = []

if lent != lenp:
    pairwise = 0

if 1 in t:
    t.remove(1)
    setwise = 1
    lenp -= 1

for i in range(lenp):
    if i == 0:
        prime_factorize(t[i])
        setlist = a
        pairlist = set(a)
    else:
        prime_factorize(t[i])
        lena = int(len(a))
        if pairwise == 1:
            for j in range(lena):
                if a[j] in pairlist:
                    pairwise = 0
                    break
                else:
                    pairlist.add(a[j])
        if pairwise == 0 and setwise == 0:
            setlen = int(len(setlist))
            aset = set(a)
            for j in range(setlen):
                if setlist[j] in aset:
                    pass
                else:
                    setlist.pop(j)
            if int(len(setlist)) == 0:
                setwise = 1

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

Submission status: Runtime Error

Solution code:
import math
(_,), a  = [list(map(int, s.split())) for s in open(0)]

def fast_prime_factorize(num):
    prime_factor_sets = [set() for _ in range(num+1)]
    for i in range(2, int(math.sqrt(num)) + 2):
        if len(prime_factor_sets[i]) == 0:
            for j in range(i, num+1, i):
                prime_factor_sets[j].add(i)
    return prime_factor_sets

prime_factor_sets = fast_prime_factorize(max(a))

x = a[0]
y = prime_factor_sets[x]
if len(y) == 0 and x != 1:
    y = {x}
g = y.copy()
l = set()
s = 0
for x in a:
    y = prime_factor_sets[x]
    if len(y) == 0 and x != 1:
        y = {x}
    g &= y
    l |= y
    s += len(y)

if len(g) != 0:
    ans = 'not coprime'
elif len(l) != s:
    ans = 'setwise coprime'
else:
    ans = 'pairwise coprime'
print(ans)

Submission status: Runtime Error

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


def prime_factorize(n):
    r = set()
    if n % 2 == 0:
        r.add(2)
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.add(n)
    return collections.Counter(r)


a1 = collections.Counter([])
a2 = prime_factorize(A[0])
for a in A:
    tmp = prime_factorize(a)
    a1 += tmp
    a2 &= tmp
if a2:
    print('not coprime')
elif a1.most_common()[0][1] >= 2:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
from math import gcd

N = int(input())
A = list(map(int, input().split()))
MAX = 10**6


def prime_factor_sieve(n):
    """
    エラトステネスの篩で、
    2 ~ Nの各数に対して、その整数のもつ最小の素因数
    (その整数を篩落とした最小の素因数)を記録して返す
    O(nloglog(n))
    """
    res = [i for i in range(n+1)]
    for i in range(2, int(n**0.5)+1):
        if res[i] < i:
            continue
        for j in range(i*i, n+1, i):
            if res[j] == j:
                res[j] = i
    return res

def factorization(n, min_factor):
    """
    エラトステネスの篩で手に入れた、各整数の最小素因数のリスト
    からO(log(n))で素因数分解する
    """
    res = set()
    while n > 1:
        res.add(min_factor[n])
        n //= min_factor[n]
        # 割った後の素因数についてもO(1)で参照できる
    return res

# 素因数が重複しているかを調べる
min_factor = prime_factor_sieve(MAX)
res = set()
is_ok = 1
A = [a for a in A if a != 1]
for a in A:
    tmp = factorization(a, min_factor)
    if res & tmp:
        is_ok = 0
        break
    res = factorization(a, min_factor)
if is_ok:
    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")

Submission status: Runtime Error

Solution code:
def prime_factorize(n):
    global a
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a = set(a)
    a = list(a)

N = input()
t = [int(s) for s in input().split()]
pairwise = int(1)
setwise = int(0)
lent = int(len(t))
p = set(t)
t = list(p)
lenp = int(len(t))
b = []

if lent != lenp:
    pairwise = 0

for i in range(lenp):
    if t[i] == 1:
        setwise == 1
    elif i == 0:
        prime_factorize(t[i])
        setlist = a
        pairlist = set(a)
    else:
        prime_factorize(t[i])
        lena = int(len(a))
        if pairwise == 1:
            for j in range(lena):
                if a[j] in pairlist:
                    pairwise = 0
                    break
                else:
                    pairlist.add(a[j])
        if pairwise == 0 and setwise == 0:
            setlen = int(len(setlist))
            aset = set(a)
            for j in range(setlen):
                if setlist[j] in aset:
                    pass
                else:
                    setlist.pop(j)
            if int(len(setlist)) == 0:
                setwise = 1

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

Submission status: Runtime Error

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


def prime_factorize(n):
    r = set()
    if n % 2 == 0:
        r.add(2)
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.add(n)
    return collections.Counter(r)


a1 = collections.Counter([])
a2 = prime_factorize(list(A)[0])
for a in A:
    tmp = prime_factorize(a)
    a1 += tmp
    a2 &= tmp
if a2:
    print('not coprime')
elif a1.most_common()[0][1] >= 2:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

def is_prime(n):
  if n==1:
    return False
  if n==2:
    return True
  else:
    for i in range(int(math.sqrt(n))+1):
      if n%i==0:
        return False
    return True
  
check=set()
for i in range(n):
  if is_prime(a[i]):
    check.add(a[i])
  
if setwise_coprime(a)==1:
  s=erast(1000)
  s.sort()
  for i in range(n):
    if a[i]!=1:
      for j in range(len(s)):
        if a[i]%s[j]==0:
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
            
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Runtime Error

Solution code:
import math
(_,), a  = [list(map(int, s.split())) for s in open(0)]

def fast_prime_factorize(num):
    prime_factor_sets = [set() for _ in range(num+1)]
    for i in range(2, int(math.sqrt(num)) + 2):
        if len(prime_factor_sets[i]) == 0:
            for j in range(i, num+1, i):
                prime_factor_sets[j].add(i)
    return prime_factor_sets

prime_factor_sets = fast_prime_factorize(max(a))

y = prime_factor_sets[a[0]]
if len(y) == 0 and a[0] != 1:
    y = {a[0]}
g = y.copy()
l = set()
s = 0
for x in a:
    y = prime_factor_sets[x]
    if len(y) == 0 and x != 1:
        y = {x}
    g &= y
    l |= y
    s += len(y)

if len(g) != 0:
    ans = 'not coprime'
elif len(l) != s:
    ans = 'setwise coprime'
else:
    ans = 'pairwise coprime'
print(ans)

Submission status: Runtime Error

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

def is_prime(n):
  if n==1:
    return False
  if n==2:
    return True
  else:
    for i in range(int(math.sqrt(n))+1):
      if n%i==0:
        return False:
    return True
  
check=set()
if setwise_coprime(a)==1:
  s=erast(1000000)
  s.sort()
  for i in range(n):
    if a[i]!=1:
      for j in range(len(s)):
        if a[i]%s[j]==0:
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
            
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Runtime Error

Solution code:
import math
(_,), a  = [list(map(int, s.split())) for s in open(0)]

def fast_prime_factorize(num):
    prime_factor_sets = [set() for _ in range(num+1)]
    for i in range(2, int(math.sqrt(num)) + 2):
        if len(prime_factor_sets[i]) == 0:
            for j in range(i, num+1, i):
                prime_factor_sets[j].add(i)
    return prime_factor_sets

prime_factor_sets = fast_prime_factorize(max(a))

g = prime_factor_sets[0].copy()
l = set()
s = 0
for x in a:
    y = prime_factor_sets[x]
    if len(y) == 0 and x != 1:
        y = {x}
    g &= y
    l |= y
    s += len(y)

if len(g) != 0:
    ans = 'not coprime'
elif len(l) != s:
    ans = 'setwise coprime'
else:
    ans = 'pairwise coprime'
print(ans)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class Osa_k():
    def __init__(self, n):
        self.sieve = list(range(n + 1))
        self.sieve[0] = 1 #素数でない
        self.sieve[1] = 1 #素数でない
        m = int(math.sqrt(n))
        for i in range(2, m + 1):
            if self.sieve[i] < i:
                continue
            for j in range(i * i, n + 1, i):
                if self.sieve[j] == j:
                    self.sieve[j] = i

    def factorize(self, n):
        prime = defaultdict(int)
        if n == 0 or n == 1:
            return n
        opt = n
        while opt > 1:
            prime[self.sieve[opt]] += 1
            opt //= self.sieve[opt]
        return sorted(prime.items())

N = getN()
A = getList()
O = Osa_k(10 ** 6 + 1)

primes = defaultdict(int)
for i in A:
    for j in O.factorize(i):
        primes[j[0]] += 1

judge = 1
for i in primes.items():
    judge = max(judge, i[1])

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

Submission status: Runtime Error

Solution code:
def prime_factorize(n):
    global a
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a = set(a)
    a = list(a)

N = input()
t = [int(s) for s in input().split()]
pairwise = int(1)
setwise = int(0)
lent = int(len(t))
p = set(t)
t = list(p)
lenp = int(len(t))
b = []

if lent != lenp:
    pairwise = 0

for i in range(lenp):
    if i == 0:
        prime_factorize(t[i])
        setlist = a
        pairlist = set(a)
    else:
        prime_factorize(t[i])
        lena = int(len(a))
        if pairwise == 1:
            for j in range(lena):
                if a[j] in pairlist:
                    pairwise = 0
                    break
                else:
                    pairlist.add(a[j])
        if pairwise == 0 and setwise == 0:
            setlen = int(len(setlist))
            aset = set(a)
            for j in range(setlen):
                if setlist[j] in aset:
                    pass
                else:
                    setlist.pop(j)
            if int(len(setlist)) == 0:
                setwise = 1

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

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class Osa_k():
    def __init__(self, n):
        max = n + 1
        # osa_k法
        prime = [2]
        self.min_factor = list(range(max + 1))
        self.min_factor[0] = -1
        self.min_factor[1] = -1
        limit = int(math.sqrt(max))

        for i in range(2, limit + 1):
            if self.min_factor[i] < i:
                continue
            for j in range(i * i, max + 1, i):
                if self.min_factor[j] == j:
                    self.min_factor[j] = i

    def factorize(self, n):
        prime = defaultdict(int)
        if n == 0 or n == 1:
            return n
        opt = n
        while opt > 1:
            prime[self.min_factor[opt]] += 1
            opt //= self.min_factor[opt]
        return sorted(prime.items())

N = getN()
A = getList()
O = Osa_k(10 ** 6 + 1)

primes = defaultdict(int)
for i in A:
    for j in O.factorize(i):
        primes[j[0]] += 1

judge = 1
for i in primes.items():
    judge = max(judge, i[1])

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

Submission status: Runtime Error

Solution code:
import math as m

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


D=[0]*(10**6+1)
D[1]=1
for i in range(2,int(m.sqrt(10**6))+2):
    if D[i]!=0:
        continue
    j=i
    while j < 10**6+1:
        D[j]=i
        j+=i

P=[0]*10**6
pc=True
g=As[0]
for n in range(N):
    A=As[n]
    ppre=1
    while True:
        p=D[A]
        if ppre != p:
            if P[p] > 0:
                pc=False
            P[p]+=1
            ppre=p
        A=A//p
        if A==1:
            break
    g=m.gcd(g,A)

if pc:
    print('pairwise coprime')
elif g==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
p = [-1] * (max(A)+1)
count = defaultdict(lambda: 0)

p[0] = 0
p[1] = 1
for i in range(2, len(p)):
    if p[i] == -1:
        for j in range(i, len(p), i):
            p[j] = i

for a in A:
    factors = set()
    while a != 1:
        factor = p[a]
        factors.add(factor)
        a //= factor
    for factor in factors:
        count[factor] += 1

max_count = max(count.values())
if max_count == 1:
    print('pairwise coprime')
elif max_count < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class Osa_k():
    def __init__(self, n):
        max = n + 1
        # osa_k法
        prime = [2]
        self.min_factor = [0] * max
        self.min_factor[0] = -1
        self.min_factor[1] = -1
        limit = int(math.sqrt(max)) + 1
        data = [i + 1 for i in range(1, max - 1)]

        while limit > data[0]:
            prime.append(data[0])
            next_data = []
            for i in data:
                if i % data[0] != 0:
                    next_data.append(i)
                else:
                    self.min_factor[i] = data[0]
            data = next_data
        prime = prime + data
        for i in prime:
            self.min_factor[i] = i

    def factorize(self, n):
        prime = defaultdict(int)
        if n == 0 or n == 1:
            return n
        opt = n
        while opt > 1:
            prime[self.min_factor[opt]] += 1
            opt //= self.min_factor[opt]
        return sorted(prime.items())

N = getN()
A = getList()
O = Osa_k(10 ** 6 + 1)

primes = defaultdict(int)
for i in A:
    for j in O.factorize(i):
        primes[j[0]] += 1

judge = 1
for i in primes.items():
    judge = max(judge, i[1])

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, AS):
    num_division = 0
    maxAS = max(AS)
    eratree = [0] * (maxAS + 10)
    for p in range(2, maxAS + 1):
        if eratree[p]:
            continue
        # p is prime
        x = p
        while x <= maxAS:
            if not eratree[x]:
                eratree[x] = p
            x += p

    from collections import defaultdict
    count = defaultdict(int)
    for a in AS:
        factors = []
        while a > 1:
            d = eratree[a]
            factors.append(d)
            a //= d
            num_division += 1
        # debug(": ", factors)
        for f in set(factors):
            count[f] += 1

    # debug(": num_division", num_division)
    if any(x == N for x in count.values()):
        return "not coprime"
    if any(x >= 2 for x in count.values()):
        return "setwise coprime"
    return "pairwise coprime"


def main():
    # parse input
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


# tests
T1 = """
3
3 4 5
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
pairwise coprime
"""

T2 = """
3
6 10 15
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
setwise coprime
"""

T3 = """
3
6 10 16
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
not coprime
"""

T4 = """
3
100000 100001 100003
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
pairwise coprime
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, AS):
    num_division = 0
    maxAS = max(AS)
    eratree = [0] * (maxAS + 10)
    for p in range(2, maxAS + 1):
        if eratree[p]:
            continue
        # p is prime
        x = p
        while x <= maxAS:
            if not eratree[x]:
                eratree[x] = p
            x += p

    from collections import defaultdict
    count = defaultdict(int)
    for a in AS:
        factors = []
        while a > 1:
            d = eratree[a]
            factors.append(d)
            a //= d
            num_division += 1
        # debug(": ", factors)
        for f in set(factors):
            count[f] += 1

    # debug(": num_division", num_division)
    if any(x == N for x in count.values()):
        return "not coprime"
    if any(x >= 2 for x in count.values()):
        return "setwise coprime"
    return "pairwise coprime"


def main():
    # parse input
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


# tests
T1 = """
3
3 4 5
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
pairwise coprime
"""

T2 = """
3
6 10 15
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
setwise coprime
"""

T3 = """
3
6 10 16
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
not coprime
"""

T4 = """
3
100000 100001 100003
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
pairwise coprime
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Runtime Error

Solution code:
import numpy as np
n=int(input())
a=list(map(int, input().split()))

if np.gcd.reduce(a) != 1:
    print('not coprime')
    exit()

N=max(a)+1
A=list(range(2,N))
p=list()

while A[0]**2<=N:
	tmp=A[0]
	p.append(tmp)
	A=[e for e in A if e%tmp!=0]
l=p+A

#print(l)
for i in range(len(a)):
    count=0
    for j in range(len(l)):
        if a[i]%l[j]==0:
            count+=1
            if count > 1:
                print('setwise coprime')
                exit() 
    #print(count) 

print('pairwise coprime')

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import numba
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, AS):
    num_division = 0
    maxAS = max(AS)
    eratree = [0] * (maxAS + 10)
    for p in range(2, maxAS + 1):
        if eratree[p]:
            continue
        # p is prime
        x = p
        while x <= maxAS:
            if not eratree[x]:
                eratree[x] = p
            x += p

    from collections import defaultdict
    count = defaultdict(int)
    for a in AS:
        factors = []
        while a > 1:
            d = eratree[a]
            factors.append(d)
            a //= d
            num_division += 1
        # debug(": ", factors)
        for f in set(factors):
            count[f] += 1

    # debug(": num_division", num_division)
    if any(x == N for x in count.values()):
        return "not coprime"
    if any(x >= 2 for x in count.values()):
        return "setwise coprime"
    return "pairwise coprime"


def main():
    # parse input
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


# tests
T1 = """
3
3 4 5
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
pairwise coprime
"""

T2 = """
3
6 10 15
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
setwise coprime
"""

T3 = """
3
6 10 16
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
not coprime
"""

T4 = """
3
100000 100001 100003
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
pairwise coprime
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()