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:
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, n+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: Accepted

Solution code:
import math

INF=float('inf')
ans1='pairwise coprime'
ans2='setwise coprime'
ans3='not coprime'

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

P=[0]*(10**6+1)
for i in A:
  P[i]+=1

pairwise=True
for i in range(2,10**6+1):
  cnt=0
  for j in range(i,10**6+1,i):
    cnt+=P[j]
  if cnt>1:
    pairwise=False
    break

if pairwise:
  print(ans1)
  exit()
  
g=math.gcd(A[0],A[1])
for i in A:
  g=math.gcd(g,i)

if g==1:
  print(ans2)
else:
  print(ans3)

Submission status: Accepted

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

ga = a[0]
for i in range(n):
  ga = math.gcd(ga, a[i])

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

m = 1000000
b = [0]*(m+1)

for i in range(2, m):
  if b[i] != 0:
    continue
  j = 1
  while True:
    t = i * j
    if t > m:
      break
    if b[t] == 0:
      b[t] = i
    j += 1

d = {}
for i in a:
  p = i
  while p != 1:
    if p in d:
      print("setwise coprime")
      sys.exit()
    d[p] = 1
    p = int(p/b[p])
print("pairwise coprime")

Submission status: Accepted

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:
        P_list = defaultdict(int)
        while a != 1:
            x = D[a]
            P_list[x] += 1
            a //= x
        for key in P_list.keys():
            if num_list[key] != 0:
                print('setwise coprime')
                exit()
            num_list[key] = 1

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Accepted

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
    judge = [i for i in range(n+1)]
    
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
                judge[j] = i

    return judge


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:
    while v > 1:
        d = l[v]

        if used[d]:
            flag = False
        else:
            used[d] = True
        
        while v % d == 0:
            v //= d

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

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

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

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce

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

max_a = max(a)
d = list(range(max_a+1))
for i in range(2, int(max_a**0.5)+1):
    if d[i] == i:
        for k in range(2*i, max_a+1, i):
            if d[k] == k:
                d[k] = i

exist = [0] * len(d)
res = 'pairwise coprime'
for i in range(n):
    val = a[i]
    s = set()
    while val != 1:
        s.add(d[val])
        val //= d[val]

    for k in s:
        if exist[k]:
            res = 'setwise coprime'
            break
        exist[k] = 1
    else:
        continue
    break

if res == 'setwise coprime':
    if reduce(gcd, a) != 1:
        res = 'not coprime'

print(res)

Submission status: Accepted

Solution code:
from functools import lru_cache
import math

def main():
    n=int(input())
    a=list(map(int,input().split()))
    x=set()
    y=a[0]
    pair=True
    for i in a:
        if pair:
            p=set(prime_factorize(i))
            if len(x&p)>0:
                pair=False
            x|=p
        y=math.gcd(y, i)
    if pair:
        print("pairwise coprime")
    elif y==1:
        print("setwise coprime")
    else:
        print("not coprime")

# 素数リスト（エラトステネスの篩）
@lru_cache(maxsize=None)
def primes(n:int) -> list:
    '''n以下の全素数をlistで返す'''
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

# 素数判定（単純な素数判定なら十分早い。大量にやる場合はX in primesがよさそう）
@lru_cache(maxsize=None)
def is_prime(n: int) -> bool:
    '''引数nが素数であればTrue、そうでなければFalseを返す'''
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

# 素因数分解
def prime_factorize(n: int) -> list:
    '''引数nの素因数分解結果のlistを返す。'''
    arr = []
    # 2で割り続け奇数まで還元する
    while n % 2 == 0:
        arr.append(2)
        n //= 2
    # sqrt(n)までの素数で試し割
    for f in primes(int(n**0.5)):
        while n % f == 0:
            arr.append(f)
            n //= f
    if n != 1:
        arr.append(n)
    return arr

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from math import gcd
from functools import reduce
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    M = max(A)

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

    # linear sieve
    sieve = list(range(M + 1))
    primes = []
    for i in range(2, M + 1):
        if sieve[i] == i:
            primes.append(i)
        for p in primes:
            if sieve[i] < p or i * p > M:
                break
            sieve[i * p] = p

    # remove prime duplicates
    f = list(range(M + 1))
    g = [1] * (M + 1)
    for i in range(2, M + 1):
        j = 0
        for j in range(i * i, M + 1, i * i):
            g[j] = i
        f[i] = f[i // g[i]]

    # prime factorization
    used = [False] * (M + 1)
    for a in map(lambda a : f[a], A):
        while a != 1:
            p = sieve[a]
            if used[p]:
                print("setwise coprime")
                return
            used[p] = True
            a //= p
    print("pairwise coprime")
resolve()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from math import gcd
from functools import reduce
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    M = max(A)

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

    # linear sieve
    sieve = list(range(M + 1))
    primes = []
    for i in range(2, M + 1):
        if sieve[i] == i:
            primes.append(i)
        for p in primes:
            if sieve[i] < p or i * p > M:
                break
            sieve[i * p] = p

    # primes without duplicate
    f = list(range(M + 1))
    g = [1] * (M + 1)
    for i in range(2, M + 1):
        j = 0
        while j <= M:
            g[j] = i
            j += i * i
        f[i] = f[i // g[i]]

    # prime factorization
    used = [False] * (M + 1)
    for a in A:
        a = f[a]
        while a != 1:
            p = sieve[a]
            if used[p]:
                print("setwise coprime")
                return
            used[p] = True
            a //= p
    print("pairwise coprime")
resolve()

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
g=np.gcd.reduce(a)
if g>1:
    print("not coprime")
    exit()
c=[0]*(10**6+1)
for i in a:
    c[i]+=1
if np.all([sum(c[i::i])<=1 for i in range(2,10**6+1)]):
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Accepted

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

num = 10**6
li = [0]*num
for k in a:
    li[k-1] += 1

i=2
while i<=num:
    if sum([li[k*i-1] for k in range(1,num//i+1)])>1:
        break
    i+=1
else:
    print("pairwise coprime")
    sys.exit()

import math
import functools
g = functools.reduce(math.gcd,a)
if g==1:
    print("setwise coprime")
    sys.exit()

print("not coprime")

Submission status: Accepted

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():
    C = [0] * (10**6 + 1)
    max_a = 0
    for a in A:
        C[a] += 1
        max_a = max(max_a, a)
    if sum(C[2::2]) > 1: return False
    for i in range(3, 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: Accepted

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)
    max_a = 0
    for a in A:
        C[a] += 1
        max_a = max(max_a, a)
    if sum(C[2::2]) > 1: return False
    for i in range(3, 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: Accepted

Solution code:
from functools import lru_cache
import math
def main():
    n=int(input())
    a=list(map(int,input().split()))
    pair,setwise=True,True
    x,y=set(),a[0]
    for i in a:
        if pair:
            ap=set(prime_factorize(i))
            if len(x & ap) > 0:
                pair=False
            x |= ap
        y=math.gcd(y, i)
    if pair:
        print("pairwise coprime")
    elif y == 1:
        print("setwise coprime")
    else:
        print("not coprime")

def prime_factorize(n: int) -> list:
    '''引数nの素因数分解結果のlistを返す。'''
    arr = []
    # 2で割り続け奇数まで還元する
    while n % 2 == 0:
        arr.append(2)
        n //= 2
    # sqrt(n)までの素数で試し割
    for f in primes(int(n**0.5)):
        while n % f == 0:
            arr.append(f)
            n //= f
    if n != 1:
        arr.append(n)
    return arr

@lru_cache(maxsize=None)
def primes(n:int) -> list:
    '''n以下の全素数をlistで返す'''
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

@lru_cache(maxsize=None)
def is_prime(n: int) -> bool:
    '''引数nが素数であればTrue、そうでなければFalseを返す'''
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)
def calc():
  n=int(input())
  arr=list(map(int,input().split()))
  g=arr[0]
  cnt=[0]*(10**6+1)
  for val in arr:
    g=gcd(g,val)
    cnt[val]+=1
  for i in range(2,10**6+1):
    tmp=0
    for j in range(i,10**6+1,i):
      tmp+=cnt[j]
    if tmp>=2:
      break
  if i==10**6:
    print('pairwise coprime')
  elif g==1:
    print('setwise coprime')
  else:
    print('not coprime')
calc()

Submission status: Accepted

Solution code:
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

n=int(input())
arr=list(map(int,input().split()))
g=arr[0]
cnt=[0]*(10**6+1)
for val in arr:
  g=gcd(g,val)
  cnt[val]+=1
for i in range(2,10**6+1):
  tmp=0
  for j in range(i,10**6+1,i):
    tmp+=cnt[j]
  if tmp>=2:
    break
if i==10**6:
  print('pairwise coprime')
elif g==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Accepted

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

def is_pairwise():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    if sum(C[2::2]) > 1: return False
    for i in range(3, MAX_A, 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: Accepted

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

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

def solve():
    if is_pairwise(): return 'pairwise'
    if gcd_all(A) == 1: return 'setwise'
    return 'not'

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

Submission status: Accepted

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

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

def solve():
    if is_pairwise(): return 'pairwise'
    if gcd_all(A) == 1: return 'setwise'
    return 'not'

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

Submission status: Accepted

Solution code:
n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    if sum(C[2::2]) > 1: pairwise = False
    for i in range(3, MAX_A, 2):
        if sum(C[i::i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')

Submission status: Accepted

Solution code:
n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for i in range(2, MAX_A):
        if sum(C[i::i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')

Submission status: Accepted

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 = 0
        while x != 1:
            if(pri_arr[y] != pri_arr[x]):
                flg_arr[pri_arr[x]] += 1
            if flg_arr[pri_arr[x]] > 1:
                return False
            y = x
            x = x // pri_arr[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()

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(10**9)

n = int(input())
a = list(map(int, input().split()))
ma = max(a)
p = [0]*(ma + 1)

for i in a:
  p[i] += 1

pairwise = True
for i in range(2, ma+1):
  cnt = 0
  for j in range(i, ma+1, i):
    cnt += p[j]
  if cnt > 1:
    pairwise = False
    break
    
if pairwise:
  print("pairwise coprime")
else:
  temp = a[0]
  for i in a:
    temp = math.gcd(temp, i)
  if temp == 1:
    print("setwise coprime")
  else:
    print("not coprime")

Submission status: Accepted

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split()))



    def get_primenumber(number):  # エラトステネスの篩
        prime_list = []
        search_list = list(range(2, number + 1))
        # search_listの先頭の値が√nの値を超えたら終了
        while search_list[0] <= math.sqrt(number):
            # search_listの先頭の値が√nの値を超えたら終了
            # search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
            head_num = search_list.pop(0)
            prime_list.append(head_num)
            # head_numの倍数を除去
            search_list = [num for num in search_list if num % head_num != 0]
        # prime_listにsearch_listを結合
        prime_list.extend(search_list)
        return prime_list


    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

    table = prime_factor_table(10**6+10)

    numset = set()
    for i in A:
        thedic = prime_factor(i, table)
        for l in thedic.keys():
            flag = True
            if l in numset and l != 1:
                flag = False
                break
        if flag:
            tmpset = set(thedic.keys())
            numset |= tmpset
        else:
            break
    if flag:
        print('pairwise coprime')
        sys.exit()
    else:
        flag = True
        theset = set(prime_factor(A[0], table).keys())
        for i in A[1:]:
            thedic = prime_factor(i, table)
            theset = theset & set(thedic.keys())
            if len(theset) == 0:
                print('setwise coprime')
                flag = False
                break
    if flag:
        print('not coprime')



if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()

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

    all_gcd = A[0]
    max_num = A[0]
    for a in A:
        all_gcd = gcd(all_gcd, a)
        max_num = max(max_num, a)
    if all_gcd != 1:
        print("not coprime")
        return

    # エラトステネスの篩でmin_prime[i] = (iを割り切る最小の素数)を記録する
    min_prime = [i for i in range(max_num + 1)]
    for p in range(2, int(max_num**0.5) + 1):
        if min_prime[p] != p: continue
        for i in range(2 * p, max_num + 1, p): min_prime[i] = p

    # Aの要素で出てきた素因数をusedに記録
    used = [0] * (max_num + 1)
    for a in A:
        while a > 1:
            p = min_prime[a]
            if used[p]:
                print("setwise coprime")
                return
            while a % p == 0: a //= p
            used[p] = 1
    print("pairwise coprime")




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()

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

    all_gcd = A[0]
    max_num = A[0]
    for a in A:
        all_gcd = gcd(all_gcd, a)
        max_num = max(max_num, a)
    if all_gcd != 1:
        print("not coprime")
        return

    # エラトステネスの篩でprimes[i] = (iを割り切る最小の素数)を記録する
    min_prime = [i for i in range(max_num + 1)]
    for p in range(2, int(max_num**0.5) + 1):
        if min_prime[p] != p: continue
        for i in range(2, max_num // p + 1): min_prime[i * p] = p

    used = [0] * (max_num + 1)
    for a in A:
        while a > 1:
            p = min_prime[a]
            if used[p]:
                print("setwise coprime")
                return
            while a % p == 0: a //= p
            used[p] = 1
    print("pairwise coprime")




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
M = max(a)+1
if M == 2:
    print("pairwise coprime")
    exit()
count = [0]*(M)
prime = [2,3,5,7,11,13]
for i in range(14,int(M**0.5)+2):
    check = True
    for j in prime:
        if i%j == 0:
            check = False
            break
    if check:
        prime.append(i)
 
for i in a:
    for j in prime:
        if i < j:
            break
        if i%j==0:
            while i%j == 0:
                i //= j
            count[j] += 1
    if i > 1:
        count[i] += 1
 
ans = max(count)
 
if ans == 1:
    print("pairwise coprime")
elif ans == n:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Accepted

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

M = 10**6

import math

setwise = A[0]
for i in range(1,N):
    setwise = math.gcd(setwise,A[i])
    
PrimeFactorss = [[] for _ in range(M+1)]
for i in range(2, M+1):
    if len(PrimeFactorss[i]) == 0:
        for x in range(i, M+1, i):
            PrimeFactorss[x].append(i)
num_list = [0]*(M+1)

for i in range(N):
    num_list[A[i]] += 1

pairwise = [0]*(M+1)

n=M
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

for i in primes:
    for j in range(i,M+1,i):
        if num_list[j]==1:
            pairwise[i] += 1
        
ans = 0    
for i in pairwise:
    if i>1:
        ans += 1
        break
    
if setwise == 1 and ans == 0:
    print("pairwise coprime")
elif setwise == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))
f = [0]*10**7
def fctr_d(n):
    c = 0
    r = int(n**0.5)
    for i in range(2, r+2):
        while n % i == 0:
            c += 1
            n = n//i
        if c != 0:
            if f[i] != 0:
                return False
            else:
                f[i] = True
                c = 0
    if n != 1:
        if f[n] != 0:
            return False
        else:
            f[n] = True
    return True


pairwise_flag = True
for i in range(n):
    m = a[i]
    if not fctr_d(m):
        pairwise_flag = False
        break

setwise_flag = True
gcd = a[0]
for i in range(1, n):
    gcd = math.gcd(gcd, a[i])
if gcd != 1:
    setwise_flag = False

if pairwise_flag:
    print("pairwise coprime")
else:
    if setwise_flag:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
from collections import Counter
def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a
n = int(input())
input_list = list(map(int,input().split()))
num_count = Counter([prime for num in input_list for prime in prime_factorize(num)])
if len(num_count.values())==0:
    print("pairwise coprime")
    exit()
max_appear = max(num_count.values())
if max_appear == 1:
    print("pairwise coprime")
elif max_appear != n:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D, A_max):
    p_count = [0] * (A_max + 1)
    for A in A_list:
        temp = A
        d = 0
        while temp != 1:
            if p_count[D[temp]] == 1 and d != D[temp]:
                return 0
            p_count[D[temp]] = 1
            d = D[temp]
            temp = temp // D[temp]
    return 1

## 標準入力
N = int(input())
A_list = list(map(int, input().split(" ")))

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D, A_max) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Accepted

Solution code:
from math import gcd

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        d = 0
        while temp != 1:
            if p_count[D[temp]] == 1 and d != D[temp]:
                return 0
            p_count[D[temp]] = 1
            d = D[temp]
            temp = temp // D[temp]
    return 1

## 標準入力
N = int(input())
A_list = list(map(int, input().split(" ")))

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Accepted

Solution code:
from math import gcd
import numpy as np

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        d = 0
        while temp != 1:
            if p_count[D[temp]] == 1 and d != D[temp]:
                return 0
            p_count[D[temp]] = 1
            d = D[temp]
            temp = temp // D[temp]
    return 1

## 標準入力
N = int(input())
A_list = list(map(int, input().split(" ")))

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Accepted

Solution code:
import math


def primes(N):
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N ** 0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    return [i for i in range(N + 1) if p[i]]


N = int(input())
A = list(map(int, input().split()))
maxA = max(A) + 1
g, Ac = A[0], [0] * maxA
P = primes(maxA)

for a in A:
    Ac[a] += 1

ans = "pairwise"
for p in P:
    if sum(Ac[p:maxA:p]) > 1:
        ans = "setwise"
for a in A:
    g = math.gcd(g, a)
print(ans if g == 1 else "not", "coprime")