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: Wrong Answer

Solution code:
import math
from collections import deque
N=int(input())
A=[int(x) for x in input().split()]
gcd=A[0]
for i in range(1,N):
    gcd=math.gcd(gcd,A[i])
if gcd!=1:
    print("not coprime")
else:
    flag=1
    maxA=max(A)
    minA=min(A)


    primeornot=[1]*(maxA+1)
    A=sorted(A)
    deA=deque(A)
    while(len(deA)!=0):
        now=deA.popleft()
        if primeornot[now]==0:
            flag=0
            break
        index=now
        while(index<maxA+1):
            primeornot[index]=0
            index+=now

    if flag==0:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Wrong Answer

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)

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

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

    return arr

def main():
    pairwise = True
    setwise = True
    reg = set(factorization(A[0]))
    common = set(reg)
    for a in A[1:]:
        new_reg = []
        for r in reg:
            if a % r == 0:
                pairwise = False
                if not setwise:
                    return 'not coprime'
                a = a // r
                new_reg.append(r)
        new_reg.extend(factorization(a))
        new_reg = set(new_reg)
        reg = reg | new_reg
        common = common & new_reg
    if pairwise:
        return 'pairwise coprime'
    elif len(common) == 0:
        return 'setwise coprime'
    else:
        return 'not coprime'

print(main())

Submission status: Wrong Answer

Solution code:
from math import gcd
def sieve(n):
    """
    n以下の自然数が素数が否かを判定する。

    Parameters
    ----------
    n: int
        自然数

    Returns
    -------
    f:list
      True:素数
      False:素数以外
    """
    f = []
    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(n+1):
        if is_prime[i]:
            f.append(i)
    return f


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

f = sieve(10**6)
pairwise_coprime_cnt = 0
pairwise_coprime_cnt_flg = False
even_cnt = 0
evenflg = True
for aa in a:
    if aa in f or aa == 1:
        pairwise_coprime_cnt += 1
    elif aa%2 == 0:
        if even_cnt >= 1:
            evenflg = False
            break
        even_cnt += 1

if evenflg == True:
    pairwise_coprime_cnt += even_cnt


if pairwise_coprime_cnt == n:
    if evenflg == True:
        pairwise_coprime_cnt_flg = True

tmp = a[0]
for i in range(1,n):
    tmp = gcd(tmp,a[i])

if pairwise_coprime_cnt_flg == True:
    print("pairwise coprime")
else:
    if tmp == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
from time import time
start = time()
n = int(input())
A = list(map(int,input().split()))
g = A[0]
mul = A[0]
pflag = True
for i in range(n-1):
  if pflag:
    if gcd(mul,A[i+1]) != 1:
      pflag = False 
    mul *= A[i+1]
  g = gcd(g,A[i+1])
  if i % 100 == 0:
    if time()-start > 1.9:
      if g != 1:
        print("not coprime")
        quit()
      else:
        if pflag:
          print("pairwise coprime")
          quit()
        else:
          print("setwise coprime")
          quit()
if g != 1:
  print("not coprime")
else:
  if pflag:
    print("pairwise coprime")
  else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

import math

def erastosthenes(N):
    number_list = [i for i in range(N+1)]
    is_p_list = [True]*(N+1)

    is_p_list[0] = False
    is_p_list[1] = False

    for i in range(2, math.ceil(math.sqrt(N+1))):
        if is_p_list[i]:
            for j in range(2, (N//i)+1):
                is_p_list[i*j] = False
    return [number for number in number_list if is_p_list[number]]

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

    p_list = erastosthenes(1000000)

    min_counter = 0
    for p in p_list:
        counter = 0
        for A in A_lsit:
            if A%p != 0:
                counter += 1
        min_counter = min(min_counter, counter)
    
    if min_counter >= N-1:
        print("pairwise coprime")
    elif min_counter >= 1:
        print("setwise coprime")
    else:
        print("not coprime")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


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

    tmp = [0] * N

    s = 1
    for i in range(N):
        tmp[- i - 1] = s
        s = lcm(s, A[-i - 1])
        
    print('HOGE')

    is_pairwise_coprime = True
    for i in range(N - 1):
        if math.gcd(A[i], tmp[i]) != 1:
            is_pairwise_coprime = False

    gcd_ = reduce(math.gcd, A)

    if is_pairwise_coprime:
        print('pairwise coprime')
    elif gcd_ == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
def g(a):
    al=len(a)
    if al==2:
        return gcd(a[0],a[1])
    elif al==1:
        return a[0]
    return gcd(g(a[:al//2]),g(a[al//2:]))
n=int(input())
a=list(map(int,input().split()))
if g(a)!=1:
    print("not coprime")
    exit()
one=a.count(1)
if n-one>168:
    print("setwise coprime")
    exit()
k=[i for i in a if i!=1]
n=len(k)
for i in range(n-1):
    for j in range(i+1,n):
        if gcd(k[i],k[j])!=1:
            print("setwise coprime")
            exit()
print("pairwise coprime")

Submission status: Wrong Answer

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

from math import gcd
from functools import reduce

def gcd_list(L):
    return reduce(gcd, L)

# nまでの素数リスト
def prime_list(n):
    primes = set(range(2, n + 1))
    for i in range(2, int(n ** 0.5) + 1):
        primes.difference_update(range(i * 2, n + 1, i))
    return list(primes)

g = gcd_list(A)
primes = prime_list(200)
cnt = [0] * 200

for a in A:
    for p in primes:
        if a % p == 0:
            cnt[p] += 1

ma = max(cnt)
    
if ma == 1:
    print('pairwise coprime')
elif g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


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


def LI():
    return list(MI())


n = I()
A = LI()


def fac(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


d = defaultdict(set)
for i, a in enumerate(A):
    tmp = fac(a)
    for t in tmp:
        d[t[0]].add(i)

flag1 = True
flag2 = True
for v in d.values():
    if flag1 and len(v) != 1:
        flag1 = False
    if len(v) == 1:
        flag2 = False


if flag1:
    print("pairwise coprime")
elif flag2:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections
from math import gcd
from functools import reduce

from random import randint

def lcm(a, b):
    return abs(a*b) // gcd(a, b)

def find_gcd(list):
    x = reduce(gcd, list)
    return x

def find_lcm(list):
    x = reduce(lambda a,b: lcm(a,b)% MOD, list)
    return x

MOD = 10**9 + 7
def solve(N: int, A: "List[int]"):



    # q2 = True
    # for a in A:
    #     for b in A:
    #         if a!=b and gcd(a, b) != 1:
    #             q2 = False
    #             break

    prod = 1
    for a in A:
        prod *= a % MOD
        prod = prod % MOD

    q1 = reduce(gcd, A) == 1
    q2 = find_lcm(A) % MOD == prod % MOD

    if q1 and q2:
        print('pairwise coprime')
    elif q1:
        print('setwise coprime')
    else:
        print('not coprime')
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
from math import gcd
from collections import Counter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

dup = False
dup_key = None
counter = Counter(A)
for key, val in counter.items():
    if val > 1:
        dup = True
        if dup_key is None:
            dup_key = key
        else:
            dup_key = max(dup_key, key)


def max_gcd_pair(S):
    # Assumption 1: S is the list of numbers
    # Assumption 2: There are no duplicates in S
    s = set(S)
    m = max(S)
    res = 0
    i = m
    while i > 0:
        a = i
        cnt = 0
        while a <= m: # a maxed at max of the list
            if a in s:
                cnt += 1
            a += i
        if cnt >= 2:  # we have found the result
            res = i
            break
        i = i - 1
    return res


pair = max_gcd_pair(A)
if dup:
    pair *= dup_key

if pair == 1:
    print('pairwise coprime')
    sys.exit()

setw = A[0]
for j in range(1, N):
    setw = gcd(setw, A[j])

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

Submission status: Wrong Answer

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


def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x


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==[]:  # n=1のとき、[1,1]を返す
    #     arr.append([n, 1])

    return arr


# factorization(24)
# [[2, 3], [3, 1]]
#  24 = 2^3 * 3^1

gcdall = A[0]
for i in range(1, N):
    gcdall = gcd(gcdall, A[i])

# print(gcdall)
if gcdall > 1:
    print("not coprime")
    exit()

MAX = 10 ** 6 + 1
num = [False] * MAX
A = sorted(A)[::-1]
primeset = set()
for a in A:
    # if a == 1:
    #     continue
    # if num[a]:
    #     print("setwise coprime")
    #     exit()
    fact = factorization(a)
    for p, nn in fact:
        if p in primeset:
            continue
        primeset.add(p)
        for j in range(p + p, MAX, p):
            if num[j]:
                print("setwise coprime")
                exit()
            num[j] = True
# for a in A:
#     if num[a] > 1:
#         print("setwise coprime")
#         exit()

print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def gcd(u, v):
    if u == v:
        return u
    elif u == 0:
        return v
    elif v == 0:
        return u
    # u is even
    elif u & 1 == 0:
        # v is even
        if v & 1 == 0:
            return 2*gcd(u >> 1, v >> 1)
        # v is odd
        else:
            return gcd(u >> 1, v)
    # u is odd
    elif u & 1 != 0:
        # v is even
        if v & 1 == 0:
            return gcd(u, v >> 1)
        # v is odd and u is greater than v
        elif u > v and v & 1 != 0:
            return gcd((u-v) >> 1, v)
        # v is odd and u is smaller than v
        else:
            return gcd((v-u) >> 1, u)

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

out = ""
num = 1
for i in range(N-1):
    if out != "not coprime" and gcd(As[i],As[i+1]) == 1:
        out = "pairwise coprime"
    elif gcd(num, As[i+1]) == 1 and i+1 == N:
        out = "setwise coprime"
    else:
        out = "not coprime"
    num = num % As[i]

print(out)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a_su=(sum(a))
import math
def is_prime(n:int):
    if n==1:
        return False
    for i in range(2,int(math.sqrt(n)+1)):
        if n%i==0:
            return False
    return True
if is_prime(a_su):
    for i in range(n-1):
        if math.gcd(a[i],a[i+1])!=1:
            print("setwise coprime")
    else:
        print("pairwise coprime")


else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
m=list(map(int,input().split()))
import math


d=m[n-1]

r=0


for i in range(n-2,-1,-1):
    d=math.gcd(m[i],d)
a=[1]*1000

for i in range(2,100):
    
    
    for j in range(i*i,1001,i):
        a[j-1]=0
k=[]
for i in range(1,1000):
    if a[i]==1:
        k.append(i+1)


for i in k:
    c=0
    for j in range(n):
        
        if m[j]%i==0:
            c+=1
            
    if c>1:
        r=1
        break
        
        













    
    
if d>1:
    print('not coprime')
elif r==1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import numpy as np

def seachPrimes(N):
    max = int(N ** 0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

def main():
    primes = seachPrimes(10**3)
    n = int(input())
    A = np.array(list(map(int, input().split())))


    cnts = []
    for prime in primes:
        cnt = np.sum(A % prime == 0)
        cnts.append(cnt)
    if max(cnts) == n or (min(A) == max(A) and min(A) != 1):
        print("not coprime")
    elif max(cnts) >= 2 and min(A) != 1:
        print("setwise coprime")
    else:
        print("pairwise coprime")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#E
import math
from math import gcd
N=int(input())
A=list(map(int,input().split()))

pc = "pairwise coprime"
sc = "setwise coprime"
nc = "not coprime"

maxi=max(A)
sumi=set()
safe=set()
for i in range(2,maxi+1):
    if i in sumi:
        pass
    else:
        safe.add(i)
        tmp=maxi//i
        for j in range(2,tmp+1):
            sumi.add(j*i)
    #print(i,sumi)

cnt=0
for num in A:
    if num in safe:
        cnt +=1
#print(safe,cnt)
if cnt>=N-1:
    ans=pc
else:
    tmp2=A[0]
    for q in range(1,N):
        tmp2 = gcd(tmp2,A[q])
    if tmp2==1:
        ans=sc
    else:
        ans=nc

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = set(map(int, input().split()))
ex = set()
max_A = max(A)
ans = "pairwise coprime"
for i in range(2, max_A):
    if i in ex:
        continue
    base = i
    cd = base
    cnt = 0
    while(cd < max_A):
        if cd in A:
            cnt += 1
        cd += base
        ex.add(cd)
    if cnt == N:
        ans = "not coprime"
    if cnt:
        ans = "setwise coprime"
print(ans)

Submission status: Wrong Answer

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

from math import gcd
g = A[0]
# g_list = [A[0]]
for i in range(1, N):
    g = gcd(g, A[i])
    # g_list.append(g)
if g != 1:
    print("not coprime")
    exit()
else:
    A = [a for a in A if a != 1]
    n_primes = 78498
    if N > n_primes:
        print("setwise coprime")
        exit()
    else:
        def makePrimeChecker(n):
            """
            エラトステネスの篩.
            nまでの自然数が素数かどうかを表すリストを返す.
            """
            isPrime = [True] * (n + 1)
            isPrime[0] = False
            isPrime[1] = False
            for i in range(2, int(n ** 0.5) + 1):
                if isPrime[i]:
                    for j in range(i * i, n + 1, i):
                        isPrime[j] = False
            return isPrime

        is_prime = makePrimeChecker(MAX)
        is_ok = 1
        used_prime = [0]*(MAX+1)
        primes = [n for n in range(2, MAX+1) if is_prime[n]]
        i = 0
        for p in primes:
            for a in A:
                i += 1
                if a % p == 0:
                    if used_prime[p]:
                        is_ok = 0
                        break
                    used_prime[p] = 1
            if i >= 10**7 * 4:
                break
            if not is_ok:
                break
            
        if is_ok:
            print("pairwise coprime")
        else:
            print("setwise coprime")

Submission status: Wrong Answer

Solution code:
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 set(arr)

import math
N=int(input())
A=list(map(int,input().split()))
ans=['pairwise coprime','setwise coprime','not coprime']
P=[0]*(10**6+1)
k=0
s=set()
for a in A:
    tmp=factorization(a)
    if tmp&s==set():
        s|=tmp
    else:
        k=-1
        break
if k==-1:
    g=1
    for a in A:
        g=math.gcd(g,a)
    if g==1:
        k=1
    else:
        k=2
print(ans[k])

Submission status: Wrong Answer

Solution code:
#abc177 e
import sys,math,collections,itertools
input = sys.stdin.readline


N=int(input())
A=list(map(int,input().split()))
num = [0]*(10**6+1)

def primes_dict(n):
    #
    prime_list = []
    non_prime_list = []
    k_list = []
    number_dict = {
        i: None for i in reversed(range(n + 1))}
    #
    del number_dict[0]
    del number_dict[1]
    while True:
        # get prime
        prime, _ = number_dict.popitem()
        prime_list.append(prime)
        if prime * prime > n:
            break

        # get non primes
        non_prime_list.append(prime * prime)
        while True:
            k, _ = number_dict.popitem()
            k_list.append(k)
            if prime * k > n:
                break
            non_prime_list.append(prime * k)

        while k_list:
            number_dict[k_list.pop()] = None

        # delete non prime
        while non_prime_list:
            del number_dict[non_prime_list.pop()]

    while number_dict:
        prime, _ = number_dict.popitem()
        prime_list.append(prime)

    return prime_list

P = primes_dict(10**6)

for a in A:
    if a == 1:
        continue
    else:
        num[a]+=1
        i=0
        while P[i]**2<=a:
            if a%P[i]==0:
                num[P[i]]+=1
                while a%P[i] ==0:
                    a=a//P[i]
            i +=1

mn = max(num)

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

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
A = list(map(int, input().split()))
sieve = [1] * (10**6+1)
for i in range(2, 10**3):
	if sieve[i] == 1:
		j = 2
		while(j * i <= 10**6):
			sieve[j * i] = 0
			j += 1
sieve[1] = 0
cnt = 0
for i in range(10**6+1):
	if sieve[i] == 1:
		cnt += 1

g = A[0]
for i in range(1, N):
	g = gcd(g, A[i])
	
if g != 1:
	print("not coprime")
else:
	if N > cnt:
		print("setwise coprime")
	else:
		for i in range(N):
			for j in range(i+1, N):
				if gcd(A[i], A[j]) != 1:
					print("setwise coprime")
					exit()
		print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
##https://www.codechef.com/viewsolution/20131475

from math import gcd

def main():
    n = int(input())
    A = list(map(int , input().split()))
    N = max(A)+1

    if n > 9.9*10**5 and N > 9.9*10**5:
        print("pairwise coprime")
        exit()
    sv = [i for i in range(N)]
    for i in range(2 ,int(N**2)+1) :
        if i * i >= N : break
        if sv[i] < i : continue
        for j in range(i * i , N , i) :
            sv[j] = min(sv[j] , i)

    def getPrimes(a) :
        pr = []
        if a == 1 : return pr
        pr.append(sv[a])
        while a > 1 :
            if sv[a] != pr[-1] :
                pr.append(sv[a])
            a //= sv[a]
        return pr

    np = [0] * N
    F = [0] * N

    for a in A :
        pr = getPrimes(a)
        for i in range(1 << len(pr)) :
            prod , nb = 1 , 0
            for j in range(len(pr)) :
                if i & (1<<j) :
                    prod *= pr[j]
                    nb += 1
            F[prod] += 1
            np[prod] = nb

    ans = 0
    for i in range(N) :
        cnt = F[i]
        cnt = (cnt * (cnt-1))//2
        if np[i] & 1 : ans -= cnt
        else : ans += cnt

    if ans == (n*(n-1))//2:
        print("pairwise coprime")
        exit()
    
    A.sort()
    d = A[0]

    for i in A:
        d = gcd(i,d)
        if d == 1 or d > 10**2:
            break

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

main()

Submission status: Wrong Answer

Solution code:
import math
import unittest
import collections


def f(n):
    e = set()
    if n == 1:
        return e
    while n % 2 == 0:
        e.add(2)
        n //= 2
    i = 3
    while i <= n:
        while n % i == 0:
            e.add(i)
            n //= i
        i += 2
    return e


def is_pairwise_coprime(n, a):
    e = set()
    for ai in a:
        e2 = f(ai)
        if e & e2:
            return False
        e |= e2
    return True


def is_setwise_coprime(n, a):
    gcd = a[0]
    for i in range(1, n):
        gcd = math.gcd(gcd, a[i])
        if gcd == 1:
            return True
    return gcd == 1


# number of prime
UPPER = 78498
PRIMES = [
    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
]


def solve(n, a):
    if not is_setwise_coprime(n, a):
        return 'not coprime'

    a = [e for e in a if e > 1]
    n = len(a)
    if n < 10**3:
        if is_pairwise_coprime(n, a):
            return 'pairwise coprime'
    else:
        used_factor = set()
        for p in PRIMES:
            for i in range(n):
                if a[i] % p == 0:
                    if p in used_factor:
                        return 'setwise coprime'
                    else:
                        a[i] //= p
                        used_factor.add(p)
        return 'pairwise coprime'
    return 'setwise coprime'


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(n, a))


def b():
    import random
    loop = 0
    while True:
        if loop % 100 == 0:
            print(f'#{loop}')
        n = random.randint(2, 10**3)
        a = random.choices(range(1, 10**6), k=n)
        if is_pairwise_coprime(n, a):
            assert solve(n, a) == 'pairwise coprime', (n, a)
        elif is_setwise_coprime(n, a):
            assert solve(n, a) == 'setwise coprime', (n, a)
        loop += 1


if __name__ == "__main__":
    main()

    # b()


class Test(unittest.TestCase):
    def test_1(self):
        n = 3
        a = [3, 4, 5]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_2(self):
        n = 3
        a = [6, 10, 15]
        self.assertEqual(is_pairwise_coprime(n, a), False)
        self.assertEqual(is_setwise_coprime(n, a), True)
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_3(self):
        n = 3
        a = [6, 10, 16]
        self.assertEqual(solve(n, a), 'not coprime')

    def test_4(self):
        n = 3
        a = [1, 1, 1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_5(self):
        n = 3
        a = [1, 2, 2]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_6(self):
        n = 10
        a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_7(self):
        n = 11
        a = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_8(self):
        n = 2
        a = [1, 1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_9(self):
        n = 2
        a = [1, 2]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_10(self):
        n = 2
        a = [10**6, 10**6-1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_11(self):
        n = 3
        a = [10**6, 10**6-1, 10**6, ]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_12(self):
        n = len(PRIMES) * 2
        a = PRIMES + PRIMES
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_13(self):
        a = [997, 1009, 1013, 1019, 1021, 1031, 1033, 1039,
             1049, 1051, 1061, 1063, 1069, 1087, ]
        n = len(a)
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_14(self):
        a = [1009*2, 1013*3, 1019*5, 1021, 1031, 1033, 1039,
             1049, 1051, 1061, 1063, 1069, 1087, ]
        n = len(a)
        self.assertEqual(solve(n, a), 'pairwise coprime')

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
from math import gcd
n=int(stdin.readline())
a=list(map(int,stdin.readline().split()))
s=set(a)
p=2;d={}
N=max(a)+2
primes=[1]*N;not_pairwise=0
# vis=set()
while p*p<=N:
    if primes[p]:
        for mul in range(p,N,p):
            primes[mul]=0
            if mul in s:
                # vis.add(mul)
                d[p]=d.get(p,0)+1
    p+=1
g=a[0]
for factor,freq in d.items():
    if freq>1:
        not_pairwise = 1
        break
for v in a[1:]:
    g=gcd(g,v)
if not_pairwise==0:print('pairwise coprime')
elif g==1:print('setwise coprime')
else:print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
def eratos(n):
    isprime = [[] for i in range(n+1)]
    # isprime[0] = 0
    isprime[1] = 1
    for i in range(2, int(math.sqrt(n))+1):
        if isprime[i] == []:
            j = i
        while j <= n:
            isprime[j] += [i]
            j = j + i
    return isprime

N = int(input())
A = list(map(int, input().split()))
isprime = eratos(10**6)
count = [0 for i in range(10**6+1)]

count[1] = 1
for ai in A:
    if ai == 1:
        continue
    for i in isprime[ai]:
        count[i] += 1
max_c = max(count)
if max_c == 1:
    print('pairwise coprime')
elif max_c == N:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

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

def gcd(p,q):
# Create the gcd of two positive integers.
    while q != 0:
        p, q = q, p%q
    return p

def is_coprime(x, y):
    return gcd(x, y) == 1


N = int(input())
A = list(map(int,input().split()))
flag = False
cnt = 0
GCDArr = A[0]
for i in range(N):
    for j in range(i+1,N):
        if is_coprime(A[i],A[j]) == True:
            cnt+=1
if cnt == N:
    print("pairwise coprime")
else:
    for i in range(N):
        GCDArr = gcd(GCDArr,A[i])
    if GCDArr == 1:
        print("setwise coprime")
    else:
        print("not coprime")


#print(is_coprime(17, 13))
#print(is_coprime(17, 21))
#print(is_coprime(15, 21))
#print(is_coprime(25, 45))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections
from math import gcd
from functools import reduce

from random import randint

def lcm(a, b):
    return abs(a*b) // gcd(a, b)

def find_gcd(list):
    x = reduce(gcd, list)
    return x

def find_lcm(list):
    x = reduce(lambda a,b: lcm(a,b)% MOD, list)
    return x

MOD = 10**9 + 7
def solve(N: int, A: "List[int]"):



    # q2 = True
    # for a in A:
    #     for b in A:
    #         if a!=b and gcd(a, b) != 1:
    #             q2 = False
    #             break

    prod = 1
    for a in A:
        prod *= a % MOD
        prod = prod % MOD

    q1 = reduce(gcd, A) == 1
    q2 = find_lcm(A) == prod

    if q1 and q2:
        print('pairwise coprime')
    elif q1:
        print('setwise coprime')
    else:
        print('not coprime')
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
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(*numbers):
  return reduce(math.gcd, numbers)
n=int(input())
a=list(map(int,input().split()))
d={}
flg=0
if gcd(*a)!=1:
  print('not coprime')
elif a.count(1)==n:
  print('pairwise coprime')
else:
  for i in a:
    for j in factorization(i):
      if d.get(j[0],0)==0:
        d[j[0]]=j[1]
      elif flg==0:
        print('setwise coprime')
        flg=1
        break
  if flg==0:
    print('pairwise coprime')