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: Accepted

Solution code:
import numpy as np
from numba import njit

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6

nums = np.zeros(MAX + 1, np.int64)
for e in a:
    nums[e] += 1


@njit
def solve(nums):
    mx = 0
    for i in range(2, MAX + 1):
        cnt = nums[i::i].sum()
        mx = max(mx, cnt)

    return mx


mx = solve(nums)

if nums[1] == n:
    ans = "pairwise coprime"
elif mx == n:
    ans = "not coprime"
elif mx == 1:
    ans = "pairwise coprime"
else:
    ans = "setwise coprime"

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)


n = 10**6
minfac = list(range(n+1))
for i in range(2, int(n**0.5) + 1):
    if minfac[i] < i:
        continue
    for j in range(i, n + 1, i):
        if minfac[j] > i:
            minfac[j] = i

"""nの素因数の種類を求める"""
def osa_k(n):
    temp = set()
    while n > 1:
        temp.add(minfac[n])
        n = n//minfac[n]
    return temp


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

check = [0]*(10**6)
flag = 0
for a in A:
    for i in osa_k(a):
        if check[i]:
            flag = 1
        else:
            check[i] = 1
    if flag:
        break
        
if gcd_list(A) > 1:
    print("not coprime")
elif flag:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
from math import gcd
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int, readline().split()))
M = max(A) + 1
#0-index
minfactor = [0] * M
minfactor[1] = 1
commondivisor = [0] * M

def seive():
    for i in range(2,M):
        if minfactor[i] == 0:
            for j in range(i*2,M,i):
                if minfactor[j] == 0:
                    minfactor[j] = i
    for i in range(2,M):
        if minfactor[i] == 0:
            minfactor[i] = i  

gc = A[0]
for i in range(1,N):
    gc = gcd(A[i],gc)
    
if gc != 1:
    print('not coprime')
else:
    seive()
    for i in range(N):
        a = A[i]
        while a > 1:
            div = minfactor[a]
            commondivisor[div] += 1
            while a % div == 0:
                a //= div
    if max(commondivisor) <= 1:
        print('pairwise coprime')
    else:
        print('setwise coprime')

Submission status: Accepted

Solution code:
import sys,random
from math import gcd
input=sys.stdin.readline
n=int(input())
*a,=map(int, input().split())
random.shuffle(a)
tmp=a[0]
for i in range(1,n):
    tmp=gcd(tmp,a[i])
if tmp>1:
    print('not coprime')
    exit()

# pairwize coprime なら素因数が2度現れることはない

def f(x):
    res=set()
    for i in range(2,int(x**(1/2))+3):
        if x%i==0:
            while x%i==0:
                x//=i
            res.add(i)
    return res,x
tmp=set()
tmp2=set()
for ai in a:
    for p in tmp:
        if ai%p==0:
            print('setwise coprime')
            exit()
    pp,x=f(ai)
    tmp|=pp 
    if x>1 and x in tmp2:
        print('setwise coprime')
        exit()
    tmp2.add(x)
    
        
print('pairwise coprime')

Submission status: Accepted

Solution code:
import sys,math
n=int(input())
a=list(map(int,input().split()))
numbers={}
flag=0
for i in range(n):
  if a[i] in numbers:
    numbers[a[i]]+=1
  else:
    numbers[a[i]]=1
for pointer in range(2,10**6+1):
  count=0
  pointer2=pointer
  while pointer2<10**6+1:
    if pointer2 in numbers:
      count+=numbers[pointer2]
    pointer2+=pointer
  if count>=2:
    flag=1
    break
if flag==0:
  print('pairwise coprime')
  sys.exit()
ans=a[0]
for i in range(1,n):
  ans=math.gcd(a[i],ans)
if ans==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Accepted

Solution code:
import sys,math
n=int(input())
a=list(map(int,input().split()))
numbers={}
flag=0
for i in range(n):
  if a[i] in numbers:
    numbers[a[i]]+=1
  else:
    numbers[a[i]]=1
pointer=2
while pointer<10**6+1:
  count=0
  pointer2=pointer
  while pointer2<10**6+1:
    if pointer2 in numbers:
      count+=numbers[pointer2]
    pointer2+=pointer
  if count>=2:
    flag=1
    break
  pointer+=1
if flag==0:
  print('pairwise coprime')
  sys.exit()
ans=a[0]
for i in range(1,n):
  ans=math.gcd(a[i],ans)
if ans==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from math import gcd
N=10**6+2
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
mp=[0]*N;not_pairwise=1
for v in a:
    mp[v]+=1
for i in range(2,N):
    if sum(mp[i::i])>1:
        not_pairwise=0
        break
g = a[0]
for v in a:
    g = gcd(g, v)
if not_pairwise:
    print('pairwise coprime')
elif g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def factorize(n, d):
  # if n == 0 or n == 1:
    # return []
    arr = []
    tmp = n
    while True:
      i = d[tmp]
      if i == 1:
        break
      #cnt=0
      while tmp%i==0:
        #cnt+=1
        tmp //= i
      arr.append(i)
    if tmp!=1:
      arr.append(tmp)
    if arr==[]:
      arr.append(n)
    return arr

def minimum_prime(n):
  # 試し割りをする際の最小の素数
  # エラトステネスの篩と同様の実装
    d = list(range(n+1))
    d[0] = 1
    for i in range(2, int(n**0.5) + 1):
        if d[i] != i:
          continue
        for j in range(i * 2, n + 1, i):
          if d[j] == j:
            d[j] = i
    return d  

def main():
  n = int(input())
  arr = list(map(int, input().split()))
  max_arr = max(arr)
  d = minimum_prime(max_arr)
  dp = [0]*(max_arr+1)
  
  if gcd(*arr) != 1:
    print('not coprime')
    exit()
  
  searched = []
  for a in arr:
    if a != 1:
      primes = factorize(a, d)
      for p in primes:
        dp[p] += 1

  if max(dp) < 2:
    print('pairwise coprime')
  else:
    print('setwise coprime')
    

main()

Submission status: Accepted

Solution code:
import math
 
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
 
input()
d = None
u = set()
for x in map(int, input().split()):
  d = math.gcd(d or x, x);
  s = set()
  while x > 1:
    p = spf[x]
    s.add(p)
    x //= p
  if u & s:
    r = 'setwise'
  u |= s
print('not' if d > 1 else r, 'coprime')

Submission status: Accepted

Solution code:
import math

N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'

input()
d = None
u = set()
for x in map(int, input().split()):
  d = math.gcd(d, x) if d else x;
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print('not' if d > 1 else r, 'coprime')

Submission status: Accepted

Solution code:
from math import gcd


def prime_fac(x):
    pfs = set()
    for i in range(2, x):
        if i * i > x:
            break
        while x % i == 0:
            pfs.add(i)
            x //= i
    if x > 1:
        pfs.add(x)
    return pfs


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

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

if g != 1:
    print("not coprime")
    exit()

s = set()
for v in a:
    p = prime_fac(v)
    ls, lp = len(s), len(p)
    s.update(p)
    if len(s) < ls + lp:
        print("setwise coprime")
        exit()
print("pairwise coprime")

Submission status: Accepted

Solution code:
from math import gcd


def prime_fac(x):
    pfs = set()
    for i in range(2, x):
        if i * i > x:
            break
        while x % i == 0:
            pfs.add(i)
            x //= i
    if x > 1:
        pfs.add(x)
    return pfs


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

a.sort()
xs = [0] * (a[-1] + 1)
g = a[0]
for v in a:
    g = gcd(g, v)
    xs[v] += 1

if g != 1:
    print("not coprime")
    exit()

s = set()
for v in a:
    p = prime_fac(v)
    ls, lp = len(s), len(p)
    s.update(p)
    if len(s) < ls + lp:
        print("setwise coprime")
        exit()
print("pairwise coprime")

Submission status: Accepted

Solution code:
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'

input()
a = input().split()
m = a.count('1')
if len(a) > m + 1:
  u = set()
  i = None
  for x in map(int, a):
    s = set()
    while x > 1:
      p = spf[x]
      if p in u:
        r = 'setwise'
      s.add(p)
      x //= p
    u |= s
    if m == 0:
      if i is None: i = s
      else: i &= s
  if i:
    r = 'not'
print(r, 'coprime')

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7
 
N = int(input())
A = list(map(int,input().split()))
 
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i ==0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
 
    if temp != 1:
        arr.append([temp, 1])
 
    if arr == []:
        arr.append([n, 1])
 
    return arr
 
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
 
def multiple(a, b):
    return a*b // euclid(a, b)
 
def gcd(nums):
    return functools.reduce(euclid, nums)
 
if gcd(A) != 1:
    print("not coprime")
 
else:
    """
    flag = 0
    M = [False]*(10**6+1)
    for i in range(N):
        n = A[i]
        if M[n]:
            flag = 1
            break
        if n != 1:
            k = 1
            while n*k <= 10**6:
                M[n*k] = True
                k += 1
    """
    flag = 0
    M = [False]*(10**6+1)
    for i in range(N):
        n = A[i]
        if n == 1:
            continue
        l = factorization(n)
        for j in range(len(l)):
            p = l[j][0]
            if M[p]:
                flag = 1
                break
            M[p] = True
        else:
            continue
        break
    if flag == 0:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

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

one = A.count(1)

def find_prime(n):
    prime_list = []
    find_list = list(range(2,n+1))
    while True:
        if find_list[0] > n**(1/2):
            prime_list.extend(find_list)
            break
        else:
            head = find_list[0]
            prime_list.append(head)
            find_list.pop(0)
            find_list = [num for num in find_list if num % head != 0]
    return prime_list

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

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

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

    return arr

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

def multiple(a, b):
    return a*b // euclid(a, b)

def gcd(nums):
    return functools.reduce(euclid, nums)

if gcd(A) != 1:
    print("not coprime")

else:
    """
    flag = 0
    M = [False]*(10**6+1)
    for i in range(N):
        n = A[i]
        if M[n]:
            flag = 1
            break
        if n != 1:
            k = 1
            while n*k <= 10**6:
                M[n*k] = True
                k += 1
    """
    flag = 0

    if N-one <= 78500:
        M = [False]*(10**6+1)
        for i in range(N):
            n = A[i]
            if n == 1:
                continue
            l = factorization(n)
            for j in range(len(l)):
                p = l[j][0]
                if M[p]:
                    flag = 1
                    break
                M[p] = True
    else:
        flag = 1
    
    if flag == 0:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Accepted

Solution code:
import itertools
import collections

class PrimeFactorize:
    def __init__(self, n):
        self.prime_factor_table = self.create_prime_factor_table(n)

    # O(NloglogN)
    def create_prime_factor_table(self, n):
        self.table = [0] * (n + 1)
        
        for i in range(2, n + 1):
            if self.table[i] == 0:
                for j in range(i + i, n + 1, i):
                    self.table[j] = i
        return self.table

    def prime_factor(self, n):
        prime_count = collections.Counter()
        
        while self.prime_factor_table[n] != 0:
            prime_count[self.prime_factor_table[n]] += 1
            n //= self.prime_factor_table[n]
        prime_count[n] += 1
        return prime_count

N = int(input())
A_s = list(map(int, input().split()))
pc = True
sc = True
M = {}
MAX = 0
pf = PrimeFactorize(10**6+1)

for i,A in enumerate(A_s):
    L = pf.prime_factor(A)
    for l in L.keys():
        if l == 1:
            continue
        if l in M:
            # print()
            M[l] += 1
            pc = False
        else:
            M[l] = 1
        MAX = max(MAX, M[l])
    if not pc and MAX <= i:
        break
else:
    sc = False

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

Submission status: Accepted

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

x = max(A)
hurui = [x]*(x+1)
for i in range(2, x+1):
    for j in range(i, x+1, i):
        hurui[j] = min(i, hurui[j])

cnt = Counter([1])
for i in range(N):
    num = A[i]
    while num > 1:
        x = hurui[num]
        while num%x == 0:
            num //= x
        cnt[x] += 1

a = cnt.most_common(1)[0][1]
if a == 1:
    print("pairwise coprime")
elif a < N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import itertools
import collections
def prime_factor_table(n):
    table = [0] * (n + 1)
    
    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i
    
    return table

def prime_factor(n, prime_factor_table):
    prime_count = collections.Counter()
    
    while prime_factor_table[n] != 0:
        prime_count[prime_factor_table[n]] += 1
        n //= prime_factor_table[n]
    prime_count[n] += 1
    
    return prime_count

N = int(input())
A_s = list(map(int, input().split()))
# A_s = [int(i+1) for i in range(N)]
pc = True
sc = True
M = {}
MAX = 0
TABLE = prime_factor_table(10**6+1)

for i,A in enumerate(A_s):
    L = prime_factor(A, TABLE)
    for l in L.keys():
        if l == 1:
            continue
        if l in M:
            # print()
            M[l] += 1
            pc = False
        else:
            M[l] = 1
        MAX = max(MAX, M[l])
    if not pc and MAX <= i:
        break
else:
    sc = False

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

Submission status: Accepted

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

import itertools
import collections
def prime_factor_table(n):
    table = [0] * (n + 1)
    
    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i
    
    return table

def prime_factor(n, prime_factor_table):
    prime_count = collections.Counter()
    
    while prime_factor_table[n] != 0:
        prime_count[prime_factor_table[n]] += 1
        n //= prime_factor_table[n]
    prime_count[n] += 1
    
    return prime_count

N = int(input())
A_s = list(map(int, input().split()))
# A_s = [int(i+1) for i in range(N)]
pc = True
sc = True
M = {}
MAX = 0
TABLE = prime_factor_table(10**6+1)

for i,A in enumerate(A_s):
    L = prime_factor(A, TABLE)
    for l in L.keys():
        if l == 1:
            continue
        if l in M:
            # print()
            M[l] += 1
            pc = False
        else:
            M[l] = 1
        MAX = max(MAX, M[l])
    if not pc and MAX <= i:
        break
else:
    sc = False

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
  n = int(input())
  A = tuple(map(int, input().split()))
  U = 10**6
  D = list(range(U+1))
  i = 2
  while i*i <= U:
    if D[i] != i:
      i += 1
      continue
    for j in range(i*i, U+1, i):
      D[j] = min(D[j], i)
    i += 1
  C = [0]*(U+1)
  is_pairwise = True
  for a in A:
    while a > 1:
      d = D[a]
      while a%d == 0:
        a //= d
      if C[d]:
        is_pairwise = False
      C[d] += 1
  if max(C) == n:
    print("not coprime")
  else:
    if is_pairwise:
      print("pairwise coprime")
    else:
      print("setwise coprime")
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
def main():
    n, *a, = map(int, open(0).read().split())
    m = max(a)

    d = [0] * (m + 1)
    d[1] = 1
    for i in range(2, m + 1):
        for j in range(i, m + 1, i):
            if d[j] == 0:
                d[j] = i

    def primes(x):
        ps = set()
        while x != 1:
            p = d[x]
            ps.add(p)
            x = x // d[x]
        return ps

    b = set()
    c = primes(a[0])
    f = 0
    for i in a:
        ps = primes(i)
        if f == 0:
            if b & ps:
                f = 1
            b |= ps
        c &= ps
    else:
        if f == 1 and len(c) > 0:
            f = 2
    
    ans = ["pairwise coprime", "setwise coprime", "not coprime"][f]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
input = sys.stdin.readline
def prime_factor(n):
    factors = []
    while n%2==0:
        factors.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            factors.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        factors.append(n)
    return set(factors)


n=int(input())
L=list(map(int,input().split()))
val = L[0]
for i in range(1,n):
    val=math.gcd(val,L[i])
if val!=1:
    print('not coprime')
    sys.exit()
d={}
for i in range(n):
    factors = prime_factor(L[i])
    for j in factors:
        if j not in d.keys():
            d[j]=1
        else:
            print('setwise coprime')
            sys.exit()
print('pairwise coprime')

Submission status: Accepted

Solution code:
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
n = int(input())
a = [int(x) for x in input().split() if x > '1']
if len(a) > 1:
  u = set()
  i = None
  for x in a:
    s = set()
    while x > 1:
      p = spf[x]
      if p in u:
        r = 'setwise'
      s.add(p)
      x //= p
    u |= s
    if len(a) == n:
      if i is None: i = s
      else: i &= s
  if i:
    r = 'not'
print(r, 'coprime')

Submission status: Accepted

Solution code:
import math
N=int(input())
m=10**6+1
M=[0]*m
g=0
for i in map(int,input().split()):M[i]+=1;g=math.gcd(g,i)
if g>1:print('not coprime')
elif all(sum(M[i::i])<=1 for i in range(2,m)):print('pairwise coprime')
else:print('setwise coprime')

Submission status: Accepted

Solution code:
from collections import defaultdict

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

INF = 10**6

def min_primes(n):
  ret = [i for i in range(n+1)]
  for i in range(2, int(n**0.5)+1):
    if ret[i] < i:
      continue
    for j in range(i, n+1, i):
      ret[j] = min(i, ret[j])
  return ret

D = min_primes(INF)
Ps = defaultdict(int)

def fact(x):
  Ps[D[x]] += 1
  pre = x
  x //= D[x]
  while x > 1:
    if D[x] > D[pre]:
      Ps[D[x]] += 1
    pre = x
    x //= D[x]

for a in A:
  fact(a)

Ps[1] = 1
ans = max(Ps.values())

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

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**18
def solve(N,A):
    P = set()

    for i in range(N):
        n = A[i]
        if n % 2 == 0 and 2 in P: break
        while n % 2 == 0:
            P.add(2)
            n //= 2
            
        f = 3
        while f * f <= n:
            if n % f == 0:
                if f in P: break
                P.add(f)
                while n%f == 0:
                    n //= f
            else:
                f += 2
        else:
            if n != 1:
                if n in P: break
                P.add(n)
            
            continue
        break
    else:
        return 0
        
    return 1 



def main():
    N=ii()
    A=np.array(list(mi()))

    flag = solve(N,A)
    if flag == 0:
        print("pairwise coprime")
    else:
        gcd = np.gcd.reduce(A)
        if gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")
       

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('solve', '(i8,i8[:])')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**18
def solve(N,A):
    P = set()

    fl = True
    for i in range(N):
        n = A[i]
        if n % 2 == 0 and 2 in P: 
            fl = False
            break
        while n % 2 == 0:
            P.add(2)
            n //= 2
            
        f = 3
        while f * f <= n:
            if n % f == 0:
                if f in P: 
                    fl = False
                    break
                
                P.add(f)
                while n % f == 0:
                    n //= f
            else:
                f += 2

        if n != 1:
            if n in P:
                fl = False
                break
            P.add(n)
            
        if not fl:
            break

        
    return fl



def main():
    N=ii()
    A=np.array(list(mi()))

    flag = solve(N,A)
    if flag:
        print("pairwise coprime")
    else:
        gcd = np.gcd.reduce(A)
        if gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")
       

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('solve', '(i8,i8[:])')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()

Submission status: Accepted

Solution code:
import numpy as np
#入力
N = int(input())
A = list(map(int, input().split()))
#カウンターテーブルの用意
count=[0]*(1000001)
for a in A:count[a]+= 1

#全体のgcdが1でないならnot coprime
if np.gcd.reduce(A)!=1:
    print("not coprime")
#A[x] % i == 0 && A[y] % i == 0 となるx, y が存在しないならpairwise coprime
elif np.all([sum(count[i::i])<=1 for i in range(2,10**6+1)]):
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Accepted

Solution code:
def main():
    from math import gcd
    _ = int(input())
    A = [int(i) for i in input().split()]

    def prime_factorize(n):
        for i in range(2, n+1):
            if i*i > n:
                break
            if n % i != 0:
                continue
            while n % i == 0:
                n //= i
            B[i] += 1
        if n != 1:
            B[n] += 1

    # 10**6 以下の素数は78498個しかない
    # よって，1以外の数がこれより多ければpairwiseにはならない
    check = True if sum(a != 1 for a in A) <= 80000 else False
    maxA = max(A)
    B = [0] * (maxA + 1)
    if check:
        for a in A:
            prime_factorize(a)

    g = A[0]
    for a in A:
        g = gcd(g, a)

    if g != 1:
        print("not coprime")
    elif check and max(B) <= 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd

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

# setwise validation
tmp = 0
for a in A:
    tmp = gcd(tmp, a)
isSetwise = (tmp == 1)

# pairwise validation
M = 10 ** 6
sieve = [0] * (M + 1)
for a in A:
    sieve[a] += 1

cnt = 0
isPairwise = True
for i in range(2, M + 1):
    isPairwise &= (sum(sieve[j] for j in range(i, M + 1, i)) <= 1)

# check
if isPairwise:
    ans = 'pairwise coprime'
elif isSetwise:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

Submission status: Accepted

Solution code:
import math


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return set(a)


n = int(input())
a = list(map(int, input().split()))
num = a[0]
for i in range(1, n):
    num = math.gcd(num, a[i])
if num != 1:
    print("not coprime")
    exit()
prime_memo = {}
for i in range(n):
    prime_number = prime_factorize(a[i])
    for num in prime_number:
        if num not in prime_memo.keys():
            prime_memo[num] = 1
        else:
            print("setwise coprime")
            exit()
print("pairwise coprime")

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

# Nまでの数の最小素因数を列挙
def smallest_prime_factors(N):
    spf = [i for i in range(N+1)]
    spf[0] = 0
    spf[1] = 1
    for i in range(2, N+1):
        # 素数のとき
        if spf[i] == i:
            j = i ** 2
            while (j <= N):
                # spfがまだ決まっていないなら
                if (spf[j] == j):
                    spf[j] = i
                j += i

    return spf

# 複数クエリに対する高速素因数分解
# spf配列を用いる（Q<=10**5, A[i]<=10**6程度）
# 出力は，[[(素因数,指数),...,(素因数,指数)],...,[(素因数,指数),...,(素因数,指数)]]
def fast_factorization(A, spf):
    ans = []
    for i in range(len(A)):
        dict = defaultdict(int)
        if A[i] == 1:
            dict[1] = 1
        else:
            x = A[i]
            while (x != 1):
                dict[spf[x]] += 1
                x //= spf[x]
        ans.append(list(dict.items()))
    return ans

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

spf = smallest_prime_factors(10**6)
f = fast_factorization(A, spf)

Primes = set()
SC = set()
sc_flag = 0
count = 0
first = 1
for ff in f:
    tmp = set()
    for fff in ff:
        if fff[0] != 1:
            Primes.add(fff[0])
            count += 1
            tmp.add(fff[0])
        else:
            sc_flag = 1
    if first == 1:
        SC = tmp
    else:
        SC = SC.intersection(tmp)
    first = 0

if len(Primes) == count:
    print("pairwise coprime")
elif sc_flag == 1 or len(SC) == 0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

import itertools
import collections

def prime_factor_table(n):
    table = [0] * (n + 1)
    
    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i
    
    return table

def prime_factor(n, prime_factor_table):
    prime_count = collections.Counter()
    
    while prime_factor_table[n] != 0:
        prime_count[prime_factor_table[n]] += 1
        n //= prime_factor_table[n]
    prime_count[n] += 1
    
    return prime_count

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

# pairwise coprime -> それぞれがすべて互いに素
# setwise coprime -> 互いに素でないのは混じっているが全体のgcdは1

if gcd_list(a) != 1:
    print("not coprime")
    exit()

pft = prime_factor_table(10**6)
pf = [0]*(10**6+1)

for i in a:
    if i == 1:
        continue
    # print(prime_factor(i, pft).keys())
    for j in prime_factor(i, pft).keys():
        if pf[j] == 1:
            print("setwise coprime")
            exit()
        pf[j] += 1

print("pairwise coprime")