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:
from math import gcd

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

v = 0
for a in A: v = gcd(a, v)
if v > 1:
	print('not coprime')
	raise SystemExit


primes = [2, 3, 5, 7]
for i in range(9, 10**3, 2):
	for v in primes:
		if v % i == 0: break
	else:
		primes.append(i)

V = [False] * len(primes)
for v in A:
	for i, p in enumerate(primes):
		if v % p == 0:
			if V[i]:
				print('setwise coprime')
				raise SystemExit
			else:
				V[i] = True

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math

def sieve():
  MAX_INT = 10**6+1
  primes = [True]*(MAX_INT)
  primes[0],primes[1] = False,False

  for i in range(2,int(math.sqrt(MAX_INT)+1)):
    if primes[i] == True:
      # multiple of i
      j = 2
      while i*j < MAX_INT:
        primes[i*j] = False
        j += 1

  return primes

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

odd,even,prime = 0,0,0
for i in range(N):
  if primes[A[i]]:
    prime += 1
  else:
    if A[i]%2==0:
      even += 1
    else:
      odd += 1

if prime == N:
  print("pairwise coprime")
elif even<=1 and odd<=1:
  print("pairwise coprime")
elif prime > 0:
  print("setwise coprime")
else:
  p1 = 2
  while A[0]%p1!=0:
    p1 += 1
  p2 = A[0]//p1

  for i in range(1, N):
    if A[i]%p1==0 or A[i]%p2==0:
      print("not coprime")
      exit()

  print("setwise coprime")

Submission status: Wrong Answer

Solution code:
from sys import exit
from math import gcd

def eratosthenes(n):
    '''
    n以下の整数の素数判定/列挙 (n > 1)
    O(NloglogN)
    '''
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    min_factor = [-1] * (n+1)
    min_factor[0] = 0
    min_factor[1] = 1
    
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            min_factor[i] = i
            for j in range(i*2, n+1, i):
                is_prime[j] = False
                if min_factor[j] == -1:
                    min_factor[j] = i

    return min_factor


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

l = eratosthenes(10**6+1)

flag = True
used = [False] * (10**6+1)
for v in a:
    s = set()
    while v > 1:
        if l[v] not in s:
            if used[l[v]]:
                flag = False
                break
            else:
                s.add(l[v])
                used[l[v]] = True
        
        v //= l[v]

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

g = 0
for v in a:
    g = gcd(g, v)

print('setwise coprime' if g == 1 else 'not coprime')

Submission status: Wrong Answer

Solution code:
def find_gcd(x, y): 
    while (y): 
        x, y = y, x % y 
    return x 
def fun(l):
  num1=l[0] 
  num2=l[1] 
  gcd=find_gcd(num1,num2) 
  for i in range(len(l)-1):
    gcd=find_gcd(l[i],l[i+1])
    if gcd!=1:
      break;
  else:
    print("pairwise coprime")
    return 1
  gcd=l[0]
  for i in range(2,len(l)):
    gcd=find_gcd(gcd,l[i])
  if gcd==1:
    print("setwise coprime")
    return 1

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

x=fun(l)
if x!=1:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
def find_gcd(x, y): 
    while (y): 
        x, y = y, x % y 
    return x 
def fun(l):
  num1=l[0] 
  num2=l[1] 
  gcd=find_gcd(num1,num2) 
  for i in range(len(l)-1):
    gcd=find_gcd(l[i],l[i+1])
    if gcd!=1:
      break;
  else:
    print("pairwise coprime")
    return 1
 
  for i in range(2,len(l)):
    gcd=find_gcd(gcd,l[i])
  if gcd==1:
    print("setwise coprime")
    return 1

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

x=fun(l)
if x!=1:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import math

def sieve():
  MAX_INT = 10**6+1
  primes = [True]*(MAX_INT)
  primes[0],primes[1] = False,False

  for i in range(2,int(math.sqrt(MAX_INT)+1)):
    if primes[i] == True:
      j = 2
      while i*j < MAX_INT:
        primes[i*j] = False
        j += 1

  return primes

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

odd,even,prime = 0,0,0
for i in range(N):
  if primes[A[i]]:
    prime += 1
  else:
    if A[i]%2==0:
      even += 1
    else:
      odd += 1

if prime == N:
  print("pairwise coprime")
elif even<=1 and odd<=1:
  print("pairwise coprime")
elif prime > 0:
  print("setwise coprime")
else:
  p = 2
  while A[0]%p!=0:
    p += 1

  for i in range(1, N):
    if A[i]%p!=0:
      print("setwise coprime")
      exit()

  print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
d=[0]*(10**6)
for i in a:
  d[i-1]+=1
num=2
while num<=10**6:
  if sum([d[i*num-1] for i in range(1,10**6//num+1)])>1:
      break
  num+=1
else:
  print('setwise coprime')
  exit()
g=reduce(gcd,a)
if g==1:
  print('pairwise coprime')
  exit()

print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

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

pcount = 78498 # not include 1

hurui = [1] * 1000
primes = []

for n in range(2, 1000):
    if hurui[n-1] != 1:
        continue

    primes.append(n)

    k = 2
    while n * k <= 1000:
        hurui[n * k - 1] = n
        k += 1

#print(len(list(filter(lambda i: i == 0, hurui))))
#print(primes)

#print(primes)

wise = A[0]
for n in A[1:]:
    wise = math.gcd(wise, n)

pairwise = True
for i in range(N):
    a = A[i]
    if a == 1:
        continue

    for p in primes:
        if a % p != 0:
            continue
        for j in range(i+1, N):
            if A[j] % p == 0:
                pairwise = False
                break
        if not pairwise:
            break
    if pairwise:
        for j in range(i+1, N):
            if A[j] == a:
                pairwise = False
                break

if pairwise:
    ans = 'pairwise coprime'
elif wise == 1:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'


print(ans)
#print(wise)

Submission status: Wrong Answer

Solution code:
def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def is_pairwise():
    MAX_A = 10**6
    C = [0] * (MAX_A + 1)
    for a in A: C[a] += 1
    if sum(C[2::2]) > 1: return False
    for i in range(3, min(a, MAX_A)+1, 2):
        if sum(C[i::i]) > 1: return False
    return True

def solve():
    if is_pairwise(): return 0
    if gcd_all(A) == 1: return 1
    return 2

n = int(input())
A = [*map(int, input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Submission status: Wrong Answer

Solution code:
def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def is_pairwise():
    MAX_A = 10**6
    C = [0] * (MAX_A + 1)
    for a in A: C[a] += 1
    if sum(C[2::2]) > 1: return False
    for i in range(3, a+1, 2):
        if sum(C[i::i]) > 1: return False
    return True

def solve():
    if is_pairwise(): return 0
    if gcd_all(A) == 1: return 1
    return 2

n = int(input())
A = [*map(int, input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Submission status: Wrong Answer

Solution code:
import math

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

pcount = 78498 # not include 1

hurui = [1] * 1000
primes = []

for n in range(2, 1000):
    if hurui[n-1] != 1:
        continue

    primes.append(n)

    k = 2
    while n * k <= 1000:
        hurui[n * k - 1] = n
        k += 1

#print(len(list(filter(lambda i: i == 0, hurui))))
#print(primes)

#print(primes)

wise = A[0]
for n in A[1:]:
    wise = math.gcd(wise, n)

pairwise = True
for i in range(N):
    a = A[i]
    for p in primes:
        if a % p != 0:
            continue
        for j in range(i+1, N):
            if A[j] % p == 0:
                pairwise = False
                break
        if not pairwise:
            break
    if not pairwise:
        for j in range(i+1, N):
            if A[j] == a:
                pairwise = False
                break

if pairwise:
    ans = 'pairwise coprime'
elif wise == 1:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'


print(ans)
#print(wise)

Submission status: Wrong Answer

Solution code:
import math

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

pcount = 78498 # not include 1

hurui = [1] * 1000
primes = []

for n in range(2, 1000):
    if hurui[n-1] != 1:
        continue

    primes.append(n)

    k = 2
    while n * k <= 1000:
        hurui[n * k - 1] = n
        k += 1

#print(len(list(filter(lambda i: i == 0, hurui))))
#print(primes)

#print(primes)

wise = A[0]
for n in A[1:]:
    wise = math.gcd(wise, n)

pairwise = True
for i in range(N):
    a = A[i]
    for p in primes:
        if a % p != 0:
            continue
        for j in range(i+1, N):
            if A[j] % p == 0 or A[j] == a:
                pairwise = False
                break
        if not pairwise:
            break

if pairwise:
    ans = 'pairwise coprime'
elif wise == 1:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'


print(ans)
#print(wise)

Submission status: Wrong Answer

Solution code:
def main():
    from math import gcd
    from itertools import chain
    import sys
    input = sys.stdin.readline

    # def gcd(x, y):
    #     if y == 0:
    #         return x
    #     return gcd(y, x % y)
    # 6n+1, 6n-1でも求めて、素数**2+素数*kはふるいおとす
    def prime_set(N):
        if N < 4:
            return ({}, {}, {2}, {2, 3})[N]
        Nsq = int(N ** 0.5 + 0.5) + 1
        primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
        for i in range(5, Nsq, 2):
            if i in primes:
                primes -= set(range(i * i, N + 1, i * 2))
        # return list(primes)
        return primes
    n = int(input())
    A = [int(x) for x in input().split()]
    # setwise coprimeの条件(1ならOK)
    g = 0
    for a in A:
        g = gcd(g, a)
    # 素数列挙
    num = 10**6+1
    primes = prime_set(num)
    # 全部素因数分解
    prime_list = [0] * (num+1)
    pairwise_f = True
    for a in A:
        if a in primes:
            prime_list[a] += 1
            if prime_list[a] == 2:
                break
            else:
                continue
            # l.append(a)
        # l = []
        # cnt = 0
        tmp = a
        # nsq = int(a ** 0.5 + 0.5) + 1
        for i in primes:
            if i*i > a:
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                prime_list[i] += 1
                # l.append(i)
                # cnt += 1
                if prime_list[i] == 2:
                    break
        # if tmp != 1:
        #     prime_list[tmp] += 1
        #     # l.append(tmp)
        #     # cnt += 1
        #     if prime_list[tmp] == 2:
        #         break
        # if l == []:
        # if cnt == 0:
        #     if a != 1:
        #         prime_list[a] += 1
        #         # l.append(a)
        #         if prime_list[a] == 2:
        #             break
    set_prime_list = set(prime_list)
    # print(prime_list[:100])
    if set_prime_list != set([0]) and set_prime_list != set([0, 1]):
        pairwise_f = False
    if pairwise_f:
        print('pairwise coprime')
    elif g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

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

pcount = 78498 # not include 1

hurui = [1] * 1000
primes = []

for n in range(2, 1000):
    if hurui[n-1] != 1:
        continue

    primes.append(n)

    k = 2
    while n * k <= 1000:
        hurui[n * k - 1] = n
        k += 1

#print(len(list(filter(lambda i: i == 0, hurui))))
#print(primes)

wise = A[0]
for n in A[1:]:
    wise = math.gcd(wise, n)

pairwise = True
for i in range(N):
    a = A[i]
    for p in primes:
        if a % p != 0:
            continue
        for j in range(i+1, N):
            if A[j] % p == 0:
                pairwise = False
                break
        if not pairwise:
            break

if pairwise:
    ans = 'pairwise coprime'
elif wise == 1:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'


print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from math import gcd
    from itertools import chain
    import sys
    input = sys.stdin.readline

    # def gcd(x, y):
    #     if y == 0:
    #         return x
    #     return gcd(y, x % y)
    # 6n+1, 6n-1でも求めて、素数**2+素数*kはふるいおとす
    def prime_set(N):
        if N < 4:
            return ({}, {}, {2}, {2, 3})[N]
        Nsq = int(N ** 0.5 + 0.5) + 1
        primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
        for i in range(5, Nsq, 2):
            if i in primes:
                primes -= set(range(i * i, N + 1, i * 2))
        # return list(primes)
        return primes
    n = int(input())
    A = [int(x) for x in input().split()]
    # setwise coprimeの条件(1ならOK)
    g = 0
    for a in A:
        g = gcd(g, a)
    # 素数列挙
    num = 10**6+1
    primes = prime_set(num)
    # 全部素因数分解
    prime_list = [0] * (num+1)
    pairwise_f = True
    for a in A:
        if a in primes:
            prime_list[a] += 1
            # l.append(a)
            if prime_list[a] == 2:
                break
        # l = []
        # cnt = 0
        tmp = a
        # nsq = int(a ** 0.5 + 0.5) + 1
        for i in primes:
            if i*i > a:
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                prime_list[i] += 1
                # l.append(i)
                # cnt += 1
                if prime_list[i] == 2:
                    break
        # if tmp != 1:
        #     prime_list[tmp] += 1
        #     # l.append(tmp)
        #     # cnt += 1
        #     if prime_list[tmp] == 2:
        #         break
        # if l == []:
        # if cnt == 0:
        #     if a != 1:
        #         prime_list[a] += 1
        #         # l.append(a)
        #         if prime_list[a] == 2:
        #             break
    set_prime_list = set(prime_list)
    # print(prime_list[:100])
    if set_prime_list != set([0]) and set_prime_list != set([0, 1]):
        pairwise_f = False
    if pairwise_f:
        print('pairwise coprime')
    elif g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def erathos(N):
    res = []
    D = [1] * (N+1)
    D[0] = 1
    D[1] = 1
    for i in range(2,N+1):
      if D[i] > 1:
        continue
      D[i] = i
      j = i * 2
      while j <= N:
        D[j] = i
        j += i
    return D;

def prime_set(a, D):
    res = set()
    while a != D[a]:
        res.add(D[a])
        a = a // D[a]
    res.add(D[a])
    return res
  
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    plist = erathos(max(A))
    
    Factors = []
    for a in A:
      Factors.append(prime_set(a, plist))
    
    fset = set(Factors[0])
    fcommon = set(Factors[0])
    eleflg = True
    for f in Factors[1:]:
      if f == set([1]):
        continue
      fcommon = fcommon & f
      if len(fset & f) == 0:
        fset = fset | f
      else:
        eleflg = False
        # 互いに素でないペアがいる
        pass
    if len(fcommon) > 0:
      print("not coprime")
    elif eleflg:
      print("pairwise coprime")
    else:
      print("setwise coprime")
    #print(fcommon)
    exit(0)

main()

Submission status: Wrong Answer

Solution code:
def erathos(N):
    res = []
    D = [1] * (N+1)
    D[0] = 1
    D[1] = 1
    for i in range(2,N+1):
      if D[i] > 1:
        continue
      D[i] = i
      j = i * 2
      while j <= N:
        D[j] = i
        j += i
    return D;

def prime_set(a, D):
    res = set()
    while a != D[a]:
        res.add(D[a])
        a = a // D[a]
    res.add(D[a])
    return res
  
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    plist = erathos(max(A))
    
    Factors = []
    for a in A:
      Factors.append(prime_set(a, plist))
    
    fset = set(Factors[0])
    fcommon = set(Factors[0])
    eleflg = True
    for f in Factors[1:]:
      fcommon = fcommon & f
      if len(fset & f) == 0:
        fset = fset | f
      else:
        eleflg = False
        # 互いに素でないペアがいる
        pass
    if len(fcommon) > 0:
      print("not coprime")
    elif eleflg:
      print("pairwise coprime")
    else:
      print("setwise coprime")
    #print(fcommon)
    exit(0)

main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

def prime(n):
    res = set()

    if not n % 2:
        res.add(2)
        while not n % 2:
            n //= 2

    i = 3

    while pow(i, 2) <= n:
        if not n % i:
            res.add(i)
            while not n % i:
                n //= i
        i += 2

    if n > 1: res.add(n)

    return res

def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = Counter()
    
    for a in A:
        res = prime(a)
        
        for r in res:
            cnt[r] += 1
            
    for c in cnt.values():
        if c == N:
            print('not coprime')
            return
        elif c > 1:
            print('setwise coprime')
            return
            
    print('pairwise coprime')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5) + 1
        cnt_list = [0] * (n + 1)
        for i in range(2, limit + 1):
            if cnt_list[i] == 0:
                k = n // i
                for j in range(1, k + 1):
                    s = i * j
                    if cnt_list[s] == 0:
                        D[s] = i
                        cnt_list[s] = 1
        for l in range(limit, n + 1):
            if cnt_list[l] == 0:
                D[l] = l
                cnt_list[l] = 1
        return D



    N = I()
    A = LI()
    D = defaultdict()
    max_a = max(A)
    num_list = [0] * (max_a + 1)
    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()

    A_ = set(A)
    A_.discard(1)
    if len(A_) >= 90000:
        print('setwise coprime')
        exit()

    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        while a != 1:
            x = D[a]
            if num_list[x] != 0:
                print('setwise coprime')
                exit()
            num_list[x] = 1
            a //= x

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5) + 1
        cnt_list = [0] * (n + 1)
        for i in range(2, limit + 1):
            if cnt_list[i] == 0:
                k = n // i
                for j in range(1, k + 1):
                    s = i * j
                    if cnt_list[s] == 0:
                        D[s] = i
                        cnt_list[s] = 1
        for l in range(limit, n + 1):
            if cnt_list[l] == 0:
                D[l] = l
                cnt_list[l] = 1
        return D



    N = I()
    A = LI()
    D = defaultdict()
    max_a = max(A)
    num_list = [0] * (10 ** 6 + 1)
    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()

    A_ = set(A)
    A_.discard(1)
    if len(A_) >= 90000:
        print('setwise coprime')
        exit()

    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        while a != 1:
            x = D[a]
            if num_list[x] != 0:
                print('setwise coprime')
                print(num_list)
                exit()
            num_list[x] = 1
            a //= x

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5) + 1
        cnt_list = [0] * (n + 1)
        for i in range(2, limit + 1):
            if cnt_list[i] == 0:
                k = n // i
                for j in range(1, k + 1):
                    s = i * j
                    if cnt_list[s] == 0:
                        D[s] = i
                        cnt_list[s] = 1
        for l in range(limit, n + 1):
            if cnt_list[l] == 0:
                D[l] = l
                cnt_list[l] = 1
        return D



    N = I()
    A = LI()
    D = defaultdict()
    max_a = max(A)
    num_list = [0] * (max_a+ 1)
    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()

    A_ = set(A)
    A_.discard(1)
    if len(A_) >= 90000:
        print('setwise coprime')
        exit()

    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        while a != 1:
            x = D[a]
            if num_list[x] != 0:
                print('setwise coprime')
                print(num_list)
                exit()
            num_list[x] = 1
            a //= x

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5) + 1
        cnt_list = [0] * (n + 1)
        for i in range(2, limit + 1):
            if cnt_list[i] == 0:
                k = n // i
                for j in range(1, k + 1):
                    s = i * j
                    if cnt_list[s] == 0:
                        D[s] = i
                        cnt_list[s] = 1
        for l in range(limit, n + 1):
            if cnt_list[l] == 0:
                D[l] = l
                cnt_list[l] = 1
        return D



    N = I()
    A = LI()
    D = defaultdict()
    num_list = [0] * (10 ** 6 + 1)

    max_a = max(A)
    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()

    A_ = set(A)
    A_.discard(1)
    if len(A_) >= 90000:
        print('setwise coprime')
        exit()

    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        while a != 1:
            x = D[a]
            if num_list[x] != 0:
                print('setwise coprime')
                exit()
            num_list[x] = 1
            a //= x

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5) + 1
        cnt_list = [0] * (n + 1)
        for i in range(2, limit + 1):
            if cnt_list[i] == 0:
                k = n // i
                for j in range(1, k + 1):
                    s = i * j
                    if cnt_list[s] == 0:
                        D[s] = i
                        cnt_list[s] = 1
        for l in range(limit, n + 1):
            if cnt_list[l] == 0:
                D[l] = l
                cnt_list[l] = 1
        return D



    N = I()
    A = LI()
    D = defaultdict()
    num_list = [0] * (10 ** 6 + 1)

    max_a = max(A)
    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()

    A_ = set(A)
    A_.discard(1)
    if len(A_) >= 90000:
        print('setwise coprime')
        exit()

    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        while a != 1:
            x = D[a]
            if num_list[x] == 1:
                print('setwise coprime')
                exit()
            num_list[x] = 1
            a //= x

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5)
        cnt_list = [0] * (n + 1)
        for i in range(2, limit + 1):
            if cnt_list[i] == 0:
                k = n // i
                for j in range(1, k + 1):
                    s = i * j
                    if cnt_list[s] == 0:
                        D[s] = i
                        cnt_list[s] = 1
        for l in range(limit, n + 1):
            if cnt_list[l] == 0:
                D[l] = l
                cnt_list[l] = 1
        return D



    N = I()
    A = LI()
    D = defaultdict()
    num_list = [0] * (10 ** 6 + 1)

    max_a = max(A)
    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()

    A_ = set(A)
    A_.discard(1)
    if len(A_) >= 90000:
        print('setwise coprime')
        exit()

    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        while a != 1:
            x = D[a]
            if num_list[x] == 1:
                print('setwise coprime')
                exit()
            num_list[x] = 1
            a //= x

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
import time

#pri_arr[i]におけるiの素因数のうち最大の数を持つ配列をつくる
#pri_arrはこんな感じになる↓
#[0, 0, 2, 3, 2, 5, 3, 7, 2, 3,...]
def make_prime_arr(max_a):
    pri_arr = [0] * max_a
    #start_time = time.time()
    for i in range(2, max_a):
        if(pri_arr[i] != 0):
            continue
        for j in range (i, max_a, i):
            pri_arr[j] = i
    #end_time = time.time()
    #print(end_time - start_time)
    return pri_arr


#pairwiseかどうかを判定する関数
def is_pairwise(a_arr, pri_arr, max_a):
    flg_arr = [0] * (max_a)
    for a_ele in a_arr:
        x = a_ele
        y = -1
        while x != 1:
            if(y != pri_arr[x]):
                flg_arr[pri_arr[x]] += 1
            if flg_arr[pri_arr[x]] > 1:
                return False
            x = x // pri_arr[x]
            y = x
    return True


#setwiseかどうかを判定する関数
def is_setwise(a_arr, N):
    entire_gcd = a_arr[0]
    for i in range(1, N):
        entire_gcd = gcd(entire_gcd, a_arr[i])
    if entire_gcd != 1:
        return False        
    return True


def main():
    N = int(input())
    a_arr = list(map(int, input().split(" ")))
    max_a = 10**6 + 1
    pri_arr = make_prime_arr(max_a)
    if is_pairwise(a_arr, pri_arr, max_a):
        print("pairwise coprime")
    elif is_setwise(a_arr, N):
        print("setwise coprime")
    else:
        print("not coprime")

if __name__ == "__main__":
    main()