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 math

N = int(input())
A = sorted(list(map(int,input().split())))
d = [0]*(10**6+2)
d[1] = 1
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

f = 1
for e in A:
    for y in make_divisors(e):
        if y == 1:
            continue
        if d[y] != 0:
            f = 0
            break
        else:
            d[y] = 1
    if f == 0:
        break
if f == 1:
    print("pairwise coprime")
    exit(0)

t = A[0]
for e in A:
    t = math.gcd(e,t)

if t == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import sys
import math
from functools import reduce
N = str(input())
A = list(map(int, input().split()))

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

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

d = 0
for i in range(2, M+1):
    tmp = 0
    for j in range(i,M+1,i):
        tmp += sieve[j]
    if tmp > 1:
        d = 1
        break

            
if d == 0:
    print('pairwise coprime')
    exit()

if gcd(*A) == 1:
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Accepted

Solution code:
import math

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

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

is_prime = [1] * 1000001
D = [0] * 1000001

for i in range(2, 1001):
    if is_prime[i]:
        D[i] = i
        j = 2 * i
        while j <= 1000000:
            if is_prime[j]:
                D[j] = i
                is_prime[j] = 0
            j += i
for i in range(1001, 1000001):
    if is_prime[i]:
        D[i] = i

count = [0] * 1000001
for a in A:
    k = a
    pre = 0
    while k != 1:
        if pre != D[k]:
            count[D[k]] += 1
            if count[D[k]] == 2:
                print('setwise coprime')
                exit()
        pre = D[k]
        k = int(k / D[k])
print('pairwise coprime')

Submission status: Accepted

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

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

l = 10**6 + 10
B = [0] * l
for i in range(2, l):
    if B[i] == 0:
        j = 0
        while i*j < l:
            if B[i*j] == 0:
                B[i*j] = i
            j += 1

pc_ng = 0
D = [0] * l
for i in range(n):
    C = []
    a = A[i]
    while a != 1:
        C.append(B[a])
        a //= B[a]
    # print(C)
    C = list(set(C))
    for j in range(len(C)):
        if D[C[j]] == 1:
            pc_ng = 1
            break
        else:
            D[C[j]] = 1

if pc_ng == 0:
    print("pairwise coprime")
    sys.exit()

g = A[0]
from math import gcd
for i in range(1, n):
    g = gcd(g, A[i])
# print(g)

if g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
table=[0 for i in range(10**6+7)]
flag=0
for i in a:
    table[i]+=1
    
for i in range(2,10**6+1):
    cnt=0
    j=i
    while(j<10**6+1):
        cnt+=table[j]
        j+=i
    if(cnt>1):
        flag=1
        break

if(flag==1):
    tmp=a[0]
    for i in range(1,n):
        tmp=math.gcd(tmp,a[i])
    if(tmp==1):
        flag=2



if(flag==0):
    print('pairwise coprime')
    
if(flag==1):
    print('not coprime')

if(flag==2):
    print('setwise coprime')

Submission status: Accepted

Solution code:
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

####
from collections import defaultdict as ddic, Counter, deque
import heapq, bisect, itertools
MOD = 10 ** 9 + 7

def solve(N, A):
    from fractions import gcd
    g  = A[0]
    for x in A:
        g=  gcd(g,x)
    if g > 1:
        return "not coprime"

    seen = set()
    for x in A:
        saw = set()
        while x % 2 == 0:
            x //= 2
            saw.add(2)
        d = 3
        while d*d <= x:
            while x%d == 0:
                saw.add(d)
                x //= d
            d += 2
        if x > 1:
            saw.add(x)

        for p in saw:
            if p in seen:
                return "setwise coprime"
        seen |= saw

    return "pairwise coprime"

N= rri()
A = rrm()

print solve(N, A)

Submission status: Accepted

Solution code:
from math import gcd
n=int(input())
l=list(map(int,input().split()))
mal=max(l)
e=[i for i in range(mal+1)]

x=2
while x*x <= mal:
    if x == e[x]:
        for m in range(x, len(e), x):
            if e[m] == m:
                e[m] = x
    x+=1
#print(e)    
s=set()
f=0
for i in l:
  st = set()
  while i > 1:
    st.add(e[i])
    i//=e[i]
  if not s.isdisjoint(st):
    f=1
    break
  s |= st

if f==0:
    print('pairwise coprime')
    exit()
p=l[0]
for i in range(1,n):
    p=gcd(p,l[i])
if p==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import math

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

MAX = 1000005

is_prime = [1]*MAX
D = [None]*MAX
is_prime[0],is_prime[1] = 0,0

for i in range(2,MAX):
  if is_prime[i]:
    D[i] = i
    for j in range(i*2,MAX,i):
      is_prime[j] = 0
      D[j] = i
      
counts = [0]*MAX
pair = True

for a_i in a:
  if a_i == 1:
    continue
  pf = {}
  while True:
    p = D[a_i]
    if counts[p]>0:
      pair = False
    pf[p] = pf.get(p,0)+1
    if p == a_i:
      break
    else:
      a_i //= p
      
  for p in pf.keys():
    counts[p] += 1

if pair:
  print('pairwise coprime')
else:
  g = a_i
  for a_i in a:
    g = math.gcd(a_i,g)
  if g == 1:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Accepted

Solution code:
import math

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

MAX = 1000005
c = [0]*MAX

for i in range(n):
  c[a[i]] += 1

pair = True

for i in range(2,MAX):
  cnt = 0
  for j in range(i,MAX,i):
    cnt += c[j]
  if cnt > 1:
    pair = False

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

Submission status: Accepted

Solution code:
N = int(input())
A = [0]*(1000001)
for a in list(map(int, input().split())):
    A[a] += 1

# MFPF = Most Frequent Prime Factor
MFPF_n = 0
seen_prime_factor = [0]*(1000001)
for i in range(2, 1000001):
    if seen_prime_factor[i]:
        continue
    n = i
    tmp = 0
    while n < 1000001:
        tmp += A[n]
        seen_prime_factor[n] = 1
        n += i
    MFPF_n = max(MFPF_n, tmp)

if MFPF_n < 2:
    print('pairwise coprime')
elif MFPF_n - A[1] < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd

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

checker = [0 for _i in range(10**6+1)]
for i in a:
    checker[i] += 1

if all(sum(checker[i::i])<2 for i in range(2,10**6+1)):
    print('pairwise coprime')
else:
    r = a[0]
    for i in a:
        r = gcd(r, i)
    if r == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Accepted

Solution code:
import random
import math
N=int(input())
A=[int(i) for i in input().split()]
isPrime=[1 for i in range(10**6+1)]
isPrime[0]=0;isPrime[1]=0
Pfact=[[] for i in range(10**6+1)]
for i in range(10**6+1):
    if isPrime[i]==0:
        continue
    Pfact[i].append(i)
    for j in range(2*i,10**6+1,i):
        isPrime[j]=0
        Pfact[j].append(i)

Prime=[]
for i in range(10**6+1):
    if isPrime[i]:
        Prime.append(i)
def ispairwisecoprime():
    X=set()
    t=0
    for i in range(N):
        for j in Pfact[A[i]]:
            if j in X:
                return False
                exit()
            else:
                X.add(j)
    return True
if ispairwisecoprime():
    print("pairwise coprime")
else:
    G=A[0]
    for i in range(1,N):
        G=math.gcd(G,A[i])
    if G==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd

N = int(input())
A = list([int(x) for x in input().split()])

max_a = max(A)

before = 0
result = [0 for _ in range(max_a + 1)]

for i in A:
    before = gcd(before, i)
    result[i] += 1

is_pairwise = True

for i in range(2, max_a + 1):
    cnt = 0
    for j in range(i, max_a + 1, i):
        cnt += result[j]
    if cnt > 1:
        is_pairwise = False
        break

if is_pairwise:
    print('pairwise coprime')
    exit()
if before == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd


def main():
    N = int(input())
    A = list([int(x) for x in input().split()])

    max_a = max(A)

    before = 0
    result = [0 for _ in range(max_a + 1)]

    for i in A:
        before = gcd(before, i)
        result[i] += 1

    is_pairwise = True
    for i in range(2, max_a + 1):
        cnt = 0
        for j in range(i, max_a + 1, i):
            cnt += result[j]

        if cnt > 1:
            is_pairwise = False
            break

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from math import gcd

n=int(input())
a=lnii()

g=a[0]
for i in range(n):
  g=gcd(g,a[i])

def factorization(n):
    p=2
    fcr=set()
    while p*p<=n:
        while n%p==0:
            fcr.add(p)
            n//=p
        p+=1
    if n>1:
        fcr.add(n)
    return fcr

def eratosthenes(lim):
  is_p=[1]*lim

  is_p[0]=0
  is_p[1]=0

  for i in a:
    fcr=factorization(i)
    for j in fcr:
      if is_p[j]:
        for k in range(j,lim,j):
          is_p[k]=0
      else:
        if g==1:
          print('setwise coprime')
        else:
          print('not coprime')
        exit()
  return is_p

lim=10**6+1
is_p=eratosthenes(lim)

print('pairwise coprime')

Submission status: Accepted

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


def main():
    from math import gcd
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    max_a = 10 ** 6
    numbers = [0 for _ in range(max_a + 1)]

    # KeyInsight:
    # 調和級数: 計算量 O(AlogA)
    # ◯: 素因数分解をすればよいことには気がつけた。
    # △: 4ケースWA・TLEが取れず
    for ai in a:
        numbers[ai] += 1

    is_pairwise = True

    # 素因数の判定
    # 素因数の倍数の要素を数えている
    for i in range(2, max_a + 1):
        count = 0

        for j in range(i, max_a + 1, i):
            count += numbers[j]

            # 2つ以上ある数の倍数があった場合は、少なくともpairwiseではない
            if count > 1:
                is_pairwise = False

    if is_pairwise:
        print("pairwise coprime")
        exit()

    value_gcd = 0

    # 全ての要素のGCDが1かどうかを判定
    for i in range(n):
        value_gcd = gcd(value_gcd, a[i])

        if value_gcd == 1:
            print("setwise coprime")
            exit()

    print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    all = 0
    for a in A:
        all = gcd(all, a)
    if all != 1:
        return "not coprime"

    M = 10 ** 6
    B = dict()
    for a in A:
        if a in B:
            B[a] += 1
        else:
            B[a] = 1

    for i in range(2, M + 1):
        cnt = 0
        for j in range(i, M, i):
            if j in B:
                cnt += B[j]
        if cnt > 1:
            return "setwise coprime"

    return "pairwise coprime"

print(solve())

Submission status: Accepted

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


def main():
    from math import gcd
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    max_a = 10 ** 6
    numbers = [0 for _ in range(max_a + 1)]

    for ai in a:
        numbers[ai] += 1

    is_pairwise = True

    for i in range(2, max_a + 1):
        count = 0

        for j in range(i, max_a + 1, i):
            count += numbers[j]

            if count > 1:
                is_pairwise = False

    if is_pairwise:
        print("pairwise coprime")
        exit()

    value_gcd = 0

    for i in range(n):
        value_gcd = gcd(value_gcd, a[i])

        if value_gcd == 1:
            print("setwise coprime")
            exit()

    print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    all = 0
    for a in A:
        all = gcd(all, a)
    if all != 1:
        return "not coprime"

    M = 10 ** 6
    B = defaultdict(int)
    for a in A:
        B[a] += 1

    for i in range(2, M + 1):
        cnt = 0
        for j in range(i, M, i):
            cnt += B[j]
        if cnt > 1:
            return "setwise coprime"

    return "pairwise coprime"

print(solve())

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline

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

max_A = max(A)
if max_A == 1:
    print("pairwise coprime")
    exit()

class Prime:
    def __init__(self, n):
        self.prime_factor = [i for i in range(n + 1)]
        self.prime = []
        for i in range(2, n + 1):
            if self.prime_factor[i] == i:
                for j in range(2, n // i + 1):
                    self.prime_factor[i * j] = i
                self.prime.append(i)
        #print(self.prime_factor)
        #print(self.prime)
    def factorize(self, m):
        ret = []
        while m != 1:
            if not ret:
                ret = [[self.prime_factor[m], 1]]
            elif self.prime_factor[m] == ret[-1][0]:
                ret[-1][1] += 1
            else:
                ret.append([self.prime_factor[m], 1])
            m //= self.prime_factor[m]
        return ret
    def divisors(self, m):
        ret = []
        for i in range(1, int(m ** 0.5) + 1):
            if m % i == 0:
                ret.append(i)
                if i != m // i:
                    ret.append(m // i)
        #self.divisors.sort()
        return ret
pm = Prime(max_A)

def is_pairwise_coprime(arr):
    cnt = [0] * (max_A + 1)
    for a in arr:
        for b, c in pm.factorize(a):
            cnt[b] += 1
    if max(cnt[2:]) <= 1:
        return 1
    else:
        return 0

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

def is_setwise_coprime(A):
    gcd_a = 0
    for a in A:
        gcd_a = gcd(gcd_a, a)
    if gcd_a == 1:
        return 1
    else:
        return 0

if is_pairwise_coprime(A):
    print("pairwise coprime")
elif is_setwise_coprime(A):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd

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

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

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

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

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

Submission status: Accepted

Solution code:
from math import gcd

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

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

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p


# error_print(len(P))

@mt
def slv(N, A):
    P = eratosthenes(10**6+1)
    P = set(P)
    # random.shuffle(A)

    for a in A:
        u = set()
        if a in P:
            P.remove(a)
            a = 1

        for p in P:
            if a % p == 0:
                u.add(p)
            while a % p == 0:
                a //= p
            if a == 1:
                break

        if a != 1:
            break
        P -= u
    else:
        return 'pairwise coprime'

    g = 0
    for a in A:
        g = math.gcd(a, g)
    return 'setwise coprime' if g == 1 else 'not coprime'


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # P = eratosthenes(10**6+1)
    # N = len(P)
    # A = P[::-1]

    # error_print(N)
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd

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

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

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

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

Submission status: Accepted

Solution code:
from math import gcd

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

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

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

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

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

Submission status: Accepted

Solution code:
from math import gcd

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

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

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

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

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().split()]

m = max(a)
primes = list(range(m+1))
primes[1] = 0
for i in range(2, m+1, 2): primes[i] = 2

for i in range(3, int(m ** 0.5)+1):
    if primes[i] < i: continue
    for j in range(i, m+1, i):
        primes[j] = i

b = [0] * (m + 1)
jdg_p = True
for aa in a:
    aset = set()
    while aa != 1:
        aset.add(primes[aa])
        aa //= primes[aa]
    for aaset in aset:
        b[aaset] += 1
        if b[aaset] >= 2:
            jdg_p = False
            break
        else:
            b[aaset] += 1
    if not jdg_p: break

x = a[0]
jdg_s = True
for aa in a[1:]:
    x = math.gcd(x, aa)
if x != 1: 
    jdg_s = False

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

Submission status: Accepted

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

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

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

st = set()
for a in A:
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
    for p in tmp:
        if p in st:
            print('setwise coprime')
            exit()
        st.add(p)
print('pairwise coprime')

Submission status: Accepted

Solution code:
from functools import reduce
from math import gcd, sqrt,ceil


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

a_gcd = reduce(gcd,a)
if a_gcd != 1:
    print("not coprime")
    exit(0)
isset = a_gcd == 1
hurui = [i for i in range(m+1)]
for i in range(2,ceil(sqrt(m))+1):
    for j in range(2,ceil(sqrt(i))+1):
        if i==2:
            continue
        if i%j == 0:
            break
    else:
        for k in range(i+i,m,i):
            if hurui[k] != k:
                continue
            hurui[k] = i
    continue
s = set()
p_f = True
for ai in a:
    t = set()
    while(ai > 1):
        t.add(hurui[ai])
        ai //= hurui[ai]
    for ti in t:
        if ti in s:
            print("setwise coprime")
            exit(0)
        else:
            s.add(ti)

print("pairwise coprime")

Submission status: Accepted

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

from math import gcd

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

    # def fast_make_divisor(x):
    #     d = D[x]
    #     divisors = [d]
    #     while x != d:
    #         x = x // d
    #         d = D[x]
    #         divisors.append(d)
    # # print(divisors)
    #     return divisors

    g = A[0]
    dct = defaultdict(int)
    flag = True
    for a in A:
        g = gcd(g, a)
        # print(a, D[a])
        # if D[a] != 1:
        #     if dct[D[a]] > 0:
        #         flag = False
        #     dct[D[a]] += 1
        # print(a, fast_make_divisor(a))
        d = D[a]
        p = a
        # 最小の素数を求める
        while p != d:
            p = p // d
            d = D[p]

        if p != 1:
            dct[p] += 1
            if dct[p] > 1:
                flag = False

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

from math import gcd

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

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

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
if True:
    N = int(input())
    As = list(map(int, input().split()))

    maxA = 10**6 + 6
    c = [0] * (maxA+1)
    for A in As:
        c[A] += 1
    isPrime = True
    cnt = 0
    for i in range(2, maxA+1):
        cnt = sum(c[i::i])
        if cnt == N:
            # Asはすべてiの約数
            print("not coprime")
            break
        if cnt >= 2:
            isPrime = False
        
    else:
        if isPrime:
            print("pairwise coprime")
        else:
            print("setwise coprime")

Submission status: Accepted

Solution code:
if True:
    N = int(input())
    As = list(map(int, input().split()))

    maxA = 10**6 + 6
    c = [0] * (maxA+1)
    for A in As:
        c[A] += 1
    isPrime = True
    cnt = 0
    for i in range(2, maxA+1):
        cnt = sum(c[i::i])
        if cnt == N:
            # Asはすべてiの約数
            print("not coprime")
            exit()
        if cnt >= 2:
            isPrime = False
        
    else:
        if isPrime:
            print("pairwise coprime")
        else:
            print("setwise coprime")