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:
large = 10**6+1
furui = [True]*(large)
prime_num = []
for num in range(large):
    if num in (0,1):
        furui[num] = False
    else:
        if furui[num]:
            times = 1
            while num * times < large:
                
                if times == 1:
                    prime_num.append(num)
                else:
                    furui[num*times] = False
                times += 1
N = int(input())
ls = list(map(int, input().split()))
num_divided = [0]*large
for element in ls:
  	if furui[element] = True:
      	num_devided[element] += 1
    else:
      	for num in range(len(prime_num)):
            diviser = prime_num[num]
            if diviser**2 > element:
                break
            else:
                if element % diviser == 0:
                    num_divided[diviser] += 1

if max(num_divided) <= 1:
    print("pairwise coprime")
elif max(num_divided) < N:
    print("setwise coprime")
else:
    print("neither")

Submission status: Runtime Error

Solution code:
large = 10**6+1
furui = [True]*(large)
prime_num = []
for num in range(large):
    if num in (0,1):
        furui[num] = False
    else:
        if furui[num]:
            times = 1
            while num * times < large:
                
                if times == 1:
                    prime_num.append(num)
                else:
                    furui[num*times] = False
                times += 1
N = int(input())
ls = list(map(int, input().split()))
num_divided = [0]*large
for element in ls:
  	if furui[element] = True:
      	num_decided[element] += 1
    else:
      	for num in range(len(prime_num)):
            diviser = prime_num[num]
            if diviser**2 > element:
                break
            else:
                if element % diviser == 0:
                    num_divided[diviser] += 1

if max(num_divided) <= 1:
    print("pairwise coprime")
elif max(num_divided) < N:
    print("setwise coprime")
else:
    print("neither")

Submission status: Runtime Error

Solution code:
large = 10**6+1
furui = [True]*(large)
prime_num = []
for num in range(large):
    if num in (0,1):
        furui[num] = False
    else:
        if furui[num]:
            times = 1
            while num * times < large:
                
                if times == 1:
                    prime_num.append(num)
                else:
                    furui[num*times] = False
                times += 1
N = int(input())
ls = list(map(int, input().split()))
num_divided = [0]*len(large)
for element in ls:
  	if furui[element] = True:
      	num_decided[element] += 1
    else:
      	for num in range(len(prime_num)):
            diviser = prime_num[num]
            if diviser**2 > element:
                break
            else:
                if element % diviser == 0:
                    num_divided[diviser] += 1

if max(num_divided) <= 1:
    print("pairwise coprime")
elif max(num_divided) < N:
    print("setwise coprime")
else:
    print("neither")

Submission status: Runtime Error

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

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


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

pc = True

fac = [0]*(10**3+1)
for a in A:
    lst = factorize(a)
    for p in lst:
        if not fac[p[0]]:
            fac[p[0]] = 1
        else:
            pc = False
            break
    if not pc:
        break
if pc:
    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:
n = int(input())
A = list(map(int,input().split()))

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

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

pc = True

fac = [0]*(10**3+1)
for a in A:
    lst = factorization(a)
    for p in lst:
        if not fac[p[0]]:
            fac[p[0]] = 1
        else:
            pc = False
            break
    if not pc:
        break
if pc:
    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:
from math import gcd
import numpy as np

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        d = 0
        while temp != 1:
            if p_count[D[temp]] == 1 and d != D[temp]:
                return 0
            p_count[D[temp]] = 1
            d = D[temp]
            temp = temp // D[temp]
    return 1

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Runtime Error

Solution code:
from math import gcd
import numpy as np

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        d = 0
        while temp != 1:
            if p_count[D[temp]] == 1 and d != D[temp]:
                return 0
            elif d != D[temp]:
                p_count[D[temp]] = 1
                d = D[temp]
            temp = temp // D[temp]
    return 1


# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Runtime Error

Solution code:
from math import gcd # Python3.6以降
# --------------------------------------------------------------

# n以下の素数列挙: O-nlogn
# def primes(n):
#     prs = []
#     is_prime = [True] * (n + 1)
#     is_prime[0] = False
#     is_prime[1] = False
#     for i in range(2, int(n**0.5)+1):
#         if not is_prime[i]:
#             continue
#         for j in range(i*2, n+1, i):
#             is_prime[j] = False
#     for i in range(len(is_prime)):
#         if is_prime[i]:
#             prs.append(i)
#     return prs

n    = int(input())
lis  = list(map(int,input().split()))
A    = 10**6
nlis = [0]*A
flg_pairwise = True

for i in range(n):
    nlis[lis[i]-1] += 1

for i in range(A):
    cnt = 0
    for j in range(i-1,A,i):
        cnt += nlis[j]
    if cnt > 1:
        flg_pairwise = False
        break

if flg_pairwise:
    print('pairwise coprime')
else:
    for i in range(n-1):
        if i==0:
            tmp = gcd(lis[i],lis[i+1])
        else:
            tmp = gcd(tmp,lis[i+1])

    if tmp==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Runtime Error

Solution code:
# In[]:
import math
from functools import reduce


# In[]:
def gcd_list(numbers):
    return reduce(math.gcd, numbers)


# In[]:
N = int(input())
input_str = input()
input_list = input_str.split()
input_int = [int(x) for x in input_list]


# In[]:
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    # print(data)
    for i in range(limit):
        p = data[0]
        prime += [p]
        # print(prime)
        data = [e for e in data if e % p != 0]
        if limit <= p:
            # print(limit, p)
            return prime + data


# In[]:
max_num = max(input_int)
# print(max_num)
prime_list = get_sieve_of_eratosthenes(max_num)
# print(prime_list)


# In[]:
def factorization(x):
    return [p for p in prime_list if x % p == 0]


# In[]:
factor_list = [factorization(x) for x in input_int]
# print(factor_list)
# c3 = list(set(factor_list[0]).intersection(factor_list[1]))
# print(c3)

# In[]:
gcd_all = gcd_list(input_int)
if gcd_all != 1:
    print('not coprime')
else:
    flag = 0
    for idx, i in enumerate(input_int):
        for j in range(idx+1, N):
            if len(list(set(factor_list[idx])\
                .intersection(factor_list[j]))) != 0:
                flag = 1
                break
        else:
            continue
        break
    if flag == 1:
        print('setwise coprime')
    elif flag == 0:
        print('pairwise coprime')

Submission status: Runtime Error

Solution code:
# In[]:
import math
from functools import reduce


# In[]:
def gcd_list(numbers):
    return reduce(math.gcd, numbers)


# In[]:
N = int(input())
input_str = input()
input_list = input_str.split()
input_int = [int(x) for x in input_list]


# In[]:
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    # print(data)
    for i in range(limit):
        p = data[0]
        prime += [p]
        # print(prime)
        data = [e for e in data if e % p != 0]
        if limit <= p:
            # print(limit, p)
            return prime + data


# In[]:
max_num = max(input_int)
print(max_num)
prime_list = get_sieve_of_eratosthenes(max_num)
print(prime_list)


# In[]:
def factorization(x):
    return [p for p in prime_list if x % p == 0]


# In[]:
factor_list = [factorization(x) for x in input_int]
print(factor_list)
c3 = list(set(factor_list[0]).intersection(factor_list[1]))
print(c3)

# In[]:
gcd_all = gcd_list(input_int)
if gcd_all != 1:
    print('not coprime')
else:
    flag = 0
    for idx, i in enumerate(input_int):
        for j in range(idx+1, N):
            if len(list(set(factor_list[idx])\
                .intersection(factor_list[j]))) != 0:
                flag = 1
                break
        else:
            continue
        break
    if flag == 1:
        print('setwise coprime')
    elif flag == 0:
        print('pairwise coprime')

Submission status: Runtime Error

Solution code:
import math
import sys

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

    #pairwise

    A_max=max(A)

    D=[-1 for _ in range(A_max+1)]
    F=[i for i in range(2,A_max+1)]
    bound=math.sqrt(A_max)
    n=F[0]
    while len(F)>0:
        temp=[]
        for f in F:
            if f%n!=0:
                temp.append(f)
            else:
                D[f]=n
        F=temp[:]
        if len(F)>0:
            n=F[0]
    F = [0 for i in range(A_max + 1)]
    flag=0
    for i in range(len(A)):
        n=A[i]
        if F[n]==0:
            F[n]=1
        else:
            flag=1
            break
        while D[n]!=n:
            n=D[n]
            if F[n]==0:
                F[n]=1
            else:
                flag=1
                break
        if flag==1:
            break
    if flag==0:
        print("pairwise coprime")
        sys.exit()
    g=A[0]
    for i in range(len(A)-1):
        g=math.gcd(g,A[i+1])
    if g==1:
        print("setwise coprime")
        sys.exit()
    print("not coprime")
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
from math import gcd # Python3.6以降
# --------------------------------------------------------------

# n以下の素数列挙: O-nlogn
def primes(n):
    prs = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            prs.append(i)
    return prs

n    = int(input())
lis  = list(map(int,input().split()))
soin = [0]*(10**6)
cnt  = 0
ans  = 'pairwise coprime'

for i in range(n):
    soin[lis[i]] += 1

for i in primes(10**6):
    for j in range(1,10**6):
        if i*j >= 10**6:
            break
        cnt += soin[i*j]
        if cnt > 1:
            ans = 'not coprime'
            break

for i in range(n-1):
    if i==0:
        tmp = gcd(lis[i],lis[i+1])
    else:
        tmp = gcd(tmp,lis[i+1])

if tmp==1:
    ans = 'setwise coprime'

print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd # Python3.6以降
# --------------------------------------------------------------

# n以下の素数列挙: O-nlogn
def primes(n):
    prs = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            prs.append(i)
    return prs

n    = int(input())
lis  = list(map(int,input().split()))
soin = [0]*(10**6)
cnt  = 0
ans  = ''

for i in range(n):
    soin[lis[i]] += 1

for i in primes(10**6):
    for j in range(1,10**6):
        if i*j >= 10**6:
            break
        cnt += soin[i*j]
        if cnt > 1:
            ans = 'pairwise coprime'
            break

if ans == '':
    for i in range(n-1):
        if i==0:
            tmp = gcd(lis[i],lis[i+1])
        else:
            tmp = gcd(tmp,lis[i+1])
    
    if tmp==1:
        ans = 'setwise coprime'
    else:
        ans = 'no coprime'

print(ans)

Submission status: Runtime Error

Solution code:
import functools
from math import gcd
N = int(input())
A = list(map(int, input().split()))
MAX = 10 * 6 + 10

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

prime_list = [i for i in range(MAX + 1)]
p = 2
while p * p <= MAX:
    if prime_list[p] == p:
        for q in range(2*p, MAX+1, p):
            if prime_list[q] == q:
                prime_list[q] = p
    p += 1

prime = set()
for a in A:
    tmp = set()
    while a > 1:
        tmp.add(prime_list[a])
        a //= prime_list[a]
    for p in tmp:
        if p in prime:
            print("setwise coprime")
            exit()
        prime.add(p)
else:
    print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import functools
from math import gcd
N = int(input())
A = list(map(int, input().split()))
MAX = 10 * 6 + 10

if functools.reduce(gcd, A) == 1:
    print("setwise coprime")
    exit()

prime_list = [i for i in range(MAX + 1)]
p = 2
while p * p <= MAX:
    if prime_list[p] == p:
        for q in range(2*p, MAX+1, p):
            if prime_list[q] == q:
                prime_list[q] = p
    p += 1

prime = set()
for a in A:
    tmp = set()
    while a > 1:
        tmp.add(prime_list[a])
        a //= prime_list[a]
    for p in tmp:
        if p in prime:
            print("setwise coprime")
            exit()
        prime.add(p)
else:
    print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import functools
from math import gcd
N = int(input())
A = list(map(int, input().split()))
MAX = 10 * 6 + 10

prime_list = [i for i in range(MAX + 1)]
p = 2
while p * p <= MAX:
    if prime_list[p] == p:
        for q in range(2*p, MAX+1, p):
            if prime_list[q] == q:
                prime_list[q] = p
    p += 1

prime = set()
cnt = 0
for a in A:
    tmp = set()
    while a > 1:
        tmp.add(prime_list[a])
        a //= prime_list[a]
    prime = prime | tmp
    cnt += len(tmp)

if len(prime) == cnt:
    print("pairwise coprime")
elif functools.reduce(gcd, A) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import functools
from math import gcd
N = int(input())
A = list(map(int, input().split()))
MAX = 10 * 6 + 10

prime_list = [i for i in range(MAX + 1)]
p = 2
while p * p <= MAX:
    if prime_list[p] == p:
        for q in range(2*p, MAX+1, p):
            if prime_list[q] == q:
                prime_list[q] = p
    p += 1

prime = set()
cnt = 0
for a in A:
    v = prime_list[a]
    tmp = set()
    while a > 1:
        tmp.add(v)
        a //= v
    prime = prime | tmp
    cnt += len(tmp)

if len(prime) == cnt:
    print("pairwise coprime")
elif functools.reduce(gcd, A) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()

def fast_prime_factorization(A, max_num):
    """
    リストAに現れる自然数全てをO(NlogN)で素因数分解する（NはリストAの長さ）
    max_numはAに現れる自然数の上界。
    """
    # エラトステネスの篩でprimes[i] = (iを割り切る最小の素数)を記録する
    primes = [0] * (max_num + 1)
    for i in range(2, int(max_num**0.5) + 1):
        if primes[i] != 0: continue
        for j in range(i, max_num + 1, i):
            if primes[j] == 0: primes[j] = i

    # factorization[i] = {p1:n1, p2:n2, ...} (A[i] = p1^{n1} * p2^{n2} * ...)
    factorization_list = [{} for _ in range(len(A))]
    for i, a in enumerate(A):
        while a > 1:
            if primes[a] not in factorization_list[i]:
                factorization_list[i][primes[a]] = 1
            else:
                factorization_list[i][primes[a]] += 1
            a //= primes[a]

    return factorization_list


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

    all_gcd = A[0]
    for a in A:
        all_gcd = gcd(all_gcd, a)
    if all_gcd != 1:
        print("not coprime")
        return

    prime_factor_list = fast_prime_factorization(A, 10**6)
    d = set()
    for factor_dict in prime_factor_list:
        for prime in factor_dict:
            if prime in d:
                print("setwize coprime")
                return
            d.add(prime)
    print("pairwise coprime")




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

n = int(input())
a_list = list(map(int, input().split()))
max = a_list[n - 1] + 100
memo = [0] * max

for a in a_list:
    memo[a] += 1

for i in range(2, max):
    if sum(memo[i::i]) > 1:
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()

print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

n = int(input())
a_list = list(map(int, input().split()))
max = a_list[n - 1] + 100
memo = [0] * max

for a in a_list:
    print(a)
    print(memo)
    memo[a] += 1

for i in range(2, max):
    if sum(memo[i::i]) > 1:
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()

print("pairwise coprime")

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

A = max(As)
lst = [0]*(A+1)
rlt = [0]*(A+1)

for i in range(2, len(lst)//2):
  if lst[i] > 0:
    continue
  j = 1
  while i*j <= A:
    if lst[i*j] == 0:
      lst[i*j] = i
    j += 1
    
for a in As:
  tmp = -1
  while a > 1:
    if tmp != lst[a]:
      rlt[lst[a]] += 1
      tmp = lst[a]
    a //= lst[a]

r = max(rlt) 

if r < 2:
  print('pairwise coprime')
elif r < N:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

n = int(input())
a_list = list(map(int, input().split()))
max = a_list[n - 1]
memo = [0] * max

for a in a_list:
    memo[a] += 1

for i in range(2, max):
    if sum(memo[i::i]) > 1:
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()

print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

n = int(input())
a_list = list(map(int, input().split()))
max = a_list[n - 1] + 1
memo = [0] * max

for a in a_list:
    memo[a] += 1

for i in range(2, max):
    if sum(memo[i::i]) > 1:
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()

print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

n = int(input())
a_list = list(map(int, input().split()))
max = a_list[-1] + 2
memo = [0] * max

for a in a_list:
    memo[a] += 1

for i in range(2, max):
    if sum(memo[i::i]) > 1:
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()

print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

n = int(input())
a_list = list(map(int, input().split()))
max = a_list[-1] + 1
memo = [0] * max

for a in a_list:
    memo[a] += 1

for i in range(2, max):
    if sum(memo[i::i]) > 1:
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()

print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

n = int(input())
a_list = list(map(int, input().split()))
memo = [0] * (a_list[-1] + 1)

for a in a_list:
    memo[a] += 1

for i in range(2, a_list[-1] + 1):
    if sum(memo[i::i]) > 1:
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()

print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

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

for i in range(2, prime_list[-1] + 1):
    if prime_list[i] != -1:
        for j in range(i * 2, prime_list[-1] + 1, i):
            prime_list[index] = -1
prime_list.sort()
del prime_list[0: prime_list.index(1) + 1]
check_list = [0] * len(prime_list)

def is_pairwise(num):
    for i, prime in enumerate(prime_list):
        if num % prime == 0:
            if check_list[i] == 1:
                return False
            else:
                check_list[i] += 1
    return True

for a in a_list:
    if not is_pairwise(a):
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()
print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

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

for i in range(2, prime_list[-1] + 1):
    if prime_list[i] != -1:
        for j in range(i * 2, prime_list[-1] + 1, i)
            prime_list[index] = -1
prime_list.sort()
del prime_list[0: prime_list.index(1) + 1]
check_list = [0] * len(prime_list)

def is_pairwise(num):
    for i, prime in enumerate(prime_list):
        if num % prime == 0:
            if check_list[i] == 1:
                return False
            else:
                check_list[i] += 1
    return True

for a in a_list:
    if not is_pairwise(a):
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()
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

check=set()

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

Submission status: Runtime Error

Solution code:
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()

def main():
    N = int(input())
    A =list(map(int, input().split()))
    A.sort()

    idx = 0
    while A[idx] == 1: idx += 1
    A = A[idx:]
    if idx == N:
        print("pairwise coprime")
        return

    all_gcd = A[0]
    for a in A:
        all_gcd = gcd(all_gcd, a)
    if all_gcd != 1:
        print("not coprime")
        return

    prod = A[0]
    for i, a in enumerate(A):
        if i == 0: continue
        if gcd(prod, a) != 1:
            print("setwise coprime")
            return
        prod *= a
    print("pairwise coprime")




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()

def main():
    N = int(input())
    A =list(map(int, input().split()))
    A.sort()

    idx = 0
    while A[idx] == 1: idx += 1
    A = A[idx:]

    all_gcd = A[0]
    for a in A:
        all_gcd = gcd(all_gcd, a)
    if all_gcd != 1:
        print("not coprime")
        return

    prod = A[0]
    for i, a in enumerate(A):
        if i == 0: continue
        if gcd(prod, a) != 1:
            print("setwise coprime")
            return
        prod *= a
    print("pairwise coprime")




if __name__ == "__main__":
    main()

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 precompute():
    maxAS = 1000000
    eratree = [0] * (maxAS + 10)
    for p in range(2, maxAS + 1):
        if eratree[p]:
            continue
        # p is prime
        eratree[p] = p
        x = p * p
        while x <= maxAS:
            if not eratree[x]:
                eratree[x] = p
            x += p

    import pickle
    pickle.dump(eratree, open("eratree.pickle", "wb"))


def solve(N, AS):
    import pickle
    eratree = pickle.load(open("eratree.pickle"))
    num_division = 0

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

if sys.argv[-1] == 'ONLINE_JUDGE':
    precompute()
else:
    main()

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

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

for i in range(2, prime_list[-1] + 1):
    if prime_list[i] != -1:
        index = i
        while index + i <= prime_list[-1]:
            index += i
            prime_list[index] = -1
prime_list.sort()
del prime_list[0: prime_list.index(1) + 1]
check_list = [0] * len(prime_list)

def is_pairwise(num):
    for i, prime in enumerate(prime_list):
        if num % prime == 0:
            if check_list[i] == 1:
                return False
            else:
                check_list[i] += 1
    return True

for a in a_list:
    if not is_pairwise(a):
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()
print("pairwise coprime")