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:
n = raw_input()
def gcd(a,b):
	if b == 0:
		return a
	return gcd(b,a%b)

def g(ais): return reduce(gcd, ais) == 1

def f(ais):
	seen = set()
	for ai in ais:
		factor =2
		oi = ai
		while(ai != 1 and factor * factor <= oi):
			if ai % factor == 0:
				if factor in seen:
					return False
				while(ai % factor == 0):
					ai /= factor
				seen.add(factor)
			factor +=1
	return True

ais = map(int, raw_input().split())

if f(ais):
	print 'pairwise coprime'
elif g(ais):
	print 'set coprime'
else:
	print 'not coprime'

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

from math import gcd

def factorN(n):
    n1 = n + 1
    A = [2, 0] * ((n1+1)//2)
    for i in range(3, n1, 2):
        if A[i]: continue
        for j in range(i, n1, 2*i):
            A[j] = i

    def factor(n):
        if n == 1:
            return [(1, 1)]
        ans = []
        a, i = A[n], 1
        while n > 1:
            n //= a
            b = A[n]
            if a == b:
                i += 1
            else:
                ans.append((a, i))
                a = b
                i = 1

        return ans

    return factor

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = list(it)
    M = max(A)
    M1 = M + 1

    dp = [0] * M1

    g1 = A[0]
    f1 = factorN(M)
    for i, a in enumerate(A):
        g1 = gcd(g1, a)

        for x, _ in f1(a):
            if x == 1: continue
            if dp[x]:
                for i in range(i+1, N):
                    a = A[i]
                    g1 = gcd(g1, a)
                    if g1 == 1:
                        print("setwise coprime")
                        return
                print("not coprime")
                return
            dp[x] = 1

    print("pairwise coprime")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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

cut = [0 for _ in range(MAX+1)]
for i in range(2, MAX+1):
    if cut[i] != 0:
        continue
    for j in range(i, MAX+1, i):
        cut[j] = i

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

already = set()
for a in A:
    now = set()
    while a != 1:
        if cut[a] in already:
            print('setwise coprime')
            exit()
        a //= cut[a]
        now.add(cut[a])
    already |= now

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
def prime(n):
    D = [i for i in range(n+1)]
    for i in range(2, n+1):
        if i != D[i]:
            break
        j = 2
        while j * i <= n:
            if D[j * i] == j * i:
                D[j * i] = D[i]
            j += 1
    return D

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

m = max(A)

D = prime(m)

dic = {}

for i in range(n):
    if D[A[i]] not in dic:
        dic[D[A[i]]] = 1
    else:
        dic[D[A[i]]] += 1
#print(dic)
if n == len(dic):
    print('pairwise coprime')
elif len(dic) == 1:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
setA = set(A)

if len(A) == len(setA):
    #pairwiseかどうかを調べる
    memo = [1]*(10**6+1)
    memo[0] = 0
    memo[1] = 0
    for i in range(2,10**6+1):
        if memo[i] == 1:
            flag = False
            if i in setA:
                flag = True
            for j in range(i*2,10**6+1,i):
                if j in setA:
                    if flag:
                        break
                    else:
                        flag = True
                memo[j] = 0
            else:
                continue
            break
    else:
        print("pairwise coprime")
        exit()



#setwise coprimeを判断
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

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

Submission status: Wrong Answer

Solution code:
import math 
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
ans = ["pairwise coprime", "setwise coprime ", "not coprime"]

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
if gcd_list(A) != 1:
  print(ans[2])
  quit()
  
def seachPrimeNum(N):
    max = int(N ** (1 / 2))
    D = [0] * N
    D[0] = 1
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        nn = seachList[0]
        D[nn - 1] = nn
        primeNum.append(nn)
        tmp = nn
        for i in seachList:
          if i != nn:
            if i % tmp == 0:
              D[i - 1] = nn
        seachList = [i for i in seachList if i % tmp != 0]
    for i in seachList:
      D[i - 1] = i
    primeNum.extend(seachList)
    
    return primeNum, D  
  
primeNum, D = seachPrimeNum(1000000)
used = [0] * len(primeNum)

for i in range(N):
  now = A[i]
  q = []
  #print(now, D[now - 1])
  while now != D[now - 1]:
    now = int(now / D[now - 1])
    if now in primeNum:
      q.append(now)
  for i in q:
    if used[primeNum.index(i)] == 0:
      used[primeNum.index(i)] = 1
    else:
      print(ans[1])
      quit()  

print(ans[0])

Submission status: Wrong Answer

Solution code:
from math import gcd
def primes(n):
    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
    return [i for i in range(n + 1) if is_prime[i]]
p = primes(4000)
c = [0]*4001
# print(len(p))

n = int(input())
# a = [999983] * 100 + [1]
a = list(map(int,input().split()))
a = [1] * (1 in a) + [i for i in a if i != 1]
# print(a)
n = len(a)

f = 1
# if n>80000:
#     # print("not coprime")
#     # exit()
#     f = 0
g = 0
c1 = 0
if len(set(a)) != n:
    f = 0
for i in a:
    g = gcd(g,i)
    if f == 1:
        for j in p:
            if i%j == 0:
                c[j] += 1
                if c[j] > 1:
                    f = 0
if g == 1:
    if f == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")
# print(a,g,f)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[4::2] = False
        self.is_prime[9::3] = False
        self.is_prime[25::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                self.is_prime[i * i::i] = False
    
    def factorize(self, x):
        assert x >= 1
        if x == 1:
            return [(1, 1)]
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        return result


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

    if all(a == 1 for a in A):
        return 'pairwise coprime'

    gcd_all = 0
    for a in A:
        gcd_all = math.gcd(gcd_all, a)

    if gcd_all > 1:
        return 'not coprime'
    
    sieve = SieveOfEratosthenes(max(A))
    used_primes = set()
    for a in A:
        if a != 1:
            factors = sieve.factorize(a)
            for (p, e) in factors:
                if p in used_primes:
                    return 'set coprime'
                used_primes.add(p)
    
    return 'pairwise coprime'

print(solve())

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
dp = [0 for i in range(a[-1])]
p = [0 for i in range(a[-1])]
for i in range(n):
    p[a[i]-1] = 1
ans = 1
for i in range(2,a[-1]+1):
    if dp[i-1] == 1:
        continue
    u = 0
    k = 1
    while i*k <= a[-1]:
        dp[i*k-1] = 1
        if p[i*k-1] == 1:
            u += 1
        k += 1
    if u == n:
        ans = -1
    elif u > 1:
        ans = min(ans,0)
if ans == 1:
    print('pairwise coprime')
elif ans == 0:
    print('setwise coprime')
elif a[0] == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math 
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
ans = ["pairwise coprime", "setwise coprime ", "not coprime"]

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
if gcd_list(A) != 1:
  print(ans[2])
  quit()
  
def seachPrimeNum(N):
    max = int(N ** (1 / 2))
    D = [0] * N
    D[0] = 1
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        nn = seachList[0]
        D[nn - 1] = nn
        primeNum.append(nn)
        tmp = nn
        for i in seachList:
          if i != nn:
            if i % tmp == 0:
              D[i - 1] = nn
        seachList = [i for i in seachList if i % tmp != 0]
    for i in seachList:
      D[i - 1] = i
    primeNum.extend(seachList)
    
    return primeNum, D  
  
primeNum, D = seachPrimeNum(1000000)
used = [0] * len(primeNum)

for i in range(N):
  now = A[i]
  #print(now, D[now - 1])
  while now != D[now - 1]:
    now = int(now / D[now - 1])
    if now in primeNum:
      xx = primeNum.index(now)
      if used[xx] == 1:
        print(ans[1])
        quit()
      else:
        used[xx] = 1
                
  
  
  

print(ans[0])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def gcd(a, b):
    if a < b:
        return gcd(b, a)
    while b > 0:
        a, b = b, a % b
    return a

def sieve_of_eratosthenes(n):
    sieve = [0] * (n+1)
    sieve[0] = 1 #素数でない
    sieve[1] = 1 #素数でない
    for i in range(2, n):
        if sieve[i] == 0:
            for j in range(2, n // i + 1):
                sieve[i * j] = i
    return sieve

def factorize_by_sieve_of_eratosthenes(x, sieve):
    factor = defaultdict(int)
    while sieve[x]:
        factor[sieve[x]] += 1
        x //= sieve[x]
    factor[x] += 1
    return factor

n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n):
    if a[i] != 1:
        break
a = a[i:]
n -= i
if n == 1:
    print("pairwise coprime")
    quit()

sieve = sieve_of_eratosthenes(a[-1])
x = a[0]

pairwise = True
setwise = True
primes = set()
for i in range(n):
    if x != 1:
        x = gcd(x, a[i])
    if pairwise:
        factor = set(factorize_by_sieve_of_eratosthenes(a[i], sieve).keys())
        if not primes.isdisjoint(factor):
            pairwise = False
        else:
            primes |= factor

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

Submission status: Wrong Answer

Solution code:
D = [0]*(10**6+1)
L = [True]*(10**6+1)
L[0] = False
L[1] = False
D[1] = 1
for i in range(2, 10**6+1):
    if L[i]:
        D[i] = i
        for j in range(i*2, 10**6+1, i):
            L[j] = False
            D[j] = i


def egcd(a, b):
    if a == 0:
        return b
    else:
        g = egcd(b % a, a)
        return g


def factorization(n):
    if n == 1:
        return {1}
    ans = set()
    ans.add(D[n])
    factorization(n//D[n])
    return ans


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

s = set()
for i in range(N):
    tmp = factorization(A[i])-{1}
    if tmp & s != set():
        break
    s |= tmp
else:
    print('pairwise coprime')
    exit()

L1 = A
while len(L1) > 1:
    l = len(L1)//2
    tmp = [0]*l
    for i in range(l):
        tmp[i] = egcd(L1[2*i], L1[2*i+1])
    if len(L1) % 2 == 1:
        tmp.append(L1[-1])
    L1 = tmp

if L1[0] == 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(int)
for i, a in enumerate(A):
    tmp = fac(a)
    for t in tmp:
        d[t[0]] += 1

flag = True
for v in d.values():
    if flag and v != 1:
        flag = False
    if v == N:
        print("not coprime")
        exit()


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

Submission status: Wrong Answer

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

c=[0]*max(a)
for i in range(n): 
    m=a[i]
    pf={}
    for j in range(2,int(m**0.5)+1):
        while m%j==0:
            pf[j]=pf.get(j,0)+1
            m//=j
    if m>1:pf[m]=1

    for k in pf:
        c[k-1]+=1

if n in c:
    print('not coprime')
    exit()

for i in c:
    if c[i]>1:
        print('setwise coprime')
        exit()

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
setA = set(A)

#pairwiseかどうかを調べる
memo = [1]*(10**6+1)
memo[0] = 0
memo[1] = 0

for i in range(2,10**6+1):
    if memo[i] == 1:
        flag = False
        if i in setA:
            flag = True
        for j in range(i*2,10**6+1,i):
            if j in setA:
                if flag:
                    break
                else:
                    flag = True
            memo[j] = 0
        else:
            continue
        break
else:
    print("pairwise coprime")
    exit()



#setwise coprimeを判断
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

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

Submission status: Wrong Answer

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

A = sorted(A,reverse = True)
prime = [0] * (10**6+1)
eratos = list(range(2,A[0]+1))
D = [0] * (A[0]+1)
D[1] = 1
i = 0
while len(eratos)>i:
  x = eratos[i]
  for a in eratos[i:]:
    if a%x==0:
      D[a] = x
  eratos = [a for a in eratos if (a==x)or(a%x!=0)]
  i += 1

Submission status: Wrong Answer

Solution code:
from collections import Counter
primes = []
flag = [True for i in range(10**3 + 1)]
for i in range(2, 10**3 + 1):
    if flag[i]:
        for j in range(2, 10**3 + 1):
            if i * j > 10**3:
                break
            flag[i * j] = False
        primes.append(i)

# print(primes)
N = int(input())
alist = []
for a in map(int, input().split()):
    f = True
    for p in primes:
        if p > a**(1 / 2):
            alist.append(a)
            f = False
            break
        if a % p == 0:
            alist.append(p)
            f = False
            break
    if f:
        alist.append(a)

count = Counter(Counter(alist).values())
_max = max(count)
if _max == 1:
    print("pairwise coprime")
elif _max == N:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
import math
import fractions
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, ela):
    if n == 1:
        return {1: 1}


    prime_dict = {}
    for i in ela:
        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 sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

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


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela2 = [i for i, b in enumerate(ela) if b]

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

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()

    SA = set(A)
    SA.discard(1)
    if len(SA) >= 90000:
        print("!not coprime")
        exit()

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela2)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 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: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
dp = [0 for i in range(a[-1])]
p = [0 for i in range(a[-1])]
for i in range(n):
    p[a[i]-1] = 1
ans = 1
for i in range(2,a[-1]+1):
    if dp[i-1] == 1:
        continue
    u = 0
    k = 1
    while i*k <= a[-1]:
        dp[i*k-1] = 1
        if p[i*k-1] == 1:
            u += 1
        k += 1
    if u == n:
        ans = -1
    elif u > 1:
        ans = min(ans,0)
if ans == 1:
    print('pairwise coprime')
elif ans == 0:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    mylist = LI()
    max_num = max(mylist)
    max_num2 = math.ceil(math.sqrt(max_num))
    D = [True]* (max_num+1)
    D[0] = D[1] = False
    mylist = set(mylist)
    setwise = True
    pairwise = True

    for i in range(2, max_num+1):
        temp = 0
        if D[i]:
            for j in range(i, max_num+1, i):
                D[j] = False
                if j in mylist:
                    temp+=1
        D[i] = True
        if temp == N:
            print("not coprime")
            exit()
        if temp >= 2:
            pairwise = False

    if pairwise:
        print("pairwise coprime")
    else:
        print("setwise coprime")
                    

            
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import fractions
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, ela):
    if n == 1:
        return {1: 1}


    prime_dict = {}
    for i in ela:
        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 sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

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


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela2 = [i for i, b in enumerate(ela) if b]

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

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()
    
    SA = set(A)
    SA.discard(1)
    if len(SA) >= 90000:
        print("not coprime")
        exit()

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela2)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 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: Wrong Answer

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

A = sorted(A,reverse = True)
prime = [0] * (10**6+1)
eratos = list(range(2,A[0]+1))
D = [0] * (A[0]+1)
D[1] = 1
i = 0
while len(eratos)>i:
  x = eratos[i]
  for a in eratos[i:]:
    if a%x==0:
      D[a] = x
  eratos = [a for a in eratos if (a==x)or(a%x!=0)]
  i += 1
  
for a in A:
  while a!=1:
    x = D[a]
    while a%x==0:
      a//=x
    prime[x] += 1

if max(prime)==1:
  print('pairwise coprime')
  
elif max(prime)!=N:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
era=[[] for i in range(10**6+1)]

a.sort()
k=2
while k<(10**6+1)**0.5+1:
  for i in range(k,10**6+1,k):
    era[i].append(k)
  if k==2:
    k+=1
  else:
    k+=2
ans=[]
for i in a:
  ans+=era[i]
ans.sort()
pflag=True
for i in range(len(ans)-1):
  if ans[i]==ans[i+1]:
    pflag=False
    break
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
import math
import fractions
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, ela):
    if n == 1:
        return {1: 1}


    prime_dict = {}
    for i in ela:
        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 sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

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


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela2 = [i for i, b in enumerate(ela) if b]

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

    SA = set(A)
    SA.discard(1)
    if len(SA) >= 90000:
        print("not coprime")
        exit()

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela2)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 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: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
def is_primes(n):
    primes = [1]*n
    primes[0] =0
    primes[1] =0
    for i in range(2,int(n**0.5)+1):
        if primes[i] ==1:
            for j in range(2*i,n,i):
                primes[j] = 0
    return primes

def factorize(n,primes):
    fct = [(1,1)]
    for b in primes:#primes ::sorted
        if b * b > n:
            break
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
    if n > 1:
        fct.append((n,1))
    return fct

n =ni()
A = lma()

mx= 10**6+10
prms = is_primes(mx)
prms2=[i for i in range(mx) if prms[i]==1]
d=collections.Counter()
for a in A:
    fct = factorize(a,prms2)
    #print(fct)
    for fc,cnt in fct:
        d[fc]+=1
f1=True # pp or sp
f2=True # sp or not p
for num,cnt in d.items():
    if num==1:
        continue
    if cnt==n:
        f2=False #not p
        break
    else:
        if cnt==1:
            pass
        else:
            f1=False
            break
if f2==False:
    print("not coprime")
elif f1:
    print("pairwise coprime")
elif f1==False:
    print("setwise 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(int)
for i, a in enumerate(A):
    tmp = fac(a)
    for t in tmp:
        d[t[0]] += 1

flag = True
for v in d.values():
    if flag and v != 1:
        flag = False
    if v == N:
        print("not coprime")
        exit()


if flag:
    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, cnt])

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

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

    return arr


N = int(input())
A = list(map(int, input().split()))
all_so = []
num2cnt = {}
cnt = 0
for i in range(N):
    so = [one[0] for one in factorization(A[i])]
    flag = False
    for one in so:
        if one not in all_so:
            all_so.append(one)
            flag=True
        if one not in num2cnt:
            num2cnt[one] = 0
        num2cnt[one]+=1
            
    if flag:
        cnt+=1
if cnt==N:
    print('pairwise coprime')
else:
    flag = True
    for key in num2cnt:
        if num2cnt[key]==N:
            print('not coprime')
            flag = False
            break
    if flag:
        print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

n = int(input())
A = list(map(int,input().split()))
d  =[0]*(2*10**6+1)
c = [0]*(2*10**6+1)
max_val = 2*10**6
for a in A:
    d[a] += 1
A.sort()
one= 0
if A[0]==1:
    one =1
set_ = set()
tmp = 0
for i in range(2,max_val+1):
    if c[i]==0:
        cnt = 0
        for j in range(i,max_val+1,i):
            c[j]=1
            if d[j] != 0:
                if i not in set_:
                    set_.add(i)
                cnt += 1
            tmp = max(cnt,tmp)

if len(set_)==1:
    print('not coprime')
elif len(set_)==n-one:
    if tmp>1:
        print('setwise coprime')
    else:
        print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
def resolve():
    import math
    n = int(input())
    a = list(map(int, input().split()))
    a = list(set(a))
    a = sorted(a)
    ggcd = a[0]
    for i in range(1, len(a)):
        ggcd = math.gcd(ggcd, a[i])
        if ggcd == 1:
            break
    if ggcd != 1:
        print("not coprime")
    else:
      print("test")
resolve()