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 math import gcd
n = int(input())
A = list(map(int, input().split()))

f1 = True
f2 = True

c = [0] * (10**6+5)
for a in A:
  c[a] += 1
for i in range(2, 10**6+5):
  cnt = 0
  for j in range(i, 10**6+5, i):
    cnt += c[j]
  if cnt > 1:
    f1 = False


g = 0
for i in range(len(A)):
  g = gcd(g, A[i])
if g != 1:
  f2 = False

if f1:
  print("pairwise coprime")
elif f2:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Accepted

Solution code:
N=int(input())
from math import gcd
from functools import reduce
l=list(map(int,input().split()))
sw=0
c=[0]*1000001
for i in l:
   c[i]+=1
if all(sum(c[i::i])<=1 for i in range(2,1000001)):
  print("pairwise coprime")
elif reduce(gcd,l)==1:
   print("setwise coprime")
else:
   print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce

n = int(input())
A = list(map(int, input().split()))
res = ['pairwise coprime', 'setwise coprime', 'not coprime']

MAX = 10 ** 6 + 1000
dp = [i for i in range(MAX)]
# dp[x]はxを割り切る最小の素数
for x in range(2, MAX):
    if dp[x] < x: continue
    for y in range(x + x, MAX, x):
        if dp[y] == y:
            dp[y] = x

def get_factor(n):
    factors = []
    while n > 1:
        factors.append(dp[n])
        n //= dp[n]
    return factors

prime_factors = []
for a in A:
    factor = get_factor(a)
    factor_set = list(set(factor))
    prime_factors.extend(factor_set)

if len(prime_factors) == len(set(prime_factors)):
    print(res[0])
elif reduce(gcd, A) == 1:
    print(res[1])
else:
    print(res[2])

Submission status: Accepted

Solution code:
import math

def eratosthenes():
    erat = [0 for _ in range(max_a+1)]
    #lim = int(math.sqrt(max_a))
    pair = True
    #for i in range(2, lim+1):
    for i in range(2, max_a+1):
        cnt = 0
        if not erat[i]:
            for res in range(i, max_a+1, i):
                if res in set_a:
                    cnt += 1
                erat[res] = i
                if cnt > 1:
                    pair = False
                    break
        if not pair:
            break
    return pair


n = int(input())
a = [int(x) for x in input().split()]
max_a = max(a)
set_a = set(a)

if eratosthenes() and len(set_a) == n - max(0, a.count(1)-1):
    print('pairwise coprime')
else:
    res = a[0]
    for i in range(n):
        res = math.gcd(res, a[i])
    if res == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from math import gcd

N = int(input())
A = list(map(int, input().split()))
era = [-1]*(10**6+1)

for i in range(2, 10**6+1):
    if era[i]==-1:
        era[i] = i

        for j in range(2*i, 10**6+1, i):
            if era[j]==-1:
                era[j] = i

s = set()
flag = True

for Ai in A:
    f = []
    t = Ai
    
    while t>1:
        f.append(era[t])
        t //= era[t]
    
    for fi in f:
        if fi in s:
            flag = False
    
    for fi in f:
        s.add(fi)

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

G = 0

for Ai in A:
    G = gcd(G, Ai)

if G==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)    

table = [0] * (10**6+5)

pairwise_flg = True
for num in A:
    table[num] += 1

for i in range(2, 10**6+5):
    cnt = 0
    for j in range(i, 10**6+5, i):
        cnt += table[j]
    if cnt > 1:
        pairwise_flg = False    
if pairwise_flg:
    print("pairwise coprime")
    exit()

gcd_val = 0
for num in A:
    gcd_val = gcd(gcd_val, num)

if gcd_val == 1:
    print("setwise coprime")
    exit()
print("not coprime")

Submission status: Accepted

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

def soinsuu(n):
    visited=defaultdict(int)
    for i in range(2,round(n**.5)+1):
        while n%i==0:
            n//=i
            visited[i]+=1
    if n>1:
        visited[n]+=1
    return(visited)

N=int(input())
A=list(map(int,input().split()))
visited=set()
flg=False
for a in A:
    for i in soinsuu(a):
        if i in visited:
            flg=True
            break
        else:
            visited.add(i)

    if flg:
        break
else:
    print("pairwise coprime")
    exit()

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



if n>1:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from math import sqrt
from collections import Counter

def gen_primes(X):
    D = [0] * (X+1)
    is_prime = [True for _ in range(0, X+1)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for n in range(2, int(sqrt(X))+1):
        if is_prime[n]:
            primes.append(n)
            j = n*2
            D[n] = n
            while j <= X:
                is_prime[j] = False
                if D[j] == 0:
                    D[j] = n
                j += n
    for n in range(int(sqrt(X)), X+1):
        if is_prime[n]:
            D[n] = n
            primes.append(n)
    return primes, D


def solve(A):
    N = len(A)
    primes, D = gen_primes(10**6)
    C = [0] * (primes[-1]+1)

    for a in A:
        a_ = a
        while a > 1:
            d = D[a]
            while a % d == 0:
                a //= d
            C[d] += 1
        
    M = max(C)
    if M <= 1:
        print("pairwise coprime")
    elif M != N:
        print("setwise coprime")
    else:
        print("not coprime")

#solve([x for x in range(1, 10**6+1)])
N = int(input())
A = [int(x) for x in input().split()]
solve(A)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

M = 10**6
P = [0]*(M+1)
for i in range(2, M+1):
    if P[i] == 1:
        continue
    P[i] = -1
    j = 2*i
    while j <= M:
        P[j] = 1
        j += i

L = [0]*(M+1)
for a in A:
    L[a] += 1

num = 0
for i in range(2, M+1):
    if P[i] > -1:
        continue
    cnt = 0
    j = i
    while j <= M:
        cnt += L[j]
        j += i
    num = max(num, cnt)


if num == 1 or max(A) == 1:
    print("pairwise coprime")
elif num == N:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Accepted

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

c = [0]*(10**6 + 3)
for i in a:
    c[i] += 1

pairwise = True
for i in range(2,10**6+1):
    if sum(c[::i])>1:
        pairwise = False

g = 0
for i in a:
    g = math.gcd(g,i)
if g == 1:
    setwise = True
else:
    setwise = False

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

Submission status: Accepted

Solution code:
from sys import stdin

input = stdin.readline
import math

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

    cur = 0
    for i in a:
        cur = math.gcd(i, cur)
    if cur > 1:
        print('not coprime')
        return
    m = max(a)
    prime = [True] * (m+1)
    c = {}
    for i in a:
        c[i] = c.get(i,0) + 1
    for i in range(2,m+1):
        if prime[i]:
            cnt = 0
            for j in range(i,m+1,i):
                prime[j] = False
                cnt += c.get(j,0)
                if cnt > 1:
                    print('setwise coprime')
                    return
    print('pairwise coprime')
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

MAX = max(A)

# remap
AR = [0] * (MAX+1)
V = [False] * (MAX+1)
for i in range(N): AR[A[i]] += 1
pairwise, setwise = True, True

# sieve
for i in range(2, MAX+1):
    if V[i]: continue
    cnt, j = 0, i
    while j < MAX+1:
        cnt += AR[j]
        V[j] = True
        j += i
    if cnt > 1: pairwise = False
    if cnt == len(A): setwise = False

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

# エラトステネスの篩
#############################################################
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
#############################################################

# 素因数分解、リストで返す
#############################################################
def prime_factorize(n, prime_list):
    a = []
    for p in prime_list:
        if p * p > n:
            break
        while True:
            if n % p == 0:
                a.append(p)
                n //= p
            else:
                break
    if n != 1:
        a.append(n)
    a.sort()
    return a
#############################################################


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

data = set(get_sieve_of_eratosthenes(10**6))

primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i], data)
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

# print(primes)

if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

"""
コーナーケース１:
    重複があるとき　not coprime(※これが誤り)
    ただし、1の重複は除く

コーナーケース:
    重複があるとき　pairwise coprime ではない
    setwise coprimeの可能性はある
    ただし、１の重複は
"""
import math
C = 10**6
#T = int(math.sqrt(C)*10**3)+1
N = int(input())
judge = [0]+[False]*C
A =list()
f = True
for a in input().split():
    if judge[int(a)] == True and int(a) != 1:
        f = False
    judge[int(a)]=True
    A.append(int(a))
d = [False]+[True]*C

#print(judge[:10])
def solve(f):
    flag = True
    #エラトステネスの篩 O(N log N)
    for i in range(2,C+1):
        count = 0
        if d[i] == True:
            for j in range(i,C+1,i):
                if judge[j] == True:
                    count += 1
                if count == 2:
                    flag = False
                    break
                d[j] = False
        if not flag:
            break
    
    if flag == True and f == True:
        return "pairwise coprime"
    ans = A[0]
    #線形探索 O(N)
    for i in range(N):
        ans = math.gcd(ans,A[i])
    #print("ans",a)
    if ans == 1:
        return "setwise coprime"
    return "not coprime"

print(solve(f))
#print(len(A))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 07:10:00 2020

@author: liang
"""


# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

"""
コーナーケース１:
    重複があるとき　not coprime
    ただし、1の重複は除く
"""
import math
C = 10**6
N = int(input())
judge = [False]*(C+1)
A = [int(x) for x in input().split()]

f = True
for a in A:
    if judge[a] == True and a != 1:
        f = False
    judge[int(a)]=True


#print(judge[:10])
def solve(f):
    
    ans = A[0]
    #線形探索 O(N)
    for i in range(N):
        ans = math.gcd(ans,A[i])
    #print("ans",a)
    if ans != 1:
        return "not coprime"
    
    flag = True
    #エラトステネスの篩 O(N log N)
    for i in range(2,C+1):
        count = 0
       #if d[i] == True:
        for j in range(i,C+1,i):
            if judge[j] == True:
                count += 1
            if count == 2:
                flag = False
                break
        #        d[j] = False
        if not flag:
            break
    
    if flag == True and f == True:
        return "pairwise coprime"
    
    return "setwise coprime"

print(solve(f))
#print(len(A))

Submission status: Accepted

Solution code:
from sys import exit

def gcd(x,y):
    if x == 0: return y
    else: return gcd(y%x,x)


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

is_prime = [True]*(10**6+10)
is_prime[0] = False
is_prime[1] = False

for i in range(2,10**6+10):
    if not is_prime[i]:
        continue
    else:
        for j in range(i*i,10**6+10,i):
            is_prime[j] = False

g = 0
for i in A:
    g = gcd(g,i)

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

prime = [p for p in A if is_prime[p]]
used = [False]*(10**6+10)
notprime = [np for np in A if not is_prime[np]]
small_prime = [p for p in range(10**3+10) if is_prime[p]]


for p in prime:
    used[p] = True

for np in notprime:
    for p in small_prime:
        if np == 1: break
        if np % p != 0: continue
        if used[p]:
            print("setwise coprime")
            exit(0)
        used[p] = True
        while np % p == 0:
            np //= p
    if np > 1:
        if used[np]:
            print("setwise coprime")
            exit(0)
        used[np] = True

print("pairwise coprime")

Submission status: Accepted

Solution code:
import sys
import re
import queue
import collections
import math
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

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

def main():
	N = i_input()
	A = i_list()

	d = dict()

	max_A = max(A)
	count_list = []

	MAXN = 10**6+10
	sieve = [i for i in range(MAXN+1)]
	p = 2
	while p*p <= MAXN:
		if sieve[p] == p:
			for q in range(2*p,MAXN+1,p):
				if sieve[q] == q:
					sieve[q] = p
		p += 1


	for i in range(0,max(A)):
		count_list.append(0)

	for a in A:
		tmp = set()
		while a > 1:
			tmp.add(sieve[a])
			a //= sieve[a]

		for p in tmp:
			count_list[p-1] += 1


	if (max(count_list)<=1):
		print("pairwise coprime")
	elif(gcd_list(A)==1):
		print("setwise coprime")
	else:
		print("not coprime")

	return

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import math

N = int(input())
a = list(map(int,input().split()))
m = max(a)
c = [0] * (m+1)

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

pairwise = True
for i in range(2, m+1, 1):
  cnt = 0
  for j in range(i, m+1, i):
    cnt += c[j]
    if cnt > 1:
      pairwise = False
      break
if pairwise:
  print("pairwise coprime")
  exit()

g = 0
for i in range(N):
  g = math.gcd(g, a[i])
if g == 1:
  print("setwise coprime")
  exit()

print("not coprime")

Submission status: Accepted

Solution code:
def gcc(x, y):
    if x == 0:return y
    return gcc(y % x, x)

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

g = 0

A.sort()

for item in A:
    g = gcc(g, item)

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

primes = []
is_prime = [True] * 1100000

is_prime[0] = is_prime[1] = False

for i in range(2, 1100000):
    if not is_prime[i]:continue
    for j in range(i*i, 1100000, i):
        is_prime[j] = False
    primes.append(i)

A_prime = [item for item in A if is_prime[item]]
A_notprime = [item for item in A if not is_prime[item]]

used = [False] * 1100000

for item in A_prime:
    used[item] = True

for a in A_notprime:
    for p in primes:
        if a == 1:break
        if a % p != 0:continue

        if used[p]:
            print("setwise coprime")
            #互いに素でない（共通素因数pで割れる）ペアがAの中にあると，それはsetwise_coprime
            exit()

        used[p] = True

        while a % p == 0:
            a //= p

print("pairwise coprime")

Submission status: Accepted

Solution code:
def gcc(x, y):
    if x == 0:return y
    return gcc(y % x, x)

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

g = 0

A.sort()

for item in A:
    g = gcc(g, item)

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

primes = []

is_prime = [True] * 1100000

is_prime[0] = is_prime[1] = False

for i in range(2, 1100000):
    if not is_prime[i]:continue
    for j in range(i*i, 1100000, i):
        is_prime[j] = False

A_prime = [item for item in A if is_prime[item]]
A_notprime = [item for item in A if not is_prime[item]]

primes = [p for p in range(1100) if is_prime[p]]
used = [False] * 1100000

for item in A_prime:
    used[item] = True

for a in A_notprime:
    for p in primes:
        if a == 1:break
        if a % p != 0:continue

        if used[p]:
            print("setwise coprime")
            #互いに素でない（共通素因数pで割れる）ペアがAの中にあると，それはsetwise_coprime
            exit()

        used[p] = True

        while a % p == 0:
            a //= p

    if a > 1:
        if used[a]:
            print("setwise coprime")
            exit()
        used[a] = True


print("pairwise coprime")

Submission status: Accepted

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

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

c = [0]*(10**6 + 3)
for i in a:
    c[i] += 1

pairwise = True
for i in range(2,10**6+1):
    if sum(c[::i])>1:
        pairwise = False

g = 0
for i in a:
    g = gcd(g,i)
if g == 1:
    setwise = True
else:
    setwise = False

if pairwise == True:
    print("pairwise coprime")
    exit()
if setwise == True:
    print("setwise coprime")
    exit()
print("not coprime")

Submission status: Accepted

Solution code:
from math import sqrt, gcd
import sys


def osk_a(M):
    p = [i for i in range(M+1)]
    for x in range(2, int(sqrt(M))+1):
        if p[x] == x:
            for y in range(2*x, M+1, x):
                if p[y] == y:
                    p[y] = x
    return p


def main():
    n = int(sys.stdin.buffer.readline())
    a = list(map(int, sys.stdin.buffer.readline().split()))

    def g(a):
        g = 0
        for x in a:
            g = gcd(g, x)
        return g

    if g(a) > 1:
        print("not coprime")
        exit()
    p = osk_a(10**6)
    chk = set()
    while a[0] > 1:
        chk.add(p[a[0]])
        a[0] //= p[a[0]]
    for x in a[1:]:
        tmp = set()
        while x > 1:
            tmp.add(p[x])
            x //= p[x]
        if not chk.isdisjoint(tmp):
            print("setwise coprime")
            exit()
        chk |= tmp
    print("pairwise coprime")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
A=max(a)
l=[i for i in range(A+1)]
for i in range(2,A+1):
  if l[i]==i:
    for j in range(1,A//i+1):
      if i*j<=A:
        l[i*j]=i

L=set()
f=0
for i in range(n):
  x=a[i]
  L2=set()
  while x!=1:
    L2.add(l[x])
    x//=l[x]
  L2=list(L2)
  for j in range(len(L2)):
    if L2[j] in L:
      f=1
    else:
      L.add(L2[j])
  if f==1:
    break
if f==0:
  print('pairwise coprime')
  exit()

y=a[0]
for i in range(1,n):
  y=math.gcd(y,a[i])
if y==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Accepted

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
ans1 = "pairwise coprime"
ans2 = "setwise coprime"
ans3 = "not coprime"

a = math.gcd(A[0], A[1])
for i in range(2, N):
    a = math.gcd(a, A[i])

if a==1:
    b = True
    l = [0]*(10**6+1)
    x = [0]*(10**6+1)
    x[0]=1
    x[1]=1
    for i in range(2, 10**6+1):
        if x[i]==0:
            for j in range(i, 10**6+1, i):
                x[j]=i

    for y in A:
        s=set()
        if y==1:
            continue
        elif y==x[y]:
            s |= {y}        #素因数のリスト
        else:
            while y!=x[y]: #素数になるまで
                s|={x[y]}  
                y//=x[y]
                if y==x[y]:
                    s|={x[y]}
                    break
        for i in s:
            l[i]+=1
            if l[i]>=2:
                b=False
                break
                
        
    if b:
        print(ans1)
    else:
        print(ans2)
        
        
    
else:
    print(ans3)

Submission status: Accepted

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


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

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


n = I()
a = LI()

mx = max(a)
table = [0] * (mx + 1) # num of factors
for x in a:
  table[x] += 1
g = 0
# check 
for x in a:
  g = gcd(g, x)
for i in range(2, mx + 1):
  c = 0
#　因数iの倍数がaにいくつ含まれるか(c)
  for j in range(i, mx + 1, i):
    c += table[j]
# cが2以上=iの倍数となるaが複数存在する
  if c > 1:
    if g == 1:
      print("setwise coprime")
    else:
      print("not coprime")
    exit(0)
print("pairwise coprime")

Submission status: Accepted

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

num = [0]*(10**6+1)

for x in a:
    num[x] += 1

f = 1
for i in range(2, 10**6+1):
    s = sum(num[i::i])
    if s == n:
        print("not coprime")
        exit()
    if s > 1 :
        f = 0
if f == 0:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Accepted

Solution code:
def f1(n):
    max_p = int(n ** 0.5)
    p = 0  # 素数
    pl = []  # 素数リスト
    el = [i for i in range(2, n + 1)]  # 探索リスト
    D = [i for i in range(n + 1)]
    while p <= max_p:
        nxt = []
        p = el[0]
        pl.append(p)
        for e in el:
            if e % p == 0:
                D[e] = p
            else:
                nxt.append(e)
        el = nxt
    for e in el:
        D[e] = e
    pl.extend(el)
    return D, pl


def f2(n, D):
    s = set()
    x = n
    while x > 1:
        p = D[x]
        s.add(p)
        x = x // p
    return s


from math import gcd


def is_nc(n, al):
    g = al[0]
    for i, a in enumerate(al):
        if i == 0:
            continue
        else:
            g = gcd(g, a)
            if g == 1:
                return False
    return True


def is_sc(n, al):
    max_al = max(al)
    if max_al == 1:
        return False
    D, pl = f1(max_al)
    count = {p: 0 for p in pl}
    for a in al:
        p_s = f2(a, D)
        for p in p_s:
            if count[p] == 1:
                return True
            else:
                count[p] += 1
    return False


n = int(input())
al = list(map(int, input().split()))
if is_nc(n, al):
    print('not coprime')
elif is_sc(n, al):
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Accepted

Solution code:
from math import gcd

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

# 解説AC(a*loga)
ans = 0
cnt = [0] * (max(a) + 1)
for ai in a:
    ans = gcd(ans, ai)
    cnt[ai] += 1

if ans != 1:
    print('not coprime')
elif any(sum(cnt[i::i]) > 1 for i in range(2, max(a) + 1)):
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Accepted

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
import random
J=int(1e9)+7

###############################################################################\n=17
X=[False]*(10**6+1)
P=[]
for i in range(2,len(X)):
    if X[i] is False:
        for j in range(2*i,len(X),i):
            X[j]=True
for i in range(2,len(X)):
    if X[i] is False:
        P.append(i)


n=int(input())
A=INPUT()
ans=0
V=[0]*(10**6+1)
for i in range(n):
    ans=math.gcd(ans,A[i])
    V[A[i]]+=1
if ans==1:
    bool=True
    for i in range(2,10**6+1):
        if V[i]>=2:
            bool=False
            break
    if bool:
        for ele in P:
            c=0
            for i in range(ele,10**6+1,ele):
                if V[i]>0 and i%ele==0:
                    c+=1
            if c>1:
                bool=False
                break
        if bool:
            print("pairwise coprime")
        else:
            print("setwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd

N,*A = map(int, open(0).read().split())
m = max(A)
if m == 1:
    print('pairwise coprime')
else:
    minfactor = [-1] * (m+1)
    for i in range(2,m+1):
        if minfactor[i] == -1:
            for j in range(1,m//i+1):
                minfactor[i*j] = i
    temp = gcd(A[0],A[1])
    for i in range(2,N):
        temp = gcd(temp,A[i])
        if temp == 1:
            break
    if temp > 1:
        print('not coprime')
    else:
        s = set()
        for x in A:
            if x > 1:
                p = x
                while p > 1:
                    mf = minfactor[p]
                    if mf not in s:
                        s.add(mf)
                        while p % mf == 0:
                            p = p // mf
                    else:
                        break
                else:
                    continue
                print('setwise coprime')
                break
        else:
            print('pairwise coprime')

Submission status: Accepted

Solution code:
import sys


def LI():
    return list(map(int, input().split()))


def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y % x, x)


input()
A = LI()

g = 0
for a in A:
    g = gcd(g, a)
if g != 1:
    print("not coprime")
    sys.exit()

sosudayo = [True] * 1100000
sosudayo[0] = False
sosudayo[1] = False
for i in range(2, 1100000):
    if not sosudayo[i]:
        continue
    for j in range(i*i, 1100000, i):
        sosudayo[j] = False

used = [False] * 1100000
sosu = [a for a in A if sosudayo[a]]
for i in sosu:
    used[i] = True
ruto_sosu = [a for a in range(1100) if sosudayo[a]]
not_sosu = [a for a in A if not sosudayo[a]]

for i in not_sosu:
    for j in ruto_sosu:
        if i == 1:
            break
        if i % j != 0:
            continue
        if used[j]:
            print("setwise coprime")
            sys.exit()
        used[j] = True
        while i % j == 0:
            i //= j
    if i > 1:
        if used[i]:
            print("setwise coprime")
            sys.exit()
        used[i] = True

print("pairwise coprime")

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    maxA = max(A)
    if maxA == 1:
        print('pairwise coprime')
        return
    prime = [i if i % 2 != 0 else 2 for i in range(maxA+1)]
    f = [False] * (maxA+1)
    for i in range(3, int(maxA**.5)+1):
        if prime[i] != i:
            continue
        p = i * 2
        while p <= maxA:
            if prime[p] == p:
                prime[p] = i
            p += i

    def gcd(x, y):
        if y == 0:
            return x
        return gcd(y, x % y)

    setwise_coprime = A[0]
    for An in A[1:]:
        setwise_coprime = gcd(setwise_coprime, An)
        if setwise_coprime == 1:
            break
    # print(prime)
    for An in A:
        if An == 1:
            continue
        # print('An = {}'.format(An))
        not_pairwise_coprime = False
        while prime[An] != An:
            # print('prime[An]={}, f[prime[An]]={}'.format(prime[An], f[prime[An]]))
            if f[prime[An]]:
                not_pairwise_coprime = True
                break
            f[prime[An]] = True
            prime_An = prime[An]
            while An % prime_An == 0:
                An //= prime_An
        else:
            if An != 1:
                if f[An]:
                    not_pairwise_coprime = True
                else:
                    f[An] = True
        if not_pairwise_coprime:
            break
        # print(f)
    else:
        print('pairwise coprime')
        return
    if setwise_coprime == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()