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 defaultdict
def enumerate_primes(n):
    if n == 1: return []
    primes = [2] + list(range(3, n + 1, 2))
    i, p = 0, 1
    while p * p <= n:
        if primes[i] != 0:
            p = primes[i]
            primes = [prime if (prime % p != 0 or prime == p) else 0 for prime in primes]
        i += 1
    return [p for p in primes if p != 0]

def main():   
    n = int(input())
    A = list(map(int, input().split()))
    primes = enumerate_primes(int(max(A) ** 0.5) + 1)
    d = defaultdict(int)
    for a in A:
        for p in primes:
            if a % p == 0:
                d[p] += 1
    m = max(d.values())
    if m == n:
        print('not coprime')
    elif m >= 2:
        print('setwise coprime')
    else:
        print('pairwise coprime')

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def prime_factorize(n):
    '''
    素因数分解のリストを返す。n == 1のとき[]になるので注意。
    :param n:int
    素因数分解する自然数
    :return: list
    素因数分解した結果。

    例
    n : 10
    primes : [[2, 1], [5, 1]]
    '''
    primes = []
    for i in range(2, int(n ** (1 / 2)) + 1):
        if n % i != 0:
            continue
        num = 0
        while n % i == 0:
            num += 1
            n //= i
        primes.append([i, num])
    if n != 1:
        primes.append([n, 1])
    return primes

N = int(input())
A = list(map(int, input().split()))
# N = 10 ** 6
# A = [10 ** 6] * N
pairwise = False
prime_key = set(prime_factorize(A[-1]).keys())
break_flag = False
prime_flags = [False] * (10 ** 6 + 1)
for i in range(N):
    for key in prime_factorize(A[i]).keys():
        if prime_flags[key]:
            break_flag = True
            break
        else:
            prime_flags[key] = True
    if break_flag:
        break
else:
    pairwise = True
if pairwise:
    print('pairwise coprime')
    exit()
work = gcd(A[0], A[1])
for i in range(2, N):
    work = gcd(work, A[i])
if work != 1:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Runtime Error

Solution code:
d = None
u = set()
r = 'pairwise'
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  s = set()
  i = 2
  while i * i <= x:
    while x % i == 0:
      if i in u:
        r = 'setwise'
      s.add(i)
      x //= i
    i += 1
  if x > 1:
    if x in u:
      r = 'setwise'
    s.add(x)
  u |= s
print((r, 'not')[d > 1], 'coprime')

Submission status: Runtime Error

Solution code:
import math
  
input()
d = None
u = set()
r = 'pairwise'
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  s = set()
  i = 2
  while i * i <= n:
    while n % i == 0:
      if i in u:
        r = 'setwise'
      s.add(i)
      n //= i
    i += 1
  if n > 1:
    if n in u:
      r = 'setwise'
    s.add(n)
  u |= s
print((r, 'not')[d > 1], 'coprime')

Submission status: Runtime Error

Solution code:
#coding: utf-8

from collections import defaultdict
from functools import reduce
from math import gcd

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

def primeFac(N):
    ret = set()
    i = 2
    while i*i <= N:
        if N % i == 0:
            ret.add(i)
            while N % i == 0:
                N //= i
        i += 1

    if N != 1:
        ret.add(N)
    return ret

numDiv = defaultdict(int) 
for a in A:
    for f in primeFac(a):
        numDiv[f] += 1
#print(numDiv, max(numDiv))
if max(numDiv.values()) == 1:
    print("pairwise coprime")
else:
    if (reduce(gcd, A) == 1):
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sympy

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

fd = set([1])
flag = 'pairwise coprime'

mimm = set(sympy.divisors(min(ab)))


for a in ab:
    if fd & set(sympy.divisors(a)) != {1}:
        flag = 'setwise coprime'
    fd = fd | set(sympy.divisors(a))

if flag ==  'setwise coprime':
    flag = 'not coprime'
    for a in ab:
        mimm =  mimm & set(sympy.divisors(a))
        if mimm  == {1}:
            flag ='setwise coprime'
            break
        
print(flag)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import math

INF = 10 ** 5
is_prime = [1] * INF

def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return

def f(n):
    yakusu = []
    if is_prime[n]:
        yakusu.append(n)
    else:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                yakusu.append(i)
                break

    for i in yakusu:
        if i != 1:
            d[i] += 1

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

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
    f(A[i])

if tmp != 1:
    print('not coprime')
    exit()
eratorasu()
f(A[0])

#for i, v in d.items():
#    if v != 1:
#        print('setwise coprime')
#        exit()

print('pairwise coprime')

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import math

INF = 10 ** 5
is_prime = [1] * INF

def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return

def f(n):
    yakusu = []
    if is_prime[n]:
        yakusu.append(n)
    else:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                yakusu.append(i)
                break

    for i in yakusu:
        if i != 1:
            d[i] += 1

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

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
    f(A[i])

if tmp != 1:
    print('not coprime')
    exit()
eratorasu()
f(A[0])
for i, v in d.items():
    if v != 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')

Submission status: Runtime Error

Solution code:
import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

cons = 10 ** 6
is_prime = [True] * (cons + 1)
Ds = [i for i in range(cons + 1)]
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(cons**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, cons + 1, i):
        is_prime[j] = False
        if Ds[j] == j:
          Ds[j] = i 

Ps = [i for i in range(cons + 1) if is_prime[i]]
flags = [[0 for _ in range(n)] for _ in range(int(cons**0.5))]
pairwiseFlag = True
setwiseFlag = True

for ia, a in enumerate(As):
  if a <= 1:
    continue
  while a != 1:
    d = Ds[a]
    flags[d][ia] = 1
    a = a // d
for i in range(int(cons**0.5)):
  s = sum(flags[i])
  if s >= 2:
    pairwiseFlag = False
  if s == n:
    setwiseFlag = False

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

Submission status: Runtime Error

Solution code:
class Sieve:
    """
    N以下の素数を列挙するエラトステネスのふるいです。
    O(NloglogN)でできます。

    Attributes
    sieveList : その数の素因数のうち最小のものの配列
    primes : N以下の素因数のリスト
    """
    def __init__(self, N):
        self.sieveList = [-1 for _ in range(N+1)]
        self.sieveList[1] = 1
        self.primes = []

        for i in range(2, N+1):
            #すでに何らかの数で割られていたらcontinue
            if self.sieveList[i] != -1:
                continue
            self.primes.append(i)
            for j in range(i, N+1, i):
                if self.sieveList[j] != -1:
                    continue
                self.sieveList[j] = i

    def getPrimes(self):
        return self.primes

    def getSieveList(self):
        return self.sieveList

class FastFactorization(Sieve):
    """
    高速素因数分解です。
    与えられたL個の数がA以下の時、
    エラトステネスでO(AloglogA)＋素因数分解でO(LlogA) = O(AloglogA+NlogA)でできます。
    """

    def __init__(self, N):
        """
        前処理でスーパークラスのエラトステネスを使ってN以下の素因数を列挙します。
        """
        super().__init__(N)
        self.N = N
        self.sieveList = self.getSieveList()

    def factorize(self, x):
        if x > self.N:
            raise ValueError("与えられた数がエラトステネスのリストの上限を超えている")
        p = set()
        # p = []
        while x > 1:
            divisor = self.sieveList[x]
            x //= divisor
            p.add(divisor)
            # p.append(divisor)
        return p

import math
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

#is setwise?
gcd = A[0]
for i in range(1, N):
    gcd = math.gcd(gcd, A[i])
isSetwise = (gcd == 1)

#is pairwise?
maxNum = max(A)
factorizor = FastFactorization(maxNum)
factors = defaultdict()
isPairwise = True
for i in range(N):
    p = factorizor.factorize(A[i])
    for x in p:
        if factors[x]:
            isPairwise = False
            break
        else:
            factors[x] = 1

if isPairwise:
    print("pairwise coprime")
elif isSetwise:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import math

N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'

input()
d = None
p = 1
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
import math

N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'

input()
d = None
p = 1
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  e = maths = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print((r, 'not')[d > 1], 'coprime')

Submission status: Runtime Error

Solution code:
import math

N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'

input()
d = None
p = 1
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  e = maths = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print((r, 'not')[d > 1], 'coprime')

Submission status: Runtime Error

Solution code:
import math


def get_input():
    N = int(input())
    A = [int(x) for x in input().split()]
    return N, A


def sieve_of_eratosthenes(x: int):
    ret = [-1] * (x + 1)
    for i in range(1, x + 1):
        ret[i] = i
    p_max = int(math.sqrt(x))
    for p in range(2, p_max + 1):
        if ret[p] < p:  # p is not a prime number
            continue
        for i in range(p, x + 1, p):
            if ret[i] > p:
                ret[i] = p
    return ret


A_max = 100000
p_table = sieve_of_eratosthenes(A_max)

N, A = get_input()
# Store a number of unique Ais using the prime number
p_nums = [0] * (A_max + 1)
max_p_nums = 0
for a in A:
    while a > 1:
        p = p_table[a]
        while a % p == 0:
            a = int(a / p)
        p_nums[p] += 1
        if max_p_nums < p_nums[p]:
            max_p_nums = p_nums[p]
if max_p_nums == 1:
    print('pairwise coprime')
elif max_p_nums < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
import math


# def get_pseudo_input():
#     N = 3
#     A = [3, 4, 5]
#     return N, A


def get_input():
    N = int(input())
    A = [int(x) for x in input().split()]
    return N, A


def sieve_of_eratosthenes(x: int):
    ret = [-1] * (x + 1)
    for i in range(1, x + 1):
        ret[i] = i
    p_max = int(math.sqrt(x))
    for p in range(2, p_max + 1):
        if ret[p] < p:  # p is not a prime number
            continue
        for i in range(p, x + 1, p):
            if ret[i] > p:
                ret[i] = p
    return ret


A_max = 100000
p_table = sieve_of_eratosthenes(A_max)

N, A = get_input()
# Store a number of unique Ais using the prime number
p_nums = [0] * (A_max + 1)
max_p_nums = 0
for a in A:
    # print(f"a={a}")
    ps = set()
    while a > 1:
        p = p_table[a]
        a = int(a / p)
        # print(f"  a={a}")
        # Count up at most 1 for one a
        if p not in ps:
            p_nums[p] += 1
            ps.add(p)
        if max_p_nums < p_nums[p]:
            max_p_nums = p_nums[p]
# print(max_p_nums)
if max_p_nums == 1:
    print('pairwise coprime')
elif max_p_nums < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
import math
L = 10**6 + 1

N = int(input())
A = list(map(int, input().split()))
memo = [0] * L
flag = 0 # 0をpairwise coprime

for a in A:
    memo[a] = 1

for i in range(2, L):
    if sum(memo[i::i]) > 1:
        flag = 1:
        break

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

if flag == 0:
    answer = 'pairwise coprime'
elif flag == 1 and g == 1:
    answer = 'setwise coprime'
else:
    answer = 'not coprime'

print(answer)

Submission status: Runtime Error

Solution code:
from math import gcd


class Eratosthenes(): # エラトステネスの篩
    def __init__(self, N) # 素数リスト生成 O(n*log(log n))
        is_prime = [0, 0] + [1] * (N - 1)
        for i in range(int(N**0.5) + 1):
            if is_prime[i] == 0:
                continue
            for j in range(i * 2, N + 1, i):
                is_prime[j] = 0
        self.prime_list = [i for i, pi in enumerate(is_prime) if pi == 1]


    def factor(self, NUM):  # 高速素因数分解 O(log num)
        PRIME = set()
        for p in self.prime_list:
            if p * p > NUM:
                break
            while NUM % p == 0:
                NUM //= p
                PRIME.add(p)
        if NUM > 1:
            PRIME.add(NUM)
        return PRIME


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

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

era = Eratosthenes(max(a))
num = set()
for ai in a:
    prime = era.factor(ai)
    if len(prime & num) > 0:
        print('setwise coprime')
        break
    num |= prime
else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
from math import gcd


class Eratosthenes: # エラトステネスの篩
    def __init__(self, N) # 素数リスト生成 O(n*log(log n))
        is_prime = [0, 0] + [1] * (N - 1)
        for i in range(int(N**0.5) + 1):
            if is_prime[i] == 0:
                continue
            for j in range(i * 2, N + 1, i):
                is_prime[j] = 0
        self.prime_list = [i for i, pi in enumerate(is_prime) if pi == 1]


    def factor(self, NUM):  # 高速素因数分解 O(log num)
        PRIME = set()
        for p in self.prime_list:
            if p * p > NUM:
                break
            while NUM % p == 0:
                NUM //= p
                PRIME.add(p)
        if NUM > 1:
            PRIME.add(NUM)
        return PRIME


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

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

era = Eratosthenes(max(a))
num = set()
for ai in a:
    prime = era.factor(ai)
    if len(prime & num) > 0:
        print('setwise coprime')
        break
    num |= prime
else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
from math import gcd


class Eratosthenes: # エラトステネスの篩
    def __init__(self, N) # 素数リスト生成 O(n*log(log n))
        is_prime = [0, 0] + [1] * (N - 1)
        for i in range(int(N**0.5) + 1):
            if is_prime[i] == 0:
                continue
            for j in range(i * 2, N + 1, i):
                is_prime[j] = 0
        self.prime_list = [i for i, pi in enumerate(is_prime) if pi == 1]


    def factor(self, NUM):  # 高速素因数分解 O(log num)
        PRIME = set()
        for p in self.prime_list:
            if p * p > NUM:
                break
            while NUM % p == 0:
                NUM //= p
                PRIME.add(p)
        if NUM > 1:
            PRIME.add(NUM)
        return PRIME


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

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print(‘not coprime’)
    exit()

era = Eratosthenes(max(a))
num = set()
for ai in a:
    prime = era.factor(ai)
    if len(prime & num) > 0:
        print(‘setwise coprime’)
        break
    num |= prime
else:
    print(‘pairwise coprime’)

Submission status: Runtime Error

Solution code:
# pairwise coprime <= setwise coprime の順に判定するのが効率が良い。
# 問題は pairwise をどのように効率よく計算するか。全探索は計算量の観点から厳しい。数字の設定的に O(N logN) 程度のアルゴリズムを想定していそう。
# エラトステネスで素数列挙　=> 全て素因数分解し、各素因数の出現回数を数える。
# もし各一回ずつなら、pairwise、ある素因数でn回出現するものがあれば、どちらでもない

def sieve(N):
    if N < 2:
        return None
    elif N == 2:
        return [2]
    data = [i for i in range(2,N+1)]
    P = []
    limit = min(int(N**0.5)+10,N)
    while True:
        p = data[0]
        if limit <= p:
            return P+data
        P.append(p)
        data = [e for e in data if e%p]

def p_fact(N,p):
    ret = False
    while N%p==0:
        N //= p
        ret = True
    return ret,N

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

primes = sieve(N)
d = dict()

for a in A:
    tmp = a
    for p in primes:
        if tmp%p == 0:
            flag,tmp = p_fact(tmp,p)
            if flag:
                if p in d:
                    d[p] += 1
                else:
                    d[p] = 1
        if p > tmp:break

T = 0
for p in d:
    T = max(T,d[p])
if T == N:
    print("not coprime")
elif T == 1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    from math import gcd
    
    # 篩の応用でnまでの数全部を素因数分解する
    
    # nまでの素数を列挙(n loglogn)
    n = 10**4 + 5
    
    D=[1]*(n+1) # 篩をしたときに初めて割った数

    #is_prime[i]にはi+1が素数か否かを示すboolが入る，[0]に1の素数判定がある(1-index)．
    is_prime = [True]*(n+1)
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            D[i-1]=i
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                if D[j-1]==1: # D[j-1]にはその数を初めて割れる数を入れとく
                    D[j-1]=i
                j += i

    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    P=[[]for _ in range(n)]
    
    # print(D)
    for i in range(2,n):
        if is_prime[i-1]:
            P[i-1].append(i)
        else:
            now=i
            while now >= 2:
                # print(i,D[now-1])
                P[i-1].append(D[now-1])
                now=now//D[now-1]

    # for i in range(100):
    #     print(i+1,P[i])
    
    N=I()
    A=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    flag=1
    for i in range(N):
        a=A[i]
        S=set(P[a-1])
        # print(a,S)
        for p in S:
            if dd[p]:
                flag=0
                break
            dd[p]+=1
    

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

main()

Submission status: Runtime Error

Solution code:
# E - Coprime

import math
from functools import reduce
from itertools import chain
from collections import Counter

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

if reduce(math.gcd, a) > 1:
    print("not coprime")
    exit()

def factors(n):
    """Return the list of prime factors of n."""
    fac = set()
    d = 2
    while d <= math.sqrt(n):
        if n % d == 0:
            fac.add(d)
            n //= d
        else:
            d += 1
    if n > 1:
        fac.add(n)
    return fac

c = Counter(chain.from_iterable(map(factors, a)))
if max(c.values()) > 1:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5)
        data = [i for i in range(2, n + 1)]
        while data[0]:
            p = data[0]
            if limit <= p:
                return D
            for i, d in enumerate(data):
                mod = d % p
                if mod != 0:
                    continue
                else:
                    D[d] = p
                    del data[i]
        return D



    N = I()
    A = LI()
    D = defaultdict()
    num_list = [0] * (10 ** 6 + 1)

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()
    max_a = max(A)
    if max_a == 1:
        print('pairwise coprime')
    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        while a != 1:
            if D.get(a) is None:
                D[a] = a
            x = D[a]
            if num_list[x] == 1:
                print('setwise coprime')
                exit()
            num_list[x] = 1
            a //= x

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
from numba import njit, i8 
import numpy as np

n = int(input())
alist = list(map(int,input().split()))
alist = np.array(alist)
a_max = max(alist)

D = [i for i in range(a_max+1)]
D = np.array(D)
D[0] = 1
D[1] = 1

@njit(i8[:](i8,i8[:]),cache=True)
def factor(n,D):
    f = set()
    f.add(n)
    while n > 1:
        f.add(D[n])
        n //= D[n]
    f.add(1)
    return np.array(list(f))

@njit(i8(i8,i8), cache=True)
def gcf(a,b):
    if a == 0:
        return b
    return gcf(b % a,a)

@njit((i8,i8[:],i8[:]),cache=True)
def main(n,alist,D):
    a_max = max(alist)
    p = 2
    top = math.ceil(math.sqrt(a_max))
    for i in range(2,top+1):
        if D[i] == i:
            p = i
            mul_p = p
            while mul_p <= a_max:
                D[mul_p] = min(p,D[mul_p])
                mul_p += p
    factor_set = set()
    pairwise = True
    for i in range(n):
        a = alist[i]

        a_factor = factor(a,D)
        for f in a_factor:
            if f != 1 and f in factor_set:
                pairwise = False
                break
            factor_set.add(f)

        if pairwise == False:
            break
    if pairwise == True: 
        print("pairwise coprime")
        exit()

    #setwise
    now = alist[0]
    for i in range(1,n-1):
        now = gcf(now,gcf(alist[i],alist[i+1]))

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

main(n,alist,D)

Submission status: Runtime Error

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5)
        data = [i for i in range(2, n + 1)]
        while data[0]:
            p = data[0]
            if limit <= p:
                return D
            for i, d in enumerate(data):
                mod = d % p
                if mod != 0:
                    continue
                else:
                    D[d] = p
                    del data[i]
        return D



    N = I()
    A = LI()
    D = defaultdict()
    num_list = [0] * (10 ** 6 + 1)

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()
    max_a = max(A)
    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        while a != 1:
            if D.get(a) is None:
                D[a] = a
            x = D[a]
            if num_list[x] == 1:
                print('setwise coprime')
                exit()
            num_list[x] = 1
            a //= x

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def _make_minimum_prime(N: int):
    # xの最小の素因数表を作成
    min_prime = [x for x in range(N + 1)]
    # min_prime[0] = 0  # 0と1は素数ではない
    # min_prime[1] = 1
    for i in range(2, int(N ** 0.5) + 1):
        if min_prime[i] == i:  # 素数だったら更新
            for j in range(2 * i, N + 1, i):  # iの倍数は素数でない
                if min_prime[j] == j:
                    min_prime[j] = i
    return min_prime


min_prime = _make_minimum_prime(10**6)


from collections import Counter


def fast_factorization(N: int):
    # -> List[Tuple[int,int]] (素数,冪数)を格納
    # 最小素数配列min_primeを使ってO(log N)で因数分解
    if N == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    tmp = N
    while tmp != 1:
        p = min_prime[tmp]
        tmp //= p
        arr.append(p)

    return Counter(arr)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from math import gcd


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
for a in A:
    g_set = gcd(g_set, a)
    if flg:
        for p, n in fast_factorization(a).items():
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def _make_minimum_prime(N: int):
    # xの最小の素因数表を作成
    min_prime = [N + 114514] * (N + 1)
    min_prime[0] = 0  # 0と1は素数ではない
    min_prime[1] = 1
    for i in range(2, int(N ** 0.5) + 1):
        if min_prime[i] == N + 114514:  # 素数だったら更新
            min_prime[i] = i
            for j in range(2 * i, N + 1, i):  # iの倍数は素数でない
                min_prime[j] = min(min_prime[j], i)
    return min_prime


min_prime = _make_minimum_prime(10**6)


from collections import Counter


def fast_factorization(N: int):
    # -> List[Tuple[int,int]] (素数,冪数)を格納
    # 最小素数配列min_primeを使ってO(log N)で因数分解
    if N == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    tmp = N
    while tmp != 1:
        p = min_prime[tmp]
        tmp //= p
        arr.append(p)

    return Counter(arr)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from math import gcd


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
for a in A:
    g_set = gcd(g_set, a)
    if flg:
        for p, n in fast_factorization(a).items():
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def _make_minimum_prime(N: int):
    # xの最小の素因数表を作成
    min_prime = [N + 114514] * (N + 1)
    min_prime[0] = 0  # 0と1は素数ではない
    min_prime[1] = 1
    for i in range(2, int(N ** 0.5) + 1):
        if min_prime[i] == N + 114514:  # 素数だったら更新
            for j in range(i, N + 1, i):  # iの倍数は素数でない
                min_prime[j] = min(min_prime[j], i)
    return min_prime


min_prime = _make_minimum_prime(10**6)


from collections import Counter


def fast_factorization(N: int):
    # -> List[Tuple[int,int]] (素数,冪数)を格納
    # 最小素数配列min_primeを使ってO(log N)で因数分解
    if N == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    tmp = N
    while tmp != 1:
        p = min_prime[tmp]
        tmp //= p
        arr.append(p)

    return Counter(arr)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from math import gcd


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
for a in A:
    g_set = gcd(g_set, a)
    if flg:
        for p, n in fast_factorization(a).items():
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')