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:
N = int(input())
A = list(map(int, input().split()))


# number_to_prime[i]: i の最小の素因数, iが素数ならば0
number_to_prime = [0] * (10**6 + 1)

# preprocess
for i in range(2, 10**6+1):
    if not number_to_prime[i]:
        j = 1
        while j*i <= 10**6:
            number_to_prime[j*i] = i
            j += 1

def is_pair_copr(A):
    U = 1 << 20
    div_p = np.arange(U)
    for p in range(2, U):
        if div_p[p] != p:
            continue
        div_p[p::p] = p
    used = np.zeros(U, np.bool_)
 
    for x in A:
        while x > 1:
            p = div_p[x]
            while x % p == 0:
                x //= p
            if used[p]:
                return False
            used[p] = True
    return True

def is_pairwise():
    used_primes = set()
    pairwise_flag = 1
    for a in A:
        curr_primes = set()
        while a > 1:
            prime = number_to_prime[a]
            curr_primes.add(prime)
            a //= prime
        if used_primes & curr_primes:
            pairwise_flag = 0
            break
        else:
            used_primes = used_primes | curr_primes
    return pairwise_flag

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pair_copr(A):
    print("pairwise coprime")
elif is_setwise(*A):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

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


# number_to_prime[i]: i の最小の素因数, iが素数ならば0
number_to_prime = [0] * (10**6 + 1)

# preprocess
for i in range(2, 10**6+1):
    if not number_to_prime[i]:
        j = 2
        while j*i <= 10**6:
            number_to_prime[j*i] = i
            j += 1


def is_pairwise():
    used_primes = set()
    pairwise_flag = 1
    for a in A:
        if a == 1:
            continue
        curr_primes = set()
        while number_to_prime[a]:
            prime = number_to_prime[a]
            curr_primes.add(prime)
            a //= prime
        if used_primes & (curr_primes | set([a])):
            pairwise_flag = 0
            break
        else:
            used_primes = used_primes | (curr_primes | set([a]))
    return pairwise_flag

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pairwise():
    print("pairwise coprime")
elif is_setwise(*A):
    0/0
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

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


# number_to_prime[i]: i の最小の素因数, iが素数ならば0
number_to_prime = [0] * (10**6 + 1)

# preprocess
for i in range(2, 10**6+1):
    if not number_to_prime[i]:
        j = 2
        while j*i <= 10**6:
            number_to_prime[j*i] = i
            j += 1


def is_pairwise():
    used_primes = set()
    pairwise_flag = 1
    for a in A:
        if a == 1:
            continue
        curr_primes = set()
        while number_to_prime[a]:
            prime = number_to_prime[a]
            curr_primes.add(prime)
            a //= prime
        curr_primes.add([a])
        if used_primes & curr_primes:
            pairwise_flag = 0
            break
        else:
            used_primes = used_primes | curr_primes
    return pairwise_flag

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pairwise():
    print("pairwise coprime")
elif is_setwise(*A):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

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

from functools import lru_cache
@lru_cache(None)

def gcd(x,y):
    if y>x:
        x,y=y,x
    if y==0:
        return x
    else:
        return gcd(y,x-y)

pairwise=True
setwise=True
gcds=[]
for i in range(N):
    for j in range(i+1,N):
        g=gcd(A[i],A[j])
        if g in gcds:
            setwise=False
        else:
            gcds.append(g)
        if g > 1:
            pairwise=False
        if pairwise==False and setwise==False:
            break
    if pairwise==False and setwise==False:
        break
        

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

Submission status: Runtime Error

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

from functools import lru_cache
@lru_cache(None)

def gcd(x,y):
    if y>x:
        x,y=y,x
    if y==0:
        return x
    else:
        return gcd(y,x-y)

pairwise=True
setwise=True
gcds=[]
for i in range(N):
    for j in range(i+1,N):
        g=gcd(A[i],A[j])
        print(i,j)
        print("gcd:",g)
        if g in gcds:
            setwise=False
        else:
            gcds.append(g)
        print(gcds)
        if g > 1:
            pairwise=False
        if pairwise==False and setwise==False:
            break
    if pairwise==False and setwise==False:
        break
        

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

Submission status: Runtime Error

Solution code:
import numpy as np
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = np.sqrt(num)

    for serial in range(3, num, 2):
    
        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            if bool_list[s]:
                input_list[s] = serial
                bool_list[s] = False

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

D = getD(max(A))

flag = True

d_set_all = set()
for i, a in enumerate(A):
    d_set = set()
    while a > 1:
        d_set.add(D[a])
        a = a // D[a]

    if len(d_set_all & d_set) > 0:
        flag = False
        break
    d_set_all = d_set | d_set_all

if flag:
    print('pairwise coprime')
    exit()

if reduce(math.gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
import numpy as np

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = np.sqrt(num)

    for serial in range(3, num, 2):
    
        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            if bool_list[s]:
                input_list[s] = serial
                bool_list[s] = False

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

D = getD(max(A))
record = np.zeros((N, max(A)+1), np.uint8)

for i, a in enumerate(A):
    while a > 1:
        record[i, D[a]] = 1
        a = a // D[a]

flag = True

for i in range(2, max(A) + 1):
    s = np.sum(record[:, i])
    if s == 1:
        continue
    elif s == N:
        print('not coprime')
        exit()
    if s > 1:
        flag = False

if flag:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Runtime Error

Solution code:
import numpy as np

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = np.sqrt(num)

    for serial in range(3, num, 2):
    
        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            if bool_list[s]:
                input_list[s] = serial
                bool_list[s] = False

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

D = getD(max(A))
record = np.zeros((N, max(A)+1))

for i, a in enumerate(A):
    while a > 1:
        record[i, D[a]] = 1
        a = a // D[a]

#print(record)

flag = True

for i in range(max(A) + 1):
    s = np.sum(record[:, i])
    if s == 1:
        continue
    elif s == N:
        print('not coprime')
        exit()
    if s > 1:
        flag = False

if flag:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Runtime Error

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    
    pr = [0]*(max(a)+1)
    for num in a:
        pr[num] += 1
    for i in range(2, max(a)+1):
        count = sum(pr[i::i])
        if count == N:
            print("not coprime")
        elif count > 1:
            flag = False
    if flag:
        print("pairwise coprime")
    else:
        print("setwise coprime")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():

        import os
    import sys
    from io import BytesIO, IOBase
    
    BUFSIZE = 8192
    
    
    class FastIO(IOBase):
        newlines = 0
    
        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = "x" in file.mode or "r" not in file.mode
            self.write = self.buffer.write if self.writable else None
    
        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines = 0
            return self.buffer.read()
    
        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b"\n") + (not b)
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines -= 1
            return self.buffer.readline()
    
        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                self.buffer.truncate(0), self.buffer.seek(0)
    
    
    class IOWrapper(IOBase):
        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode("ascii"))
            self.read = lambda: self.buffer.read().decode("ascii")
            self.readline = lambda: self.buffer.readline().decode("ascii")
    
    
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
    mod = 10**9 + 7

    import sys
    input = lambda: sys.stdin.readline().rstrip("\r\n")

    from math import gcd

    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

    n = int(input())
    a = [int(x) for x in input().split()]

    primes = set()

    flag = 1

    for i in a:
        prime_factors = set(prime_factorize(i))
        for j in prime_factors:
            if j in primes:
                flag = 0
            else:
                primes.add(j)


    if flag:
        print('pairwise coprime')
        sys.exit()
                
    
    import math
    from functools import reduce
    
    def gcd(*numbers):
        return abs(reduce(math.gcd, numbers))
    
    if gcd(*a) == 1:
        print('setwise coprime')
    else:
        print('not coprime')

main()

Submission status: Runtime Error

Solution code:
import math
N = int(input())
num = list(map(int, input().split()))

MAXX = 10**6 + 1
MAXZ = int(math.sqrt(MAXX)+1)
furui = [[] for _ in range(MAXZ)]

furui[1].append(1)
count = [0]*MAXX
for i in range(2, MAXZ):
    if len(furui[i]) == 0:
        for k in range(i, MAXZ, i):
            furui[k].append(i)

setwise = True
pairwise = True
for i in range(N):
    if not setwise and not pairwise: break
    for fu in furui[num[i]]:
        count[fu] += 1
        if count[fu] >= N:
            setwise = False
            pairwise = False
            break
        elif count[fu] > 1:
            pairwise = False

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

Submission status: Runtime Error

Solution code:
from math import sqrt
N = int(input())
num = list(map(int, input().split()))

MAXX = 10**6 + 1
MAXZ = int(sqrt(MAXX)+1)
furui = [[] for _ in range(MAXZ)]

furui[1].append(1)
count = [0]*MAXX
for i in range(2, MAXZ):
    if len(furui[i]) == 0:
        for k in range(i, MAXZ, i):
            furui[k].append(i)

setwise = True
pairwise = True
for i in range(N):
    if not setwise and not pairwise: break
    for fu in furui[num[i]]:
        count[fu] += 1
        if count[fu] >= N:
            setwise = False
            pairwise = False
            break
        elif count[fu] > 1:
            pairwise = False

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

from math import gcd
n = int(input())
a = list( map(int, input().split()))


g = 0
for aa in a:
    g = gcd(g,aa)
if g > 1:
    print('not coprime')
    exit()

def eratosthenes(limit):
    import math
    if not isinstance(limit, int):
        raise TypeError('n is int type.')
    if limit < 2:
        raise ValueError('n is more than 2')
    prime = []
    sqrt_limit = math.sqrt(limit)
    prime_numbers_list = [i + 1 for i in range(1, limit)]
    while True:
        p = prime_numbers_list[0]
        if sqrt_limit <= p:
            return prime + prime_numbers_list
        prime.append(p)
        prime_numbers_list = [e for e in prime_numbers_list if e % p != 0]
    return prime_numbers_list


g = 0
for aa in a:
    g = gcd(g,aa)
if g > 1:
    print('not coprime')
    exit()

seta = set(a)
if seta == {1}:
    print('pairwise coprime')
    exit()

prime_numbers_list = eratosthenes(a[-1])

insu_set = set()
for aa in a:
    for prime in prime_numbers_list:
        tmp = set()
        if aa % prime ==0:
            tmp.add(prime)
            aa //= prime
        if tmp & insu_set:
            print('setwise coprime')
            exit()
        else:
            insu_set = insu_set | tmp

print('pairwise coprime')

Submission status: Runtime Error

Solution code:
from math import gcd
MAX = 10**6

sieve = [i for i in range(MAX+1)]

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


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

for a in A:
    tmp = set()
    b = a
    while b != 1:
        tmp.add(sieve[b])
        b //= sieve[b]
    pf.append(tmp)


soin = [0] * (10 ** 6 + 1)
for f in pf:
    for n in f:
        soin[n] += 1

if max(soin[2:]) <= 1:
    print('pairwise coprime')
    exit()


setwise = a[0]

for a in A:
    setwise = gcd(setwise, a)
    
if setwise == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
import numpy as np
MAX = 10**6

sieve = [i for i in range(MAX+1)]

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


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

for a in A:
    tmp = set()
    b = a
    while b != 1:
        tmp.add(sieve[b])
        b //= sieve[b]
    pf.append(tmp)


soin = [0] * (10 ** 6 + 1)
for f in pf:
    for n in f:
        soin[n] += 1

if max(soin[2:]) <= 1:
    print('pairwise coprime')
    exit()

flag = np.gcd.reduce(A)

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

Submission status: Runtime Error

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

li = [0] * 10**3

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

for i in a:
    li2 = factorization(i)
    for x,y in li2:
        li[x] += 1

flag = True
flag2 = True

for i in li:
    if i == n:
        flag2 = False
    elif i >= 2:
        flag = False

if not flag2:
    print('not coprime')
elif not flag:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:

def gen_factorization(N):
    tables=[-1]*(N+1)
    for i in range(2,N+1):
        if tables[i]!=-1:continue
        tmp=i
        while tmp<=N:
            tables[tmp]=i
            tmp+=i
    def fuctorization(n):
        if n==1:return 1
        elif n<0:n=abs(n)
        if n>N:return {}
        ans={}
        while n!=1:
            tmp=tables[n]
            #debug print
            #print(tmp,n)
            ans.setdefault(tmp,0)
            ans[tmp]+=1
            n//=tmp
        return ans
    return fuctorization

N=int(input())
f=gen_factorization(10**6+10)
A=list(map(int,input().split()))
primes={}
for i in A:
  if i==1:continue
  d=f(i)
  for j in d:
    primes.setdefault(j,0)
    primes[j]+=1

ansMax=max(primes.values())
ansMin=min(primes.values())

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

Submission status: Runtime Error

Solution code:

def gen_factorization(N):
    tables=[-1]*(N+1)
    for i in range(2,N+1):
        if tables[i]!=-1:continue
        tmp=i
        while tmp<=N:
            tables[tmp]=i
            tmp+=i
    def fuctorization(n):
        if n==1:return 1
        elif n<0:n=abs(n)
        elif n>N:return -1
        ans={}
        while n!=1:
            tmp=tables[n]
            #debug print
            #print(tmp,n)
            ans.setdefault(tmp,0)
            ans[tmp]+=1
            n//=tmp
        return ans
    return fuctorization

N=int(input())
f=gen_factorization(10**6+10)
A=list(map(int,input().split()))
primes={}
for i in A:
  if i==1:continue
  d=f(i)
  for j in d:
    primes.setdefault(j,0)
    primes[j]+=1

ansMax=max(primes.values())
ansMin=min(primes.values())

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

Submission status: Runtime Error

Solution code:

def gen_factorization(N):
    tables=[-1]*(N+1)
    for i in range(2,N+1):
        if tables[i]!=-1:continue
        tmp=i
        while tmp<=N:
            tables[tmp]=i
            tmp+=i
    def fuctorization(n):
        if n==1:return 1
        elif n<0:n=abs(n)
        elif n>N:return -1
        ans={}
        while n!=1:
            tmp=tables[n]
            #debug print
            #print(tmp,n)
            ans.setdefault(tmp,0)
            ans[tmp]+=1
            n//=tmp
        return ans
    return fuctorization

N=int(input())
f=gen_factorization(10**6)
A=list(map(int,input().split()))
primes={}
for i in A:
  if i==1:continue
  d=f(i)
  for j in d:
    primes.setdefault(j,0)
    primes[j]+=1

ansMax=max(primes.values())
ansMin=min(primes.values())

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

Submission status: Runtime Error

Solution code:
isPair=True
isSet=True

def gen_factorization(N):
    tables=[-1]*(N+1)
    for i in range(2,N):
        if tables[i]!=-1:continue
        tmp=i
        while tmp<=N:
            tables[tmp]=i
            tmp+=i
    def fuctorization(n):
        if n==1:return 1
        elif n<0:n=abs(n)
        elif n>N:return -1
        ans={}
        while n!=1:
            tmp=tables[n]
            #debug print
            #print(tmp,n)
            ans.setdefault(tmp,0)
            ans[tmp]+=1
            n//=tmp
        return ans
    return fuctorization

N=int(input())
f=gen_factorization(10**6)
A=list(map(int,input().split()))
primes={}
for i in A:
  d=f(i)
  for j in d:
    primes.setdefault(j,0)
    primes[j]+=1

ansMax=max(primes.values())
ansMin=min(primes.values())

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

Submission status: Runtime Error

Solution code:
isPair=True
isSet=True

def gen_factorization(N):
    tables=[-1]*(N+1)
    for i in range(2,N):
        if tables[i]!=-1:continue
        tmp=i
        while tmp<=N:
            tables[tmp]=i
            tmp+=i
    def fuctorization(n):
        if n==1:return 1
        elif n<0:n=abs(n)
        elif n>N:return -1
        ans={}
        while n!=1:
            tmp=tables[n]
            #debug print
            #print(tmp,n)
            ans.setdefault(tmp,0)
            ans[tmp]+=1
            n//=tmp
        return ans
    return fuctorization

N=int(input())
f=gen_factorization(10**6)
A=list(map(int,input().split()))
primes={}
for i in A:
  print(i)
  d=f(i)
  for j in d:
    primes.setdefault(j,0)
    primes[j]+=1
ansMax=max(primes.values())
ansMin=min(primes.values())
print(primes)
if ansMax==1:
  print('pairwise coprime')
elif ansMax==N:
  print('not coprime')
else:
  print('setwise coprime')

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
soin = [0]*(10**5+1)
if a.count(1)==n:
    print("pairwise coprime")
    exit()

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

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

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

    return arr


if len(a)>78498:
    ans=a[0]
    for i in a:
        ans=math.gcd(ans,i)
    if ans==1:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    for i in a:
        for num in factorization(i):
            soin[num]+=1
    if max(soin)==1:
        print("pairwise coprime")
    elif max(soin)==n and 1 not in a:
        print("not coprime")
    else:print("setwise coprime")

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
soin = [0]*(10**5+1)
if sum(a)==n:
    print("pairwise coprime")
    exit()

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

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

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

    return arr


if len(a)>78498:
    ans=a[0]
    for i in a:
        ans=math.gcd(ans,i)
    if ans==1:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    for i in a:
        for num in factorization(i):
            soin[num]+=1
    if max(soin)==1:
        print("pairwise coprime")
    elif max(soin)==n and 1 not in a:
        print("not coprime")
    else:print("setwise coprime")

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
soin = [0]*(10**5+1)
if sum(a)==n:
    print("pairwise coprime")
    exit()

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

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

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

    return arr


if len(a)>78498:
    ans=a[0]
    for i in a:
        ans=math.gcd(ans,i)
    if ans==1:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    for i in a:
        for num in factorization(i):
            soin[num]+=1
    if max(soin)==1:
        print("pairwise coprime")
    elif max(soin)==n:
        print("not coprime")
    else:print("setwise coprime")

Submission status: Runtime Error

Solution code:
    N = int(input())
    Alist = list(map(int,input().split()))
     
    def GCD(a,b):
        if a>b:
            a = a%b
            if a == 0:
                return(b)
            else:
                return GCD(a,b)
        else:
            b = b%a
            if b == 0:
                return(a)
            else:
                return GCD(a,b)
     
    isPC = True
    isSC = False
    kouyaku = 1
    skipindex = 0
     
    for i,x in enumerate(Alist):
        for y in Alist[:i]:
            if GCD(x,y) != 1:
                isPC = False
                kouyaku = GCD(x,y)
                break
        else:
            continue
        break
     
    if kouyaku > 1:
        for x in Alist:
            kouyaku = GCD(x,kouyaku)
            if kouyaku == 1:
                isSC = True
                break
     
    if isPC:
        print('pairwise coprime')
    elif isSC:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
soin = [0]*(10**5+1)


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

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

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

    return arr


if len(a)>78498:
    ans=a[0]
    for i in a:
        ans=math.gcd(ans,i)
    if ans==1:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    for i in a:
        for num in factorization(i):
            soin[num]+=1
    if max(soin)==1:
        print("pairwise coprime")
    elif max(soin)==n:
        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()))
soin = [0]*(10**5+1)


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

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

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

    return arr


if len(a)>78498:
    ans=a[0]
    for i in a:
        ans=math.gcd(ans,i)
    if ans==1:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    for i in a:
        for num in factorization(i):
            soin[num]+=1
    if max(soin)==1:
        print("pairwise coprime")
    elif max(soin)==n:
        print("not coprime")
    else:print("setwise coprime")

Submission status: Runtime Error

Solution code:
# -*- coding:utf-8 -*-

def prime_factor(n):
    """因数分解して因数のみを取得する"""
    if n <= 1: return {}

    ans = set()
    i = 2
    while i*i <= n:
        while n%i == 0:
            if not i in ans:
                ans.add(i)
            n //= i
        i += 1

    if n != 1:
        ans.add(n)
    return ans

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

    pf_sets = []
    for a in As:
        pf_set = prime_factor(a)
        pf_sets.append(pf_set)


    # pairwiseにできるかを調べる
    is_pairwise = True
    a_set = set()
    for pf_set in pf_sets:
        if len(a_set & pf_set) != 0:
            # すでに因数が存在するならpairwiseになれない
            is_pairwise = False
            break
        a_set |= pf_set

    if is_pairwise:
        print("pairwise coprime")
        return

    # setwiseにできるかを調べる
    is_setwise = False
    base_pf_set = pf_sets[0]
    for pf_set in pf_sets[1:]:
        base_pf_set &= pf_set

        if len(base_pf_set) == 0:
            is_setwise = True
            break

    if is_setwise:
        print("setwise coprime")
        return

    print("not coprime")

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
# -*- coding:utf-8 -*-

def prime_factor(n):
    """因数分解して因数のみを取得する"""
    if n <= 1: return {}

    ans = set()
    i = 2
    while i*i <= n:
        while n%i == 0:
            if not i in ans:
                ans.add(i)
            n //= i
        i += 1

    if n != 1:
        ans.add(n)
    return ans

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

    # pairwiseにできるかを調べる
    is_pairwise = True
    a_set = set()
    pf_sets = []
    for a in As:
        pf_set = prime_factor(a)
        pf_sets.append(pf_set)
        if not is_pairwise: continue

        for key in pf_set:
            if key in a_set:
                # すでにkeyが存在するならpairwiseになれない
                is_pairwise = False
                break
            a_set.add(key)
            if not is_pairwise: break

    if is_pairwise:
        print("pairwise coprime")
        return

    # setwiseにできるかを調べる
    is_setwise = False
    base_pf_set = pf_sets[0]
    for pf_set in pf_sets[1:]:
        base_pf_set &= pf_set

        if len(base_pf_set) == 0:
            is_setwise = True
            break

    if is_setwise:
        print("setwise coprime")
        return

    print("not coprime")

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = map(int, input().split())

is_prime = [1] * 1001
is_prime[0] = 0
is_prime[1] = 0
for current in range(2, 1001):
  if is_prime[current]:
    for i in range(2, 1 + 1000//current):
      is_prime[i*current] = 0
primes = []
for i in range(2, 1001):
  if is_prime[i]:
    primes.append(i)

def factorize(n):
  factors = set()
  for p in primes:
    if n % p == 0:
      factors.add(p)
      while n % p == 0:
        n //= p
    if p * p > n:
      if n > 1:
        factors.add(n)
      break
  return factors

p_coprime = True
common_factors = None
appeared_factors = None
for a in A:
  f = factorize(a)
  #print(a, f, p_coprime, common_factors, appeared_factors) 
  if common_factors == None:
    common_factors = f
    appeared_factors = f
  else:
    if appeared_factors & f:
      p_coprime = False
    common_factors = common_factors & f
    appeared_factors = appeared_factors | f
  print(a, f, p_coprime, common_factors, appeared_factors) 
if p_coprime:
  print('pairwise coprime')
elif not common_factors:
  print('setwise coprime')
else:
  print('not coprime')