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())
num_lis = list(map(int, input().split()))
c1 = True #setwise
c2 = True #pairwise

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

hoge = 0
for i in num_lis:
  hoge = gcd(hoge, i)
if hoge > 1:
  c1 = False

if c1:
  d_lis = osa_k(10**6+10)
  tmp = set()
  for i in num_lis:
    num = i
    new_tmp = set()
    while num > 1:
      d = d_lis[num]
      new_tmp.add(d)
      num //= d
    for j in new_tmp:
      if j in tmp:
        c2 = False
        break
      else:
        tmp.add(j)
    else:
      continue
    break

if c2:
  print("pairwise coprime")
elif c1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True #setwise
c2 = True #pairwise

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

hoge = 0
for i in num_lis:
  hoge = gcd(hoge, i)
if hoge > 1:
  c1 = False

if c1:
  d_lis = osa_k(10**6+10)
  tmp = set()
  for i in num_lis:
    num = i
    new_tmp = set()
    while num > 1:
      d = d_lis[num]
      new_tmp.add(d)
      num //= d
    for j in new_tmp:
      if j in tmp:
        c2 = False
        break
      else:
        tmp.add(j)
    else:
      continue
    break

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

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True
c2 = True

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

hoge = 0
for i in num_lis:
  hoge = gcd(hoge, i)
if i > 1:
  print("not coprime")
  exit()

d_lis = osa_k(max(num_lis))
tmp = set()
for i in num_lis:
  num = i
  new_tmp = set()
  while num > 1:
    d = d_lis[num]
    new_tmp.add(d)
    num //= d
  if len(tmp | new_tmp) != len(tmp)+len(new_tmp):
    print("setwise coprime")
    exit()
  else:
    tmp |= new_tmp
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True
c2 = True

d_lis = [i for i in range(max(num_lis)+2)]
p = 2
while p**2 <= max(num_lis):
  if d_lis[p] == p:
    for q in range(2*p, max(num_lis)+1, p):
      if d_lis[q] == q:
        d_lis[q] = p
  p += 1

tmp = []
for i in num_lis:
  num = i
  new_tmp = []
  while num > 1:
    d = d_lis[num]
    new_tmp.append(d)
    num //= d
  #print(new_tmp)
  for j in new_tmp:
    if j in tmp:
      c1 = False
      break
    else:
      tmp.append(j)
  if not c1:
    break
if c1:
  print("pairwise coprime")
  exit()

g = 0
for i in num_lis:
  g = gcd(g, i)
if g > 1:
  c2 = False
if c2:
  print("setwise coprime")
  exit()
print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from math import gcd
from functools import reduce

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True
c2 = True

d_lis = [i for i in range(max(num_lis)+2)]
p = 2
while p**2 <= max(num_lis):
  if d_lis[p] == p:
    for q in range(2*p, max(num_lis)+1, p):
      if d_lis[q] == q:
        d_lis[q] = p
  p += 1

tmp = []
for i in num_lis:
  num = i
  new_tmp = []
  while num > 1:
    d = d_lis[num]
    new_tmp.append(d)
    num //= d
  #print(new_tmp)
  for j in new_tmp:
    if j in tmp:
      c1 = False
      break
    else:
      tmp.append(j)
  if not c1:
    break
if c1:
  print("pairwise coprime")
  exit()

g = 0
for i in num_lis:
  g = gcd(g, i)
if g > 1:
  c2 = False
if c2:
  print("setwise coprime")
  exit()
print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from math import gcd
from functools import reduce

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True
c2 = True

d_lis = [i for i in range(max(num_lis)+2)]
p = 2
while p**2 <= max(num_lis):
  if d_lis[p] == p:
    for q in range(2*p, max(num_lis)+1, p):
      if d_lis[q] == q:
        d_lis[q] = p
  p += 1

tmp = []
for i in num_lis:
  num = i
  new_tmp = []
  while num > 1:
    d = d_lis[num]
    new_tmp.append(d)
    num //= d
  #print(new_tmp)
  for j in new_tmp:
    if j in tmp:
      c1 = False
      break
    else:
      tmp.append(j)
  if not c1:
    break

g = 0
for i in num_lis:
  g = gcd(g, i)
if g > 1:
  c2 = False

if c1:
  print("pairwise coprime")
elif not c1 and c2:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from math import gcd
from functools import reduce

def osa_k(max_num):
  lis = [i for i in range(max_num+2)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True
c2 = True

d_lis = osa_k(max(num_lis))
tmp = []
for i in num_lis:
  num = i
  new_tmp = []
  while num > 1:
    d = d_lis[num]
    new_tmp.append(d)
    num //= d
  #print(new_tmp)
  for j in new_tmp:
    if j in tmp:
      c1 = False
      break
    else:
      tmp.append(j)
  if not c1:
    break

g = 0
for i in num_lis:
  g = gcd(g, i)
  if g != 1:
    c2 = False
    break

if c1:
  print("pairwise coprime")
elif not c1 and c2:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from math import gcd
from functools import reduce

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True
c2 = True

d_lis = osa_k(max(num_lis))
tmp = set()
for i in num_lis:
  num = i
  new_tmp = set()
  while num > 1:
    d = d_lis[num]
    new_tmp.add(d)
    num //= d
  #print(new_tmp)
  if len(tmp)+len(new_tmp) == len(tmp | new_tmp):
    tmp |= new_tmp
    continue
  else:
    c1 = False
    break

g = 0
for i in num_lis:
  g = gcd(g, i)
  if g != 1:
    c2 = False
    break

if c1:
  print("pairwise coprime")
elif not c1 and c2:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

from math import gcd

def solve():
    N = II()
    A = LI()
    
    mx = 1000003
    D = [1] * mx
    for i in range(2, len(D)):
        # if D[i] != 1:
        #     continue
        for j in range(i, len(D), i):
            if D[j] == 1:
                D[j] = i
    # print(D[mx-3])
    # print(D[4], D[6], D[35])

    g = A[0]
    # dct = defaultdict(int)
    # flag = True
    C = [0] * mx
    for a in A:
        g = gcd(g, a)
        # print(a, D[a])
        # if D[a] != 1:
        #     if dct[D[a]] > 0:
        #         flag = False
        #     dct[D[a]] += 1
        d = D[a]
        C[d] += 1
    # print(dct, flag, g)
    # flag = False
    if all(C[i] <= 1 for i in range(2, len(C))):
        flag = True
    else:
        flag = False

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


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

from math import gcd

def solve():
    N = II()
    A = LI()
    
    mx = 1000003
    D = [1] * mx
    for i in range(2, mx):
        # if D[i] != 1:
        #     continue
        for j in range(i, mx, i):
            if D[j] == 1:
                D[j] = i
    # print(D[mx-3])
    # print(D[4], D[6], D[35])

    g = A[0]
    # dct = defaultdict(int)
    # flag = True
    C = [0] * mx
    for a in A:
        g = gcd(g, a)
        # print(a, D[a])
        # if D[a] != 1:
        #     if dct[D[a]] > 0:
        #         flag = False
        #     dct[D[a]] += 1
        d = D[a]
        C[d] += 1
    # print(dct, flag, g)
    # flag = False
    if all(C[i] <= 1 for i in range(2, len(C))):
        flag = True
    else:
        flag = False

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


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

from math import gcd

def solve():
    N = II()
    A = LI()
    
    mx = 1000003
    D = [1] * mx
    for i in range(2, mx):
        if D[i] != 1:
            continue
        for j in range(i, mx, i):
            if D[j] == 1:
                D[j] = i
    # print(D)
    # print(D[4], D[6], D[35])

    g = A[0]
    # dct = defaultdict(int)
    # flag = True
    C = [0] * mx
    for a in A:
        g = gcd(g, a)
        # print(a, D[a])
        # if D[a] != 1:
        #     if dct[D[a]] > 0:
        #         flag = False
        #     dct[D[a]] += 1
        d = D[a]
        C[d] += 1
    # print(dct, flag, g)
    # flag = False
    if all(C[i] <= 1 for i in range(2, len(C))):
        flag = True
    else:
        flag = False
        
    if g == 1:
        if flag:
            print('pairwise coprime')
        else:
            print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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


def main():
    N = int( sys.stdin.readline() )
    A_list = list(map(int, sys.stdin.readline().split()))


    def get_factor(n :int) -> set:
        ans = set()
        
        for i in range(2, int(n**(1/2)+1) ):  # exclude "factor 1" and "max factor"
            if  n % i == 0:
                ans.add(i)
                
                d = n / i
                if (d != i) and (d % 1 == 0):
                    ans.add( int(d) )
        
        ans.add(n)  # include "max factor"
        return ans

    # ----------
    factor = [None] * N

    for i in range(N):
        factor[i] = get_factor( A_list[i] )
    
    # ----------
    for i in range(1, N):
        check = factor[i] & factor[i-1]

        if check:
            break
    
    else:
        print("pairwise coprime")
        return

    # ----------
    common = set( factor[0] )

    for i in range(1, N):
        common &= factor[i]

    if (not common):
        print("setwise coprime")
        return
    
    # ----------
    print("not coprime")
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

from math import gcd

def solve():
    N = II()
    A = LI()
    
    mx = 1000003
    D = [1] * mx
    for i in range(2, mx):
        if D[i] != 1:
            continue
        for j in range(i, mx, i):
            if D[j] == 1:
                D[j] = i
    # print(D)
    # print(D[4], D[6], D[35])

    g = A[0]
    dct = defaultdict(int)
    flag = True
    for a in A:
        g = gcd(g, a)
        # print(a, D[a])
        if D[a] != 1:
            if dct[D[a]] > 0:
                flag = False
            dct[D[a]] += 1
    # print(dct, flag, g)
    flag = False
    if g == 1:
        if flag:
            print('pairwise coprime')
        else:
            print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

from math import gcd

def solve():
    N = II()
    A = LI()
    
    mx = 1000003
    D = [1] * mx
    for i in range(2, mx):
        if D[i] != 1:
            continue
        for j in range(i, mx, i):
            if D[j] == 1:
                D[j] = i
    # print(D)
    # print(D[4], D[6], D[35])

    g = A[0]
    dct = defaultdict(int)
    flag = True
    for a in A:
        g = gcd(g, a)
        # print(a, D[a])
        if D[a] != 1:
            if dct[D[a]] > 0:
                flag = False
            dct[D[a]] += 1
    # print(dct, flag, g)
    if g == 1:
        if flag:
            print('pairwise coprime')
        else:
            print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

from math import gcd

def solve():
    N = II()
    A = LI()
    
    mx = 1000001
    D = [1] * mx
    for i in range(2, mx):
        if D[i] != 1:
            continue
        for j in range(i, mx, i):
            if D[j] == 1:
                D[j] = i
    # print(D)
    # print(D[4], D[6], D[35])

    g = A[0]
    dct = defaultdict(int)
    flag = True
    for a in A:
        g = gcd(g, a)
        # print(a, D[a])
        if D[a] != 1:
            if dct[D[a]] > 0:
                flag = False
            dct[D[a]] += 1
    # print(dct, flag, g)
    if g == 1:
        if flag:
            print('pairwise coprime')
        else:
            print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
if a == [1,1]:
    print("pairwise coprime")
    quit()
m = max(a)
l = [-1]*(m+3)
for i in range(2,m+1):
    if l[i] != -1:
        continue
    l[i] = i
    j = 2
    while i*j <= m:
        if l[i*j] == -1:
            l[i*j] = i
        j += 1
def fastfact(i,lst):
    if l[i] == -1:
        return lst
    while i > 1:
        lst.append(l[i])
        i //= l[i]
    return lst
check = [0]*(m+1)
for i in range(n):
    if a[i] == 1:
        continue
    s = set(fastfact(a[i],[]))
    for j in s:
        check[j] += 1
M = max(check)
if M == 1:
    print("pairwise coprime")
elif M == n:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = max(a)
l = [-1]*(m+3)
for i in range(2,m+1):
    if l[i] != -1:
        continue
    l[i] = i
    j = 2
    while i*j <= m:
        if l[i*j] == -1:
            l[i*j] = i
        j += 1
def fastfact(i,lst):
    if l[i] == -1:
        return lst
    while i > 1:
        lst.append(l[i])
        i //= l[i]
    return lst
check = [0]*(m+1)
for i in range(n):
    if a[i] == 1:
        continue
    s = set(fastfact(a[i],[]))
    for j in s:
        check[j] += 1
M = max(check)
if M == 1:
    print("pairwise coprime")
elif M == n:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
n=int(input())
1/(n>2)

Submission status: Wrong Answer

Solution code:
n=int(input())
1/(n>1)

Submission status: Wrong Answer

Solution code:
m=1
c=[0]*6**8
n,a=open(0)
for a in a.split():c[int(a)]+=1
print(('not','psaeitr'[any((m:=max(m,sum(c[i::i])))>1for i in range(2,6**8))::2]+'wise')[m<int(n)],'coprime')

Submission status: Wrong Answer

Solution code:
c=[m:=0]*6**8
n,a=open(0)
for a in a.split():c[int(a)]+=1
print(('not','psaeitr'[any((m:=max(m,sum(c[i::i])))>1for i in range(2,6**8))::2]+'wise')[m<int(n)],'coprime')
1/(m<=int(n))

Submission status: Wrong Answer

Solution code:
c=[m:=0]*6**8
n,a=open(0)
for a in a.split():c[int(a)]+=1
print(('not','psaeitr'[any((m:=max(m,sum(c[i::i])))>1for i in range(2,6**8))::2]+'wise')[m<int(n)],'coprime')

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

def factoring(n):
    """
    This program factorize any number.
    This returns the dictionary of prime factors of the number.(if n=18=2*3**2, this returns {2:1,3:2})
        """
    if n == 0:
        return {0: 1}
    if n == 1:
        return {1: 1}

    # 今回のアルゴリズムについて
    # nが素数でない⇔nは√n以下の素因数を持つ⇒√n以下のすべての素数を列挙して、それでnを割っていってみる。
    #√n以下の素数をすべて書き出すために、エラトステネスの篩を使用する。t以下の素数をすべて列挙するためには√tまでの素数について調べれば十分なので、√nまでの素数を書き出すためには√√nまでの数について真面目に篩をかければいい。

    nOrigin = n
    n = n**0.5
    # n(=√input())以下の素数のリストをエラトステネスにより作成する
    # 素数の位置にはその数が、合成数の位置には-1が格納されているリストを作成
    # 0が格納されているのはまだ確認していない数。
    numlist = [0 for i in range(int(n) + 1)]
    numlist[0] = -1
    numlist[1] = -1

    #√√n以下の数について篩をかけていく
    t = 2
    while t < (n**0.5):
        if numlist[t] == 0:
            numlist[t] = t
            k = 2
            while t * k <= n:
                numlist[t * k] = -1
                k += 1
        t += 1

    #√√nより大きい数で、篩にかからなかった数は素数。
    while t <= n:
        if numlist[t] == 0:
            numlist[t] = t
        t += 1

    #√n以下の数で割っていく。
    result = {}
    for i in numlist:
        if i == -1:
            continue
        j = 0
        while nOrigin % i == 0:
            j += 1
            nOrigin = nOrigin / i
        if j == 0:
            continue
        else:
            result[i] = j

    if int(nOrigin) != 1:
        result[int(nOrigin)] = 1
    return result

def GCD(a, b):
    M = max(a, b)
    m = min(a, b)
    if m == 0:
        return M
    else:
        return GCD(m, M % m)


N=int(input())
A=[int(i) for i in input().split(" ")]

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

if gcd!=1:
    print("not coprime")
    sys.exit()


factors = [Counter(factoring(a)) for a in A]

S=Counter()
for f in factors:
    S+=f



for f in factors:
    for prime in f:
        if S[prime]>f[prime]:
            print("setwise coprime")
            sys.exit()

print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

def factoring(n):
    """
    This program factorize any number.
    This returns the dictionary of prime factors of the number.(if n=18=2*3**2, this returns {2:1,3:2})
        """
    if n == 0:
        return {0: 1}
    if n == 1:
        return {1: 1}

    # 今回のアルゴリズムについて
    # nが素数でない⇔nは√n以下の素因数を持つ⇒√n以下のすべての素数を列挙して、それでnを割っていってみる。
    #√n以下の素数をすべて書き出すために、エラトステネスの篩を使用する。t以下の素数をすべて列挙するためには√tまでの素数について調べれば十分なので、√nまでの素数を書き出すためには√√nまでの数について真面目に篩をかければいい。

    nOrigin = n
    n = n**0.5
    # n(=√input())以下の素数のリストをエラトステネスにより作成する
    # 素数の位置にはその数が、合成数の位置には-1が格納されているリストを作成
    # 0が格納されているのはまだ確認していない数。
    numlist = [0 for i in range(int(n) + 1)]
    numlist[0] = -1
    numlist[1] = -1

    #√√n以下の数について篩をかけていく
    t = 2
    while t < (n**0.5):
        if numlist[t] == 0:
            numlist[t] = t
            k = 2
            while t * k <= n:
                numlist[t * k] = -1
                k += 1
        t += 1

    #√√nより大きい数で、篩にかからなかった数は素数。
    while t <= n:
        if numlist[t] == 0:
            numlist[t] = t
        t += 1

    #√n以下の数で割っていく。
    result = {}
    for i in numlist:
        if i == -1:
            continue
        j = 0
        while nOrigin % i == 0:
            j += 1
            nOrigin = nOrigin / i
        if j == 0:
            continue
        else:
            result[i] = j

    if int(nOrigin) != 1:
        result[int(nOrigin)] = 1
    return result


N=int(input())
A=[int(i) for i in input().split(" ")]

factors = [Counter(factoring(a)) for a in A]

S=Counter()
for f in factors:
    S+=f


pair_wise=True

for f in factors:
    for prime in f:
        if S[prime]>f[prime]:
            pair_wise=False
            break

if pair_wise:
    print("pairwise coprime")
    sys.exit()

setwise=True
for f in S:
    if sum([a%f for a in A])==0:
        setwise=False

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

def factoring(n):
    """
    This program factorize any number.
    This returns the dictionary of prime factors of the number.(if n=18=2*3**2, this returns {2:1,3:2})
        """
    if n == 0:
        return {0: 1}
    if n == 1:
        return {1: 1}

    # 今回のアルゴリズムについて
    # nが素数でない⇔nは√n以下の素因数を持つ⇒√n以下のすべての素数を列挙して、それでnを割っていってみる。
    #√n以下の素数をすべて書き出すために、エラトステネスの篩を使用する。t以下の素数をすべて列挙するためには√tまでの素数について調べれば十分なので、√nまでの素数を書き出すためには√√nまでの数について真面目に篩をかければいい。

    nOrigin = n
    n = n**0.5
    # n(=√input())以下の素数のリストをエラトステネスにより作成する
    # 素数の位置にはその数が、合成数の位置には-1が格納されているリストを作成
    # 0が格納されているのはまだ確認していない数。
    numlist = [0 for i in range(int(n) + 1)]
    numlist[0] = -1
    numlist[1] = -1

    #√√n以下の数について篩をかけていく
    t = 2
    while t < (n**0.5):
        if numlist[t] == 0:
            numlist[t] = t
            k = 2
            while t * k <= n:
                numlist[t * k] = -1
                k += 1
        t += 1

    #√√nより大きい数で、篩にかからなかった数は素数。
    while t <= n:
        if numlist[t] == 0:
            numlist[t] = t
        t += 1

    #√n以下の数で割っていく。
    result = {}
    for i in numlist:
        if i == -1:
            continue
        j = 0
        while nOrigin % i == 0:
            j += 1
            nOrigin = nOrigin / i
        if j == 0:
            continue
        else:
            result[i] = j

    if int(nOrigin) != 1:
        result[int(nOrigin)] = 1
    return result


N=int(input())
A=[int(i) for i in input().split(" ")]

factors = [Counter(factoring(a)) for a in A]

S=Counter()
for f in factors:
    S+=f

print(factors)
print(S)

pair_wise=True

for f in factors:
    for prime in f:
        if S[prime]>f[prime]:
            pair_wise=False
            break

if pair_wise:
    print("pairwise coprime")
    sys.exit()

setwise=True
for f in S:
    if sum([a%f for a in A])==0:
        setwise=False

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

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
m=6**8
c=[0]*m
p=[1,1]+c[:]
for i in range(m):
  if p[i]<1:
    for j in range(i,m,i):p[j]=i
for a in a:
  c[a]+=1
  while a!=p[a]:
    i=p[a]
    c[i]+=1
    a//=p[a]
    c[a]+=i!=a
print(('not','psaeitr'[max(c[2:])>1::2]+'wise')[max(c[2:])<n],'coprime')

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
m=6**8
c=[0]*m
p=[1,1]+c[:]
for i in range(m):
  if p[i]<1:
    for j in range(i,m,i):p[j]=i
for a in a:
  c[a]+=1
  while p[a]!=a:
    a//=p[a]
    c[a]+=1
print(('not','psaeitr'[max(c[2:])>1::2]+'wise')[max(c[2:])<n],'coprime')

Submission status: Wrong Answer

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

#素数
def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

primes=primes(int(1000))
points=[0]*1000001

from math import gcd
pairprime_flag=True
allgcd=A[0]
allprime=set()

for a in A:
    allgcd=gcd(allgcd,a)
    for i in primes:
        if a%i==0:
            if points[i]==1:
                pairprime_flag=False
            points[i]=1
            while a%i==0:
                a//=i

if pairprime_flag:
    print('pairwise coprime')
elif allgcd==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

#素数
def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

#素因数分解
n=1000000
primelist=set(primes(int(n**0.5+1))+[n+1])
def primeset(n):
    factors=set()
    for prime in primelist:
        if prime>n:
            factors.add(n)
            break
        while n%prime==0:
            n=n//prime
            factors.add(prime)
    for i in factors:
        if i in primelist:
            primelist.remove(i)
    return n

from math import gcd
def lcm(a,b):
    return a*b//gcd(a,b)

pairprime_flag=True
allgcd=A[0]
allprime=set()

for a in A:
    allgcd=gcd(allgcd,a)
    st = primeset(a)
    if st==1:
        continue
    if st!=1:
        pairprime_flag=False

if pairprime_flag:
    print('pairwise coprime')
elif allgcd==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

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

D = [i for i in range(1000001)]

for i in range(2,1001):
    if D[i] == i:
        for j in range(2,1+100000//i):
            D[i*j] = i

###
#print(D[:10])
###

det = True
P = []

for a in A:
    Q = []
    aa = a
    while aa > 1:
        Q.append(D[aa])
        aa //= D[aa]
    P = P + list(set(Q))

    if len(P) != len(set(P)):
        det = False
        break
    P = list(set(P))

if det:
    print('pairwise coprime')

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