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 inf, log2


class SegmentTree:
    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def query(self, alpha, omega):
        """Returns the result of function over the range (inclusive)!"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """Updates the element at index to given value!"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index >>= 1


# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

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


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

def get_primes(n):
  m = n+1
  #numbers = [True for i in range(m)]
  numbers = [True] * m #EDIT: faster
  for i in range(2, int(n**0.5 + 1)):
    if numbers[i]:
      for j in range(i*i, m, i):
        numbers[j] = False
  primes = []
  for i in range(2, m):
    if numbers[i]:
      primes.append(i)
  return primes

gp = set(get_primes(10**6))

from collections import Counter


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def memodict(f):
    """memoization decorator for a function taking a single argument"""
    class memodict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret

    return memodict().__getitem__


def pollard_rho(n):
    """returns a random factor of n"""
    if n & 1 == 0:
        return 2
    if n % 3 == 0:
        return 3

    s = ((n - 1) & (1 - n)).bit_length() - 1
    d = n >> s
    for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
        p = pow(a, d, n)
        if p == 1 or p == n - 1 or a % n == 0:
            continue
        for _ in range(s):
            prev = p
            p = (p * p) % n
            if p == 1:
                return gcd(prev - 1, n)
            if p == n - 1:
                break
        else:
            for i in range(2, n):
                x, y = i, (i * i + 1) % n
                f = gcd(abs(x - y), n)
                while f == 1:
                    x, y = (x * x + 1) % n, (y * y + 1) % n
                    y = (y * y + 1) % n
                    f = gcd(abs(x - y), n)
                if f != n:
                    return f
    return n


@memodict
def prime_factors(n):
    """returns a Counter of the prime factorization of n"""
    if n <= 1:
        return Counter()
    f = pollard_rho(n)
    return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)


def distinct_factors(n):
    """returns a list of all distinct factors of n"""
    factors = [1]
    for p, exp in prime_factors(n).items():
        factors += [p**i * factor for factor in factors for i in range(1, exp + 1)]
    return factors


def all_factors(n):
    """returns a sorted list of all distinct factors of n"""
    small, large = [], []
    for i in range(1, int(n**0.5) + 1, 2 if n & 1 else 1):
        if not n % i:
            small.append(i)
            large.append(n // i)
    if small[-1] == large[-1]:
        large.pop()
    large.reverse()
    small.extend(large)
    return small

for _ in range(int(input()) if not True else 1):
    n = int(input())
    #d, t, s = map(int, input().split())
    a = list(map(int, input().split()))
    g = a[0]
    for i in a:
        g = gcd(i, g)
    if g != 1:
        print("not coprime")
        continue
    pos = True
    for i in a:
        if i == 1:continue
        x = i
        b = []
        pf = prime_factors(i)
        for i in pf:
            if i in gp:
                gp.remove(i)
            else:
                pos = False
                break
        if not pos:break
    print("pairwise coprime" if pos else "setwise coprime")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        if not 1 <= n <= self.n_max: raise ValueError("Invaild Value!")
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return set(res)

from math import gcd
_, *a = map(int, open(0).read().split())
D = set()
t = 0
k = True
fac = Osa_k(max(a))
for b in a:
    s = fac(b)
    if D & s: k = False
    D |= s
    t = gcd(t, b) if t else b
if k:
    print("pairwise coprime")
elif t == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    d = {-1:1}
    def prime_factorize(n):
        a = set()
        while n % 2 == 0:
            a.add(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.add(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.add(n)
        for i in a:
            d[i] = d.get(i, 0) + 1
    for x in A:
        prime_factorize(x)
    m = max(d.values())
    if m == 1:
        return 'pairwise coprime'
    if m == N:
        return 'not coprime'
    return 'setwise coprime'
print(main())

Submission status: Accepted

Solution code:
def yakusu(x):
    tmp=int(pow(x, 1/2))+1
    out=set()
    for i in range(1, tmp):
        if x%i==0:
            out.add(i)
            out.add(x//i)
    if pow(x, 1/2)%1==0:
        out.add(pow(x, 1/2))
    out=list(out)
    out.sort()
    return out

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

pairwise=True
X=set()

for a in A:
  tmp=yakusu(a)
  for i in tmp[1:]:
    if i in X:
      pairwise=False
      break
    else:
      X.add(i)
  if pairwise==False:
    break
      
import math
tmp=A[0]+0
for a in A[1:]:
  tmp=math.gcd(tmp, a)
  
if tmp==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:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal
# from fractions import Fraction
# sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9) + 7

n=int(data())
a = mdata()
N=10**6 + 1
lpf = [0 for i in range(N)]
mobius = [0 for i in range(N)]


# Function to calculate least
# prime factor of each number
def least_prime_factor():
    for i in range(2, N):

        # If it is a prime number
        if (lpf[i] == 0):

            for j in range(i, N, i):

                # For all multiples which are not
                # visited yet.
                if (lpf[j] == 0):
                    lpf[j] = i

                # Function to find the value of Mobius function


# for all the numbers from 1 to n
def Mobius():
    for i in range(1, N):

        # If number is one
        if (i == 1):
            mobius[i] = 1
        else:

            # If number has a squared prime factor
            if (lpf[(i // lpf[i])] == lpf[i]):
                mobius[i] = 0

            # Multiply -1 with the previous number
            else:
                mobius[i] = -1 * mobius[i // lpf[i]]

            # Function to find the number of pairs


# such that gcd equals to 1
def gcd_pairs(a, n):
    # To store maximum number
    maxi = 0

    # To store frequency of each number
    fre = [0 for i in range(N)]

    # Find frequency and maximum number
    for i in range(n):
        fre[a[i]] += 1
        maxi = max(a[i], maxi)

    least_prime_factor()
    Mobius()

    # To store number of pairs with gcd equals to 1
    ans = 0

    # Traverse through the all possible elements
    for i in range(1, maxi + 1):
        if (mobius[i] == 0):
            continue

        temp = 0
        for j in range(i, maxi + 1, i):
            temp += fre[j]

        ans += temp * (temp - 1) // 2 * mobius[i]

        # Return the number of pairs
    return ans


# Driver code


# Function call
g=a[0]
for i in range(n):
    g=math.gcd(g,a[i])
    if g==1:
        break
if gcd_pairs(a, n) == (n*(n-1))//2:
    out("pairwise coprime")
elif g==1:
    out("setwise coprime")
else:
    out("not coprime")

Submission status: Accepted

Solution code:
from sys import exit

def eratosthenes(n):
    '''
    n以下の整数の素数判定/列挙 (n > 1)
    O(NloglogN)
    '''
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False

    return [i for i in range(n+1) if is_prime[i]]


def factorization(n):
    '''
    素因数分解
    O(√N)
    '''
    res = []
    m = 2
    while m ** 2 <= n:
        if n % m == 0:
            cnt = 0
            while n % m == 0:
                cnt += 1
                n //= m
            res.append([m, cnt])
        m += 1

    if n > 1:
        res.append([n, 1])

    return res


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

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

flag1 = True
for v1 in a:
    for v2 in l1:
        if is_prime[v1]:
            if judge[v1]:
                flag1 = False
            else:
                judge[v1] = True
            break

        if v1 % v2 == 0:
            if judge[v2]:
                flag1 = False
            else:
                judge[v2] = True
            
            while v1 % v2 == 0:
                v1 //= v2
        
        if v1 == 1:
            break
        
if flag1:
    print('pairwise coprime')
    exit()

l2 = factorization(a[0])
for i, j in l2:
    flag2 = True
    for v in a:
        if v % i != 0:
            flag2 = False
            break
    if flag2:
        print('not coprime')
        exit()

print('setwise coprime')

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


# 素因数分解（複数回）
class Factorize(object):

    def __init__(self, maxnum):
        self.primes = self.__smallest_prime_factors(maxnum)

    # 素因数分解 O(logN)
    def factorize(self, n):
        fct = defaultdict(lambda: 0)
        while n != 1:
            fct[self.primes[n]] += 1
            n //= self.primes[n]
        return fct

    # n以下の最小の素因数を列挙する O(NlogN)
    def __smallest_prime_factors(self, n):

        prime = list(range(n + 1))

        for i in range(2, int(n**0.5) + 1):
            if prime[i] != i:
                continue
            for j in range(i * 2, n + 1, i):
                prime[j] = min(prime[j], i)
        return prime


def main():

    N = in_n()
    A = sorted(in_nl())

    M = 10**6 + 1
    ok = [True] * M

    fct = Factorize(M)

    pf = True
    for i in range(N):
        prime = fct.factorize(A[i])
        for p in prime.keys():
            if not ok[p]:
                pf = False
                break
            else:
                ok[p] = False

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

    if pf:
        ans = "pairwise coprime"
    else:
        if g == 1:
            ans = "setwise coprime"
        else:
            ans = "not coprime"

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from math import gcd

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class Eratosthenes:
    def __init__(self, n):
        self.n = n
        self.min_factor = [-1] * (n + 1)
        self.min_factor[0], self.min_factor[1] = 0, 1

    def get_primes(self):
        primes = []
        is_prime = [True] * (self.n + 1)
        is_prime[0] = is_prime[1] = False
        for i in range(2, self.n + 1):
            if not is_prime[i]:
                continue
            primes.append(i)
            self.min_factor[i] = i
            for j in range(i * 2, self.n + 1, i):
                is_prime[j] = False
                if self.min_factor[j] == -1:
                    self.min_factor[j] = i
        return primes

    def prime_factorization(self, n):
        res = []
        while n != 1:
            prime = self.min_factor[n]
            exp = 0
            while self.min_factor[n] == prime:
                exp += 1
                n //= prime
            res.append([prime, exp])
        return res


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    MAX = max(A)
    tot_gcd = A[0]
    for a in A:
        tot_gcd = gcd(tot_gcd, a)

    if tot_gcd != 1:
        print("not coprime")
    else:
        er = Eratosthenes(MAX)
        er.get_primes()
        check = [False] * (MAX + 1)
        for a in A:
            for p, _ in er.prime_factorization(a):
                if not check[p]:
                    check[p] = True
                else:
                    print("setwise coprime")
                    exit()
        print("pairwise coprime")


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def sieve(n):
    is_prime = [True for _ in range(n)]
    is_prime[0] = False

    for i in range(2, n + 1):
        if is_prime[i - 1]:
            j = i
            f = 0
            while j <= n:
                if f and j in b:
                    return False
                if j in b:
                    f = True
                is_prime[j - 1] = False
                j += i
    return True


from math import gcd
from functools import reduce


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


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
b = set(a)
c = Counter(a)
f = 0
for i in c:
    if i != 1 and c[i] > 1:
        f = 1
if ((1 in a and len(b) == 1) or sieve(10 ** 6)) and f == 0:
    print("pairwise coprime")
elif gcd_list(a) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

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

def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret


from collections import defaultdict
n = int(input())
A = tuple(map(int, input().split()))
x = A[0]
M1 = defaultdict(int)
M2 = defaultdict(int)
b = False
for a in A:
    x = gcd(x, a)
    if b:
      continue
    for f, cnt in primeFactor(a).items():
      if cnt >= M1[f]:
        M2[f] = M1[f]
        M1[f] = cnt
      elif cnt >= M2[f]:
        M2[f] = cnt
      if M2[f] >= 1:
        b = True
        break
if x != 1:
    print("not coprime")
    exit()
if b:
  print("setwise coprime")
  exit()
print("pairwise coprime")

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce


def factor(n):
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            res.append(i)
            n //= i
    if n > 1:
        return res + [n]
    else:
        return res


def solve():
    PC = "pairwise coprime"
    SC = "setwise coprime"
    NC = "not coprime"
    is_PC = True
    is_SC = True

    N, *A = map(int, open(0).read().split())

    primes = set()
    for a in A:
        if a == 1:
            continue
        new_primes = set(factor(a))
        if new_primes & primes:
            is_PC = False
            break
        primes |= set(factor(a))

    if reduce(gcd, A) != 1:
        is_SC = False

    if is_PC:
        print(PC)
    elif is_SC:
        print(SC)
    else:
        print(NC)


solve()

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
a = list(map(int, input().split()))
g = a[0]
for i in range(1, n):
    g = gcd(g, a[i])
if g == 1:
    p = [1] * (10 ** 6 + 1)
    r = [0] * (10 ** 6 + 1)
    p[0], p[1] = 0, 0
    r[0] = 0
    r[1] = 1
    for i in range(2, 10 ** 6 + 1):
        if p[i]:
            r[i] = i
            for j in range(i * 2, 10 ** 6 + 1, i):
                p[j] = 0
                if r[j] == 0:
                    r[j] = i
    t = [0] * (10 ** 6 + 1)
    for x in a:
        ps = []
        while x > 1:
            if t[r[x]]:
                print('setwise coprime')
                exit(0)
            ps.append(r[x])
            x //= r[x]
        for p in ps:
            t[p] = 1
    print('pairwise coprime')
else:
    print('not coprime')

Submission status: Accepted

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

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

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

small_prime = [p for p in range(1100) if is_prime[p]]
        
g = 0

for a in A:
    g = gcd(g, a)

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

used = [False] * 1100000
primes = [a for a in A if is_prime[a]]
for p in primes:
    used[p] = True

not_primes = [a for a in A if not is_prime[a]]

for a in not_primes:
    for p in small_prime:
        if a == 1:break
        if a % p != 0:continue
        if used[p]:
            print("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:
import sys
input=sys.stdin.readline

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

import math

gall=a[0]
for i in a:
    gall=math.gcd(gall,i)

M=10**6
if gall==1:
    check=True
    sa=set()
    for i in a:
        if not i in sa:
            sa.add(i)
        else:
            if not i==1:
                check=False
    for i in range(2,M+1):
        temp=i
        count=0
        while temp<=M:
            if temp in sa:
                count+=1
            temp+=i
        if count>=2:
            check=False

    if check:
        print('pairwise coprime')
    else:
        print('setwise coprime')

else:
    print('not coprime')

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    *A, = map(int, input().split())

    B = [0] * (10 ** 6 + 1)
    for x in A:
        B[x] += 1

    setwise = False

    d = 2
    e = d
    cnt = 0
    while e <= 10 ** 6:
        if B[e]:
            cnt += B[e]
        e += d
    if cnt == N:
        print('not coprime')
        return
    elif cnt > 1:
        setwise = True

    d = 3
    while d <= 10 ** 6:
        e = d
        cnt = 0
        while e <= 10 ** 6:
            if B[e]:
                cnt += B[e]
            e += d
        if cnt == N:
            print('not coprime')
            return
        elif cnt > 1:
            setwise = True
        d += 2

    print('setwise coprime' if setwise else 'pairwise coprime')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
m=(10**6+1)
b=[-1]*m
g=a[0]
for i in a:
    g=math.gcd(g,i)
for i in range(2,m):
    tmp=i
    while tmp<m:
        if b[tmp]==-1:
            b[tmp]=i
        tmp+=i
def factorize(k):
    l=[]
    while k>1:
        l.append(b[k])
        k//=b[k]
    return l
p=set()
for i in a:
    l=factorize(i)
    for j in l:
        if j in p:
            if g==1:
                print('setwise coprime')
            else:
                print('not coprime')
            exit()
    for j in l:
        p.add(j)
print('pairwise coprime')

Submission status: Accepted

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

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


def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

p = primes(1003)



g = a[0]

for e in a:
    g = gcd(g,e)


if g != 1:
    print("not coprime")
else:
    s = set()
    for e in a:
        if e == 1:
            continue
        if e in s:
            print("setwise coprime")
            exit()
        for d in p:
            if e < d:
                break
            if e%d == 0:
                d2 = e//d
                if d in s:
                    print("setwise coprime")
                    exit()
                s.add(d)
                if d2 > 1003:
                    if d2 in s:
                        print("setwise coprime")
                        exit()
                    s.add(d2)
        s.add(e)
    print("pairwise coprime")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
A = LI()

from math import gcd

g = 0
for i in range(N):
    g = gcd(g,A[i])

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

B = []
for i in range(N):
    if A[i] != 1:
        B.append(A[i])
N = len(B)

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

primes = [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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

if N > 78498:
    print('setwise coprime')
    exit()


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

for i in range(N):
    b = B[i]
    for p in primes:
        if b % p == 0:
            if C[p] == 1:
                print('setwise coprime')
                exit()
            else:
                C[p] = 1
            while b % p == 0:
                b //= p
    if b != 1:
        if C[b] == 1:
            print('setwise coprime')
            exit()
        else:
            C[b] = 1

print('pairwise coprime')

Submission status: Accepted

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


X = A[:]
while len(X) > 1:
    X.append(gcd(X.pop(), X.pop()))


def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


S = set()
pairwise_coprime_flg = True
for a in A:
    s = set(prime_factorization(a))
    for v in s:
        if v in S:
            pairwise_coprime_flg = False
        S.add(v)
    if not pairwise_coprime_flg:
        break

if pairwise_coprime_flg:
    print('pairwise coprime')
elif X[0] == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

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

s=set()
f=1
for x in a:
	if f==0:
		break
	if x>1:
		r=int(x**0.5+1e-8)+1
		for i in range(2,r):
			if x%i==0:
				while x%i==0:
					x//=i
				if i in s:
					f=0
					break
				else:
					s.add(i)
		if x>1:
			if x in s:
				f=0
				break
			else:
				s.add(x)

if f:
	print("pairwise coprime")
	exit()
p=a[0]
from math import gcd
for x in a:
	p=gcd(p,x)
if p==1:
	print("setwise coprime")
else:
	print("not coprime")