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 sys
import math

if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    check_pairwise()
    check_set()
    return


def check_pairwise():
    active = set()
    for i in range(0, n):
        pp = getprimes(a[i])
        for p in pp:
            if p in active:
                return
            else:
                active.add(p)
    print("pairwise coprime")
    exit()



def check_set():
    active = getprimes(a[0])
    for i in range(1, n):
        if not a[i] % a[i-1] == 0:
            for act in active:
                if not a[i] % act == 0:
                    active.remove(act)
                    if not active:
                        print("setwise coprime")
                        exit()
    print("not coprime")
    exit()




def getprimes(num):
    if num in primes:
        return set([num])
    pp = set()
    for p in primes:
        if p > int(math.sqrt(num)+2):
            break
        if num % p == 0:
            pp.add(p)

    return pp




def n_primes(n):
    nums = list(range(0, n + 1))
    primes = []
    for i in range(2, n + 1):
        num = nums[i]
        if num != 0:
            primes.append(num)
            for i in range(0, n // num + 1):
                nums[i * num] = 0
    return primes


n = RN()
a = sorted(RA())
primes = set(n_primes(10 ** 6))
solve()

Submission status: Runtime Error

Solution code:
def make_divisors(n):
    divisors = []
    # 試し割りで、かつ積でnを作るときの相方も同時に追加してる
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
from math import gcd
import sys
n = int(input())
a_ls = list(map(int, input().split()))
now = a_ls[0]
for i in range(1,n):
    now = gcd(now,a_ls[i])
if now != 1:
    print('not coprime')
    sys.exit()
else:
    a_ls.sort()
    is_in_a = [0] * (10**6+1)
    for a in a_ls:
        is_in_a[a] = 1
    Max = a_ls[-1]

    res = 'pairwise coprime'
    
    lim = int(Max**0.5)+2
    isdone = [0] * (Max+1)
    # baseは共通の素因数の候補
    for base in range(2,lim+1):
        if isdone[base]:
            continue
        now = base*2
        time_inA = 0
        while now <= Max:
            isdone[now] = 1
            if is_in_a[now]:
                time_inA += 1
                if time_inA >= 2:
                    res = 'setwise coprime'
            now += base
    print(res)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_right

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)


P=[2,
 3,
 5,
 7,
 11,
 13,
 17,
 19,
 23,
 29,
 31,
 37,
 41,
 43,
 47,
 53,
 59,
 61,
 67,
 71,
 73,
 79,
 83,
 89,
 97,
 101,
 103,
 107,
 109,
 113,
 127,
 131,
 137,
 139,
 149,
 151,
 157,
 163,
 167,
 173,
 179,
 181,
 191,
 193,
 197,
 199,
 211,
 223,
 227,
 229,
 233,
 239,
 241,
 251,
 257,
 263,
 269,
 271,
 277,
 281,
 283,
 293,
 307,
 311,
 313,
 317,
 331,
 337,
 347,
 349,
 353,
 359,
 367,
 373,
 379,
 383,
 389,
 397,
 401,
 409,
 419,
 421,
 431,
 433,
 439,
 443,
 449,
 457,
 461,
 463,
 467,
 479,
 487,
 491,
 499,
 503,
 509,
 521,
 523,
 541,
 547,
 557,
 563,
 569,
 571,
 577,
 587,
 593,
 599,
 601,
 607,
 613,
 617,
 619,
 631,
 641,
 643,
 647,
 653,
 659,
 661,
 673,
 677,
 683,
 691,
 701,
 709,
 719,
 727,
 733,
 739,
 743,
 751,
 757,
 761,
 769,
 773,
 787,
 797,
 809,
 811,
 821,
 823,
 827,
 829,
 839,
 853,
 857,
 859,
 863,
 877,
 881,
 883,
 887,
 907,
 911,
 919,
 929,
 937,
 941,
 947,
 953,
 967,
 971,
 977,
 983,
 991,
 997]

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

check = [0]*1000
flag = 0
for a in A:
    for i in range(bisect_right(P, int(a**0.5))+1):
        if a%P[i] == 0 and flag == 0:
            if check[P[i]] == 1:
                flag = 1
            else:
                check[P[i]] = 1
    if flag:
        break

if gcd_list(A) > 1:
    print("not coprime")
elif flag:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Runtime Error

Solution code:
# Python3 program to find prime factorization 
# of a number n in O(Log n) time with 
# precomputation allowed. 
import math as mt 

MAXN = 100001

# stores smallest prime factor for 
# every number 


# Calculating SPF (Smallest Prime Factor) 
# for every number till MAXN. 
# Time Complexity : O(nloglogn) 
def sieve(): 
    spf = [0 for i in range(MAXN)] 
    spf[1] = 1
    for i in range(2, MAXN): 
		
		# marking smallest prime factor 
		# for every number to be itself. 
        spf[i] = i 

	# separately marking spf for 
	# every even number as 2 
    for i in range(4, MAXN, 2): 
        spf[i] = 2

    for i in range(3, mt.ceil(mt.sqrt(MAXN))): 
		
		# checking if i is prime 
        if (spf[i] == i): 
			
			# marking SPF for all numbers 
			# divisible by i 
            for j in range(i * i, MAXN, i): 
				
				# marking spf[j] if it is 
				# not previously marked 
                if (spf[j] == j): 
                    spf[j] = i 
    return spf

# A O(log n) function returning prime 
# factorization by dividing by smallest 
# prime factor at every step 
def getFactorization(x,spf): 
	ret = set()
	while (x != 1): 
		ret.add(spf[x]) 
		x = x // spf[x] 

	return ret 

# # Driver code 

# # precalculating Smallest Prime Factor 
# sieve() 
# x = 12246
# print("prime factorization for", x, ": ", 
# 								end = "") 

# # calling getFactorization function 
# p = getFactorization(x) 

# for i in range(len(p)): 
# 	print(p[i], end = " ") 

# This code is contributed 
# by Mohit kumar 29 


def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor,gcd
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    spf = sieve()
    primes = set()
    PairWise = True
    for a in A:
        p = getFactorization(a,spf)
        if len(p & primes) > 0:
            PairWise = False
            break
        primes |= p
    else:
        print('pairwise coprime')
        return

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

    


    
main()

Submission status: Runtime Error

Solution code:
import math as mt
n=int(input())
l=list(map(int,input().split()))
gd=l[0]
sv=[0]*(10**6+1)
for i in range(2,len(sv)+1):
  if not sv[i]:
    sv[i]=i
    for j in range(2*i,len(sv),i):
      sv[j]=i
an="not coprime"
for i in range(n):
      gd=mt.gcd(gd,l[i])
if gd!=1:
	print(an)
else:
    an="setwise coprime"
    pos=1
    vis=[0]*(10**6+2)
    for i in range(n):
      cr=l[i]
      while cr>1:
          dv=sv[cr]
          if vis[dv]:
            pos=0;break
          while cr%dv==0:
            cr//=dv
          vis[dv]=1
    if pos:
      an="pairwise coprime"
    print(an)

Submission status: Runtime Error

Solution code:
# https://cs.stackexchange.com/questions/93030/algorithm-for-checking-if-a-list-of-integers-is-pairwise-coprime

import math
n = int(input())
nums = list(map(int, input().split()))

gcd_ = nums[0]
for num in nums[1:]:
    gcd_ = math.gcd(gcd_, num)

if gcd_ >= 2:
    print('not coprime')
    exit()



def smallest_divisor(num):
    if num == 1:
        raise ValueError("error!")
    d = 2
    while d * d <= num:
        if num % d == 0:
            return d
        d += 1
    return num


prime_set = set()

for num in nums:
    soinsuu = set()
    
    warareru = num
    while True:
        divi = smallest_divisor(warareru)
        soinsuu.add(divi)
        warareru = warareru // divi
        if warareru == 1:
            break
    # print(soinsuu)
    if soinsuu & prime_set:
        print('setwise coprime')
        exit()
    else:
        prime_set |= soinsuu

print('pairwise coprime')

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def get_prime_factors(x):
    out = []
    while not x%2:
        out.append(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.append(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.append(x)
    return set(out)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    df = defaultdict(lambda : 0)
    for ai in a:
        primes = get_prime_factors(ai)
        for prime in primes:
            df[prime] += 1
    val = max(df.values())
    if val == 1:
        print("pairwise coprime")
    elif val == n:
        print("not coprime")
    else:
        print("setwise coprime")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import  numpy as np
n=int(input())
a= list(map(int, input().strip().split()))
a.sort()
b=np.gcd(a[0],a[1])
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
def prime_factorize(n):
    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)
    return a
B=prime_factorize(b)
l=len(B)
f=[0]*l
p=[]
for i in range(l):
    for j in range(n):
        if a[j]%B[i]>0:
            f[j]=1
            break
if f.count(0)==0:
    print("pairwise coprime")
else:
  print("not coprime")

Submission status: Runtime Error

Solution code:
def gcd(a, b): 
    if (a == 0 or b == 0): 
        return False
    if (a == b): 
        return a 
    if (a > b): 
        return gcd(a-b, b) 
    return gcd(a, b-a) 
def coprime(a, b) : 
    return (gcd(a, b) == 1) 
n=int(input())
lst=list(map(int,input().strip().split()))
flag=0 
for i in range(0,n):
    for j in range(i+1,n):
        a=coprime(lst[i],lst[j])
        if(a==False):
            flag=1 
            break 
if(flag==0):
    print("pairwise coprime")
else:
    g=gcd(lst[0],lst[1]) 
    for k in range(2,n):
        g=gcd(g,lst[k])
    if(g==1):
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Runtime Error

Solution code:
import math
m=int(input())
a,b,c=map(int,input().split())
if math.gcd(a,b)==math.gcd(a,c)==math.gcd(b,c)==1:
    print("pairwise coprime")
elif math.gcd(a,b)==math.gcd(a,c)==math.gcd(b,c)==2:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
n=int(input())
a=list(map(int, input().split()))
q=0
size=16

judge=[0]*(size)

for i in range(len(a)):
    num=a[i]
    for j in range(2,int(num**0.5)+1):
        if num%j==0:
            if judge[j-1]==-1:
                q=1
            elif judge[num//j-1]==-1:
                q=1
            else:
                judge[j-1]=-1
                judge[num//j-1]=-1

    if judge[num-1]==-1:
        q=1
    else:
        judge[num-1]=-1

if reduce(math.gcd,a)==1:
    if q!=1:
        q=2
else:
    q=0

if q==2:
    print('pairwise coprime')

elif q==1:
    print('setwise coprime')
        
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import numpy as np
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

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)

    if temp!=1:
        arr.append(temp)

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

    return list(set(arr))

N = i()
A = l()
li = []
num = [0]*(10**6+1)
for i in range(N):
    for j in factorization(A[i]):
        if j not in li:
            li.append(j)
        else:
            num[j] += 1
if max(num) == 0:
    print('pairwise coprime')
elif max(num) == N-1:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
tmp = [False if i == 0 or i == 1 else True for i in range(1000)]
p, s = True, True

for i in range(2, int(max(A) ** 0.5) + 1):
    t = 0
    if not tmp[i]:
        continue

    for j in range(N):
        if A[j] % i == 0:
            t += 1
            A[j] //= i

    for j in range(i * 2, 1000, i):
        tmp[j] = False

    if t >= 2:
        p = False

    if t == N:
        s = False
        break

print('pairwise coprime' if p else 'setwise coprime' if s else 'not coprime')

Submission status: Runtime Error

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

def func(m):
    for i in range(2,int(m**0.5)+2):
        if m%i==0:
            mapa[i]+=1
            while m%i==0:
                m//=i
        else:
            continue
    if m>1:
        mapa[m]+=1

for ai in a:
    func(ai)

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

Submission status: Runtime Error

Solution code:
import sys
import math

if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    check_pairwise()
    check_set()
    return


def check_pairwise():
    active = set()
    for i in range(0, n):
        pp = getprimes(a[i])
        for p in pp:
            if p in active:
                return
            else:
                active.add(p)
    print("pairwise coprime")
    exit()



def check_set():
    active = getprimes(a[0])
    for i in range(1, n):
        if not a[i] % a[i-1] == 0:
            for act in active:
                if not a[i] % act == 0:
                    active.remove(act)
                    if not active:
                        print("setwise coprime")
                        exit()
    print("not coprime")
    exit()




def getprimes(num):
    if num in primes:
        return set([num])
    pp = set()
    for i in range(int(math.sqrt(num)+2)):
        if i in primes:
            pp.add(i)
    return pp




def n_primes(n):
    nums = list(range(0, n + 1))
    primes = []
    for i in range(2, n + 1):
        num = nums[i]
        if num != 0:
            primes.append(num)
            for i in range(0, n // num + 1):
                nums[i * num] = 0
    return primes


n = RN()
a = sorted(RA())
primes = set(n_primes(10 ** 6))
solve()

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
n=int(input())
a=list(map(int, input().split()))
q=0
size=16

judge=[0]*(size)

for i in range(len(a)):
    num=a[i]
    print(i)
    for j in range(2,int(num**0.5)+1):
        if num%j==0:
            if judge[j-1]==-1:
                q=1
            elif judge[num//j-1]==-1:
                q=1
            else:
                judge[j-1]=-1
                judge[num//j-1]=-1

    if judge[num-1]==-1:
        q=1
    else:
        judge[num-1]=-1
    print(judge)

if reduce(math.gcd,a)==1:
    if q!=1:
        q=2
else:
    q=0

print(a,reduce(math.gcd,a))


if q==2:
    print('pairwise coprime')

elif q==1:
    print('setwise coprime')
        
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
def pf(N):
    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)
    return A

n = int(input())
a = list(map(int, input().split()))
b = [0]*1001
for i in range(n):
    x = pf(a[i])
    x = list(set(x))
    for j in x:
        b[j] += 1
#print(b)
tnp = 0
for i in range(1001):
    if (b[i]>1):
        tnp += 1
        break
if (tnp==0):
    print("pairwise coprime")
    exit()
        
for i in range(1001):
    if (b[i]==n):
        print("not coprime")
        exit()
print("setwise coprime")

Submission status: Runtime Error

Solution code:
import math as mt
n=int(input())
l=list(map(int,input().split()))
gd=l[0]
sv=[0]*(10**6+1)
for i in range(2,int(len(sv)**0.5)+1):
  if not sv[i]:
    sv[i]=i
    for j in range(2*i,len(sv),i):
      sv[j]=i
an="not coprime"
for i in range(n):
      gd=mt.gcd(gd,l[i])
if gd!=1:
	print(an)
else:
    an="setwise coprime"
    pos=1
    vis=[0]*(10**6+2)
    for i in range(n):
      cr=l[i]
      while cr>1:
          dv=sv[cr]
          if vis[dv]:
            pos=0;break
          while cr%dv==0:
            cr//=dv
          vis[dv]=1
    if pos:
      an="pairwise coprime"
    print(an)

Submission status: Runtime Error

Solution code:
#素因数分解
def Prime_Factorization(N):
    if N<0:
        R=[[-1,1]]
    else:
        R=[]

    N=abs(N)
    k=2
    while k*k<=N:
        if N%k==0:
            C=0
            while N%k==0:
                C+=1
                N//=k
            R.append([k,C])
        k+=1

    if N!=1:
        R.append([N,1])
    if not R:
        R.append([N,1])

    return R
#================================================
from math import gcd
N=int(input())
A=list(map(int,input().split()))

#Pairwise?
P=set()
F=True
for a in A:
    K=Prime_Factorization(a)
    for (p,_) in K:
        if p in P:
            F=False
            break
        else:
            P.add(p)

    if not F:
        break

if F:
    print("pairwise coprime")
    exit()

#Setwise?
g=A[0]
for a in A:
    g=gcd(g,a)

if g==1:
    print(1/0)
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import sympy

Submission status: Runtime Error

Solution code:
#素因数分解
def Prime_Factorization(N):
    if N<0:
        R=[[-1,1]]
    else:
        R=[]

    N=abs(N)
    k=2
    while k*k<=N:
        if N%k==0:
            C=0
            while N%k==0:
                C+=1
                N//=k
            R.append([k,C])
        k+=1

    if N!=1:
        R.append([N,1])
    if not R:
        R.append([N,1])

    return R
#================================================
from math import gcd
N=int(input())
A=list(map(int,input().split()))

#Pairwise?
P=set()
F=True
for a in A:
    K=Prime_Factorization(a)
    for (p,_) in K:
        if p in P:
            F=False
            break
        else:
            P.add(p)

    if not F:
        break

if F:
    print(1/0)
    print("pairwise coprime")
    exit()

#Setwise?
g=A[0]
for a in A:
    g=gcd(g,a)
    if g==1:
        break

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

Submission status: Runtime Error

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

d = {}
flag = False
for i in a:
    f = sympy.factorint(i)
    for k in f.keys():
        try:
            if d[k] >= 1:
                d[k] += 1
                flag = True
        except:
            d[k] = 1
if not flag:
    print("pairwise coprime")
else:
    flag = False
    for i in d.values():
        if i == len(a):
            print("not coprime")
            flag = True
            break
    if not flag:
        print("setwise coprime")

Submission status: Runtime Error

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

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


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


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

    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()

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

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    for a in A:
        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a)
        PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

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



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math

def linked_merge_sort(l): #マージソート
    if len(l) == 1:
        return
    q, r = divmod(len(l), 2)
    left = [l.pop() for _ in range(q)]
    right = [l.pop() for _ in range(q + r)]
    
    linked_merge_sort(left)
    linked_merge_sort(right)
    
    left.reverse()
    right.reverse()
    while left and right:
        if left[-1] <= right[-1]:
            l.append(left.pop())
        else:
            l.append(right.pop())
    while left:
        l.append(left.pop())
    while right:
        l.append(right.pop())
    return

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

linked_merge_sort(a)

gx=list()
if (n-1)%2==0:
    npt=(n*(n-1))//2
else:
    npt=(((n+1)*n)//2)-n

for i in range(n):
    j=1
    while i+j<n:
        if math.gcd(a[i],a[i+j])!=1:
            gx.append(math.gcd(a[i],a[i+j]))
        j+=1

y=gx[0]
jud=1

for i in gx:
    if i !=y:
        jud=0
        break

if len(gx)==0:
    print("pairwise coprime")
elif len(gx)==npt and jud==0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

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

for a, b in itertools.combinations(A, 2):
    if math.gcd(a, b) != 1:
        if functools.reduce(math.gcd, A) == 1:
            print('setwise coprime')
        else:
            print('not coprime')
        break
else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
import java.io.*;
import java.util.*;
// i want to become the best
class Main{
	public static void main(String[] args) throws Exception{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(reader.readLine());
		long[] list = Arrays.stream(reader.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
	    //System.out.println(list[1]*list[2]>=list[0]?"Yes":"No");
		long lcm = list[0];
		long hcf = list[0];
		long prod = list[0];
	}
	public static lcm
}
class pair implements Comparable<pair>{
		long a = 0;
		int b = 0;
		public pair(long a,int b){
			this.a = a;
			this.b = b;
		}
		@Override
		public int compareTo(pair p){
			if(this.a == p.a) return -(Integer.compare(this.b,p.b));
			else return -(Long.compare(this.a,p.a));
		}
		@Override
		public String toString(){
			return a+" "+b;
		}
	}

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    primes = []
    isprime = [True for i in range(1001)]
    for i in range(2, 1001):
        if isprime[i]:
            primes.append(i)
            for j in range(i * i, 1001, i):
                isprime[j] = False
    x = a[0]
    f = True

    cnt = [0 for i in range(1000001)]
    for val in a:
        x = gcd(x, val)
        i = 0
        while primes[i] ** 2 <= val:
            if val % primes[i] == 0:
                cnt[primes[i]] += 1
                while val % primes[i] == 0:
                    val //= primes[i]
            i += 1
        if val > 1:
            cnt[val] += 1
    for i in range(2, n + 1):
        if cnt[i] > 1:
            f = False
            break
    if f:
        print('pairwise coprime')
    elif x == 1:
        print('setwise coprime')
    else:
        print('not coprime')



t = 1
while t > 0:
    solve()
    t -= 1

Submission status: Runtime Error

Solution code:

max_val = int(1e+6+1)
def make_kago(x):
    kago = [0 for _ in range(x+1)]
    sosuu = []
    for i in range(2,x+1):
        if kago[i] != 0:
            continue
        sosuu.append(i)
        for j in range(i, x+1, i):
            if kago[j] == 0:
                kago[j] = i
    return kago, sosuu

kago, sosuu = make_kago(max_val)

def prime_factorization(x):
    if x==0 or x==1:
        return None
    soinsuu = []
    while x!=1:
        soinsuu.append(kago[int(x)])
        x = x/kago[int(x)]
    
    soinsuu_dict = dict()
    for i in range(len(soinsuu)):
        if soinsuu[i] not in soinsuu_dict:
            soinsuu_dict[soinsuu[i]] = 1
        else:
            soinsuu_dict[soinsuu[i]]+=1
    return soinsuu_dict

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

exists = [0 for _ in range(int(1e+6+1))]

complete_ok = True
for i, A in enumerate(As):
    soinsuu_dict = prime_factorization(A)
    keys = list(soinsuu_dict.keys())
    for key in keys:
        if exists[key] != 0:
            complete_ok = False
        exists[key] += 1

part_ok = False
for i in range(len(exists)):
    if exists[i] == len(As):
        part_ok = True

if complete_ok == True:
    print("pairwise coprime")
elif part_ok == False:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import sys
import math

if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    check_pairwise()
    check_set()
    return


def check_pairwise():
    active = set()
    for i in range(0, n):
        pp = getprimes(a[i])
        for p in pp:
            if p in active:
                return
            else:
                active.add(p)
    print("pairwise coprime")
    exit()



def check_set():
    active = getprimes(a[0])
    for i in range(1, n):
        if not a[i] % a[i-1] == 0:
            for act in active:
                if not a[i] % act == 0:
                    active.remove(act)
                    if not active:
                        print("setwise coprime")
                        exit()
    print("not coprime")
    exit()




def getprimes(num):
    if num in primes:
        return set([num])
    pp = set()
    for i in range(int(math.sqrt(num+5))):
        if i in primes:
            pp.add(i)
    return pp




def n_primes(n):
    nums = list(range(0, n + 1))
    primes = []
    for i in range(2, n + 1):
        num = nums[i]
        if num != 0:
            primes.append(num)
            for i in range(0, n // num + 1):
                nums[i * num] = 0
    return primes


n = RN()
a = sorted(RA())
primes = set(n_primes(10 ** 6))
solve()

Submission status: Runtime Error

Solution code:
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
a.sort()
g=a[0]
d=defaultdict(int)
for i in a:
    g=math.gcd(g,i)
    d[i]+=1
if g>1:
    print("not coprime")
p=[0]*(a[-1]+1)
ch=0
for i in range (2,a[-1]+1):
    if p[i]==1:
        continue
    p[i]=1
    ans=0
    for j in range (i,a[-1]+1,i):
        ans+=d[j]
    if ans>1:
        ch=1
        break
if ch==1:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import math

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

def gcd_n(xs):
    if len(xs) == 1:
        return xs[0]
    return math.gcd(xs[0], gcd_n(xs[1:]))


if gcd_n(A) != 1:
    print("not coprime")
    exit()

for i in range(N):
    for j in range(i + 1, N):
        if math.gcd(A[i], A[j]) != 1:
            print("setwise coprime")
            exit()
print("pairwise coprime")

Submission status: Runtime Error

Solution code:
def resolve():
    n=int(input())
    a = list(map(int, input().split()))
    seki=1
    import math
    from functools import reduce

    def gcd(*numbers):
        return reduce(math.gcd, numbers)

    for i in a:
      seki*=i

    c=seki
    ch=0

    for i in range(n-1):
        seki=int(seki/a[i])
        gc=gcd(a[i], seki)
        if gc!=1:
            c=gcd(c,gc)
            ch+=1

    if ch==0:
        print("pairwise coprime")
    elif c==1:
        print("setwise coprime")
    else:
        print("not coprime")
resolve()