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 sys, re
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 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def gcd_list(num_list: list) -> int:
    return reduce(gcd, num_list)

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

    return return_list[2:]

def main():
    n = i_input()
    num_list = i_list()

    num_list = list(set(num_list))

    if gcd_list(num_list) != 1:
        print('not coprime')
        exit()

    num_list.sort()

    tmp_list = [0] * (num_list[0-1] + 1)

    for num in num_list:
        if tmp_list[num] == 1:
            print('setwise coprime')
            exit()

        yakusu_list = make_divisors(num)
        yakusu_list.sort()

        for yakusu in yakusu_list:
            for i in range(yakusu, num_list[-1], yakusu):
                tmp_list[i] = 1

        for i in range(num, num_list[-1], num):
            tmp_list[i] = 1

    print('pairwise coprime')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


import collections
import functools
from math import gcd


L = 10 ** 6 + 1


def sieve_of_eratosthenes(end):
    """Enumerates prime numbers below the given integer `end`.

    Returns (as a tuple):

    - `is_prime`: a list of bool values.
      If an integer `i` is a prime number, then `is_prime[i]` is True.
      Otherwise `is_prime[i]` is False.
    - `primes`: a list of prime numbers below `end`.
    """

    if end <= 1:
        raise ValueError("The integer `end` must be greater than one")
    is_prime = [True for _ in range(end)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for i in range(2, end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes


PRIMES = sieve_of_eratosthenes(L)


def factorize(n):
    factors = []
    if n < 2:
        return factors
    for p in PRIMES:
        if p * p > n:
            break
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        factors.append(n)
    return factors


def is_pairwise_coprime(bs):
    lcm_fs = set()
    for b in bs:
        ps = set(factorize(b))
        for p in ps:
            if p in lcm_fs:
                return False
            else:
                lcm_fs.add(p)
    return True


def is_setwise_coprime(bs):
    return functools.reduce(gcd, bs) == 1


def main():
    n = int(input())
    bs = [int(b) for b in input().split()]
    if is_pairwise_coprime(bs):
        print("pairwise coprime")
    elif is_setwise_coprime(bs):
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def all_same(a):
    return all([x==a[0] for x in a])

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

def primechecker(x):
	original=x
	primefactorization=set()
	for i in range (2,int(original**0.5)+1):
		while x%i==0:
			primefactorization.add(i)
			x=x//i
	if x>1:
		primefactorization.add(x)
	return primefactorization

primefactors=set()

N=int(input())
array=[int(x) for x in input().split()]
checklist=[]
totality=0

def pairwisecoprime(array):
	for i in array:
		for j in primechecker(i):
			if j in primefactors:
				return 0
			else:
				primefactors.add(j)
	return 1
if pairwisecoprime(array):
	print("pairwise coprime")
	exit()




for i in array:
	totality=gcd(totality,i)

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

Submission status: Accepted

Solution code:
from operator import truediv
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

def make_divisors(n):
    res = []
    x = n
    y = 2
    while y*y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1:
        res.append(x)
    return res

n = ni()
a = na()
g = [0]*1000000

for i in range(n):
    ii = list(set(make_divisors(a[i])))
    b = True
    for p in ii:
        if g[p] == 0:
            g[p] += 1
        else:
            b = False
            break
    if not b:
        break
else:
    print('pairwise coprime')
    exit()

import math

k = a[0]
for i in a:
    k = math.gcd(k,i)
    if k == 1:
        print('setwise coprime')
        exit()

print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict

mxn = 10**6+1
spf = [i for i in range(mxn)]

for i in range(4,mxn,2):
  spf[i] = 2
i = 3
while i*i <= mxn:
  if spf[i] == i:
    for j in range(i*i,mxn,i):
      if spf[j] == j:
        spf[j] = i
  i += 1
ph = defaultdict(lambda:False)
pc = True
def getFactors(n):
  global pc
  while n != 1:
    temp = spf[n]
    if ph[temp] == True:
      pc = False
      break
    ph[temp] = True
    while n%temp == 0:
      n //= temp

n = int(input())
a = list(map(int,input().split()))
i,g = n-2,a[n-1]
while i >= 0:
  g = gcd(g,a[i])
  i -= 1
if g != 1:
  print("not coprime")
else:
  for i in a:
    if not pc:
      break
    getFactors(i)
  if not pc:
    print("setwise coprime")
  else:
    print("pairwise coprime")

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict
from functools import lru_cache


@lru_cache(None)
def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


def merge_dict(d1, d2):
    for k, v in d2.items():
        d1[k] += v
    return d1


def input():
    return sys.stdin.readline().strip()


def prime_factorization(N: int) -> dict:
    primes = defaultdict(int)
    primes[1] = 1
    if N < 2:
        return primes
    i = 2
    while i * i <= N:
        while N % i == 0:
            primes[i] += 1
            N = N // i
        i += 1
    if N != 1:
        primes[N] = 1
    return primes


def main():
    n = int(input())
    A = [int(i) for i in input().split()]
    primes = defaultdict(int)
    is_pair_gcd = True
    # pre-process
    for i in range(n):
        p = prime_factorization(A[i])
        for k, v in p.items():
            if k == 1:
                continue
            if k in primes.keys():
                is_pair_gcd = False
                break
            else:
                primes[k] += v
        else:
            continue
        break

    if is_pair_gcd:
        print("pairwise coprime")
        return

    set_gcd = A[0]
    for i in range(1, n):
        set_gcd = gcd(set_gcd, A[i])

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

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd

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

d = a[0]
m = a[0]

g = True

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

if d != 1:
    print("not coprime")
else:
    while len(a) > 1:
        b = []
        for i in range(0, len(a), 2):
            #print(i, a)
            if i == len(a)-1:
                b.append(a[i])
            else:
                e = gcd(a[i], a[i+1])
                if e != 1:
                    g = False
                    break
                else:
                    b.append(a[i] * a[i+1])
        a = b.copy()
        #print(a)


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

Submission status: Accepted

Solution code:
import sys
import math
import random
from collections import defaultdict
input = sys.stdin.readline
def is_prime(q,k=6):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

def fact(n):
    ret = set()
    for i in range(2, math.floor(math.sqrt(n))+1):
        if n % i == 0:
            ret.add(i)
            while n % i == 0:
                n //= i
    if n != 1:
        ret.add(n)
    return ret

    
if __name__ == "__main__":
    N = int(input())
    A = list(map(int,input().split()))
    primes = set()
    i = 0
    fl=True
    g = A[0]
    while i < len(A):
        a = A[i]
        g = math.gcd(g, a)
        if is_prime(a):
            if a in primes:
                fl = False
                break
            else:
                primes.add(a)
        else:
            ret = fact(a)
            if ret.intersection(primes):
                fl = False
                break
            else:
                primes |= ret
        i += 1
    if fl:
        print("pairwise coprime")
        exit(0)

    while i < len(A):
        g = math.gcd(g, A[i])
        if g == 1:
            print("setwise coprime")
            exit(0)
        i += 1
    print("not coprime")

Submission status: Accepted

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

is_pairwise = True

def calc_primes(n):
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data

primes = calc_primes(int(math.sqrt(10**6)))
used = set()

def factorize(n):
    for prime in primes:
        if n == 1:
            break
        is_used = False
        while n % prime == 0:
            if prime in used:
                return False
            n //= prime
            is_used = True
        if is_used:
            used.add(prime)
    if n > 1:
        if n in used:
            return False
        used.add(n)
    return True

all_gcd = A[0]
for a in A:
    all_gcd = math.gcd(all_gcd, a)
    if is_pairwise:
        if not factorize(a):
            is_pairwise = False

if is_pairwise:
    print('pairwise coprime')
elif all_gcd == 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 a > b:
        a, b = b, a
    while a > 0:
        a, b = b % a, a
    return b


def isprime(x):
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            return False
    return True


def div_primes(x):
    ret = {}
    for i in range(2, int(x**0.5) + 1):
        tmp = 0
        while x % i == 0:
            tmp += 1
            x //= i
        if tmp > 0:
            ret[i] = tmp
    if x > 1:
        ret[x] = 1
    return ret


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

if f >= 2:
    print("not coprime")
    exit()

# 10^6以下の素数
hurui = [True for _ in range(10**6 + 1)]
hurui[0] = hurui[1] = False
primes = {}
for i in range(2, len(hurui)):
    if hurui[i]:
        primes[i] = 0
        for j in range(i * 2, len(hurui), i):
            hurui[j] = False

flag = True
for av in a:
    if av in primes:
        if primes[av] == 0:
            primes[av] = 1
        else:
            flag = False
            break
    else:
        divs = div_primes(av)
        for k in divs.keys():
            if primes[k] == 0:
                primes[k] = 1
            else:
                flag = False
                break
    if flag == False:
        break

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

# 6
# 4 7 9 11 5 13

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
from math import gcd
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
        
    class Eratos:
        def __init__(self, num: int):
            '''
            O(nlglgn) で num までの素数判定テーブルを作る
            >>> e = Eratos(10)
            >>> e.table
            [False, False, True, True, False, True, False, True, False, False, False]
            '''
            if num < 1:
                raise ValueError(f'Eratos.__init__(): argument should be >= 1. got {num}')
            self.table_max = num
            # self.table[i] は i が素数かどうかを示す (bool)
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            i = 2
            while i ** 2 <= num:
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    # i**2 からスタートすることで定数倍高速化できる
                        self.table[j] = False
                i += 1   


        def is_prime(self, num: int) -> bool:
            '''
            O(1) で素数判定を行う
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
            '''
            if num < 1:
                raise ValueError(f'Eratos.is_prime(): argument shoule be >= 1. got {num}')
            if num > self.table_max:
                raise ValueError(f'Eratos.is_prime(): exceed table_max({self.table_max}). got {num}')
            return self.table[num]

        # def prime_factorize(self, num: int) -> Dict[int, int]:
        #     '''
        #     O(√n) で素因数分解を行う
        #     >>> e = Eratos(10000)
        #     >>> e.prime_factorize(6552)
        #     {2: 3, 3: 2, 7: 1, 13: 1}
        #     '''
        #     if num < 1:
        #         raise ValueError(f'Eratos.prime_factorize(): argument shoule be >= 1. got {num}')
        #     if (self.table_max + 1) ** 2 < num:
        #         raise ValueError('Eratos.prime_factorize(): exceed prime table size. got {}'.format(num))
        #     # 素因数分解の結果を記録する辞書        
        #     factorized_dict = dict()
        #     # n について、√n 以下の素数で割り続けると最後には 1 or 素数となる
        #     # 背理法を考えれば自明 (残された数が √n より上の素数の積であると仮定。これは自明に n を超えるため矛盾)
        #     for p in self.candidate:
        #         if num == 1:    # これ以上調査は無意味
        #             break
        #         if num % p == 0:
        #             # cnt = 0
        #             while num % p == 0:
        #                 num //= p
        #                 # cnt += 1
        #             # factorized_dict[p] = cnt
        #             factorized_dict[p] = 1
        #     if num != 1:
        #         factorized_dict[num] = 1
        #     return factorized_dict


    def check_setwise(n, L):
        gcd_memo = L[0]        
        for i in range(n):
            gcd_memo = gcd(L[i], gcd_memo)
        return gcd_memo == 1


    def check_pairwise(n, L):
        eratos = Eratos(10**3+1)
        # 2 to 10 ** 3 (168 個)
        p_list = [p for p in range(2, 10**3+1) if eratos.is_prime(p)]
        # print(p_list)
        divided = [0] * n
        memo = set()
        for i in range(n):
            num = L[i]
            for p in p_list:
                if num == 1:
                    break
                if num % p == 0:
                    while num % p == 0:
                        num //= p
                    if p in memo:
                        return False
                    else:
                        memo.add(p)
            divided[i] = num
        # print(divided)
        rem_one = [elm for elm in divided if elm != 1]
        return len(rem_one) == len(set(rem_one))


    n = ii()
    L = lmi()
    if check_pairwise(n, L):
        print('pairwise coprime')
    elif check_setwise(n, L):
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
*a,=map(int, input().split())
mapa=[0]*(10**6+1)

from bisect import bisect_left

n0 = 10**6
primes = set(range(2, n0+1))
for i in range(2, int(n0**0.5+1)):
    primes.difference_update(range(i*2, n0+1, i))
primeind=[0]*(10**6+1)
for p in primes:
    primeind[p]=1

def isPrime(m):
    return primeind[m]==1

def func(m):
    for i in range(2,int(m**0.5)+1):
        if isPrime(m):
            break
        if m%i==0:
            mapa[i]+=1
        while m%i==0:
            m//=i
        if m<i:
            break
    if m>1:
        mapa[m]+=1

for ai in a:
    func(ai)

tmp=max(mapa)
#print(mapa[:20])
if tmp==n:
    print('not coprime')
elif tmp>1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Accepted

Solution code:
import math 
import sys
from functools import reduce

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

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

if gcd_list(A) > 1:
  print("not coprime")
  sys.exit()
  
union = set()
intersection = set()

visited = set()
A_set = set()

flag = False
MAX = 10**6
lim = math.ceil(math.sqrt(MAX))
for a in A:
  #print(visited, a)
  if a in visited: 
    print("setwise coprime")
    sys.exit()
    flag = True 
    break
  b = a
  p = 2
  while p <= lim and b > 1:
    if p in visited: 
      p += 1
      continue
    if b % p == 0:
      q = p
      for q in range(p,MAX+1,p): #pの倍数を全てvisitedへ
        visited.add(q)     
    while b % p == 0:
      b = b // p
    p += 1
  if b > 1:
    q = b
    p = b
    for q in range(p,MAX+1,p): #pの倍数を全てvisitedへ
      visited.add(q) 
      
      

print("pairwise coprime")



"""
def raise_prime(B):
  n = len(B)
  if n == 1:
    
  C = B[0: n//2]
  D = B[n//2:n]
"""


  
  
"""
for a in A:
  p = 2
  while p <= N:
    if p not in visited:
      
      
    
  
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    union.add()
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
"""

Submission status: Accepted

Solution code:
MAXN = 1000001
spf = [i for i in range(MAXN)] 
hash1 = [0 for i in range(MAXN)] 

def sieve(): 
	for i in range(4, MAXN, 2): 
		spf[i] = 2

	for i in range(3, MAXN): 
		if i * i > MAXN: 
			break
		if (spf[i] == i): 
			for j in range(i * i, MAXN, i): 
				if (spf[j] == j): 
					spf[j] = i 

def getFactorization(x): 

	while (x != 1): 
		temp = spf[x] 
		if (x % temp == 0): 

			hash1[spf[x]] += 1
			x = x // spf[x] 

		while (x % temp == 0): 
			x = x // temp 

def hasValidNum(arr, n): 

	sieve() 

	for i in range(n): 
		getFactorization(arr[i]) 

	for i in hash1:
		if(i>1):
			return False
	return True

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

n=int(input())
arr=list(map(int,input().split()))
if (hasValidNum(arr, n)): 
	print("pairwise coprime") 
else: 
	g=arr[0]
	for i in range(1,n):
		g=gcd(g,arr[i])
	if(g==1):
		print("setwise coprime") 
	else:
		print("not coprime")

Submission status: Accepted

Solution code:

from math import gcd
from functools import reduce
from collections import defaultdict


def calc_factor(n):
    # O(N log log N)
    min_factor = list(range(n + 1))
    for i in range(2, n + 1):
        if min_factor[i] == i:
            for j in range(2 * i, n + 1, i):
                min_factor[j] = i
    return min_factor


def calc_prime_factor(n, min_factor):
    # O(log N)
    ctr = defaultdict(int)
    while n > 1:
        div = min_factor[n]
        while n % div == 0:
            ctr[div] += 1
            n //= div
    return ctr


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

min_factor = calc_factor(10 ** 6 + 10)
pairwise = True
appeared = set()
for v in X:
    primes = calc_prime_factor(v, min_factor)
    for n in primes:
        if n in appeared:
            pairwise = False
        appeared.add(n)

if pairwise:
    print("pairwise coprime")
elif reduce(gcd, X) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=tf-8
#

"""
"""

from collections import defaultdict
from itertools import accumulate
import bisect

import sys
input = sys.stdin.readline
import math as mt

MAXN = 10**6 +1
  
# stores smallest prime factor for 
# every number 
spf = [0 for i in range(MAXN)] 
  
# Calculating SPF (Smallest Prime Factor)  
# for every number till MAXN. 
# Time Complexity : O(nloglogn) 
def sieve(): 
    spf[1] = 1
    for i in range(2, MAXN): 
          
        # marking smallest prime factor  
        # for every number to be itself. 
        spf[i] = i 
  
    # separately marking spf for  
    # every even number as 2 
    for i in range(4, MAXN, 2): 
        spf[i] = 2
  
    for i in range(3, mt.ceil(mt.sqrt(MAXN))): 
          
        # checking if i is prime 
        if (spf[i] == i): 
              
            # marking SPF for all numbers 
            # divisible by i 
            for j in range(i * i, MAXN, i):  
                  
                # marking spf[j] if it is  
                # not previously marked 
                if (spf[j] == j): 
                    spf[j] = i 


def getFactorization(x): 
    ret = set([]) 
    while (x != 1): 
        ret.add(spf[x]) 
        x = x // spf[x] 
  
    return ret 


def solve(n,a):
    sieve()
    gcd_primes = getFactorization(a[0])
    seen_primes = set([])
    flag_pcp = True
    for aa in a:
        ps = getFactorization(aa)
        if flag_pcp:
            if not (seen_primes & ps):
                seen_primes |= ps
            else:
                flag_pcp = False
        gcd_primes &= ps
    if flag_pcp:
        print('pairwise coprime')
    elif gcd_primes:
        print('not coprime')
    else:
        print('setwise coprime')





            


            

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import Counter

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

set_A = set(A)
set_flag = len(set_A) != N

counter = Counter(A)
if len(counter) == N or (1 in counter and len(counter) - 1 + counter[1] == N):
    co_prime = True
    max_a = max(A)
    
    coprime = True
    exists = set()
    for i in range(2, max_a + 1):
        flag = False
        for j in range(i, max_a + 1, i):
            if j in set_A:
                if not flag:
                    flag = True
                elif flag:
                    coprime = False
                    break
        if not coprime:
            break
else:
    coprime = False

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

setwise = False
tmp = A[0]
for i in range(N):
    tmp = math.gcd(tmp, A[i])
if tmp == 1:
    setwise = True

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

Submission status: Accepted

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

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

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

    return arr

#factorization(24) 

## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1


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

#A = sorted(A)

ansN = A[0]
for i in range(1, n):
    ansN = math.gcd(ansN, A[i])
if ansN > 1:
    print('not coprime')
else:
    ans2 = True
    C = [0 for _ in range(10**6+10)]
    for a in A:
        F = factorization(a)
#        print(F)
        for f in F:
            if f[0] != 1:
                if C[f[0]] == 0:
                    C[f[0]] = 1
                else:
                    ans2 = False
                    break
        else:
            continue
        break
    if ans2:
        print('pairwise coprime')
    else:
        print('setwise coprime')

Submission status: Accepted

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

def prime_decomposition(n):
    i = 2
    table = []
    while i**2 <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1: table.append(n)
    return set(table)

pri_0 = prime_decomposition(a[0])
pri_1 = prime_decomposition(a[1])
ans = pri_0&pri_1

if len(ans):
    for i in range(2, n):
        res = prime_decomposition(a[i])
        ans &= res
        if not ans:
            print('setwise coprime')
            sys.exit()
    print('not coprime')

else:
    ans = pri_0 | pri_1
    for i in range(2, n):
        res = prime_decomposition(a[i])
        for i in res:
            if i in ans:
                print('setwise coprime')
                sys.exit()
        ans |= res
    print('pairwise coprime')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import gcd
from functools import reduce
def input(): return sys.stdin.readline().rstrip()
 
def pairwaise(bools):
    for i in range(2,10**6):
        hantei=0
        for j in range(i,10**6+1,i):
            hantei+=bools[j]
        if hantei>1:
            return False
    return True
 
 
def main():
    n=int(input())
    A=list(map(int, input().split()))
    gcds=reduce(gcd,A)
    if gcds>1:
        print('not coprime')
    else:
        bools=[0]*(10**6+5)
        for AA in A:
            if bools[AA]==1 and AA!=1:
                print('setwise coprime')
                exit()
            bools[AA]+=1
        if pairwaise(bools):
            print('pairwise coprime')
        else:
            print('setwise coprime')
 
    
    
 
 
if __name__ == '__main__':
    main()