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:
# E

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

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

def fast_factorization_init(N):
    res=list(range(N))
    for i in range(2,N):
        if i*i>N:
            break
        for j in range(i*i,N,i):
            if res[j]==j:
                res[j]=i
        if res[i]<i:
            continue
    return res            
    
min_factors=fast_factorization_init(10**6+10)
def fast_factorization(n):
    res=[]
    while n>1:
        res.append(min_factors[n])
        n//=min_factors[n]
    return list(set(res))

res2=0
P=[]
for i in range(N):
    if i!=0:
        res1=gcd(A[i],res1)
    else:
        res1=A[0]
    P += fast_factorization(A[i])

if len(set(P))==len(P):
    res2=1

if res2==1:
    print('pairwise coprime')
elif res1==1:
    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()))
MAX = 10**6 + 1

def prime_factor_sieve(n):
    """
    エラトステネスの篩で、
    2 ~ Nの各数に対して、その整数のもつ最小の素因数
    (その整数を篩落とした最小の素因数)を記録して返す
    O(nloglog(n))
    """
    res = [i for i in range(n+1)]
    for i in range(2, int(n**0.5)+1):
        if res[i] < i:
            continue
        for j in range(i*i, n+1, i):
            if res[j] == j:
                res[j] = i
    return res

def factorization(n, min_factor, used_factor, cnt):
    """
    エラトステネスの篩で手に入れた、各整数の最小素因数のリスト
    からO(log(n))で素因数分解する
    """
    
    while n > 1:
        if used_factor[min_factor[n]] == 0:
            used_factor[min_factor[n]] = cnt
        elif used_factor[min_factor[n]] != cnt:
            return False
        n //= min_factor[n]
        # 割った後の素因数についてもO(1)で参照できる
    return True


# 素因数が重複しているかを調べる
min_factor = prime_factor_sieve(MAX)
res = set()
is_ok = 1
used_factor = [0]*(MAX+1)
cnt = 1
for a in A:
    if a == 1:
        continue
    is_ok = factorization(a, min_factor, used_factor, cnt)
    cnt += 1
    if not is_ok:
        break

if is_ok:
    print("pairwise coprime")
else:
    g = A[0]
    for i in range(1, N):
        g = gcd(g, A[i])
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd
def main():
    n=int(input())
    A=list(map(int,input().split()))
    m=max(A)
    l=[0 for _ in range(m)]
    fp=True
    for a in A:
        l[a-1]+=1
    for i in range(2,m):
        cnt=0
        for j in range(i-1,m,i):
            cnt+=l[j]
            if cnt>1:
                fp=False
                break
    g=0
    fs=False
    for a in A:
        g=gcd(g,a)
    if g==1:
        fs=True

    if fp:
        print("pairwise coprime")
    elif fs:
        print("setwise coprime")
    else:
        print("not coprime")
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import math
(_,), a  = [list(map(int, s.split())) for s in open(0)]
 
def fast_factorize(num):
    min_factor_list = list(range(num + 1))
    for i in range(int(math.sqrt(num) + 1), 1, -1):
        for j in range(i, num+1, i):
            min_factor_list[j] = i
    return min_factor_list
 
min_factor_list = fast_factorize(max(a))
 
prime_factor_sets = []
for x in a:
    prime_factor_set = set()
    while min_factor_list[x] != 1:
        prime_factor_set.add(min_factor_list[x])
        x //= min_factor_list[x]
    prime_factor_sets.append(prime_factor_set)

g = prime_factor_sets[0].copy()
l = set()
s = 0
for x in prime_factor_sets:
    g &= x
    l |= x
    s += len(x)

if len(g) != 0:
    ans = 'not coprime'
elif len(l) != s:
    ans = 'setwise coprime'
else:
    ans = 'pairwise coprime'
print(ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
    if a < b:
        a, b = b, a
    c = 1
    while c != 0:
        c = a % b
        a = b
        b = c
    return a


numbers = [[] for i in range(10**6 + 1)]
flag = [True for i in range(10**6 + 1)]
for i in range(2, 10**6 + 1):
    if flag[i]:
        for j in range(2, 10**6 // i + 1):
            if i * j > 10**6:
                break
            flag[i * j] = False
            numbers[i * j].append(i)
N = int(input())
alist = list(map(int, input().split()))
adict = {}
flag = False
for a in alist:
    if a == 1:
        continue
    temp = numbers[a]
    if temp == []:
        temp = [a]
    for i in temp:
        if i not in adict:
            adict[i] = 0
        else:
            flag = True
            break
    if flag:
        break

if not flag:
    print("pairwise coprime")
    exit(0)

temp = gcd(alist[0], alist[1])
for a in alist[2:]:
    temp = gcd(temp, a)
    if temp == 1:
        print("setwise coprime")
        exit(0)

print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd
n=int(input())
arr=list(map(int,input().split()))
p=[i for i in range(10**6+1)]
for i in range(2,10**3+1):
    if p[i]==i:
        for j in range(i*i,10**6+1,i):
            if p[j]==j:
                p[j]=i
se=set()
k=0
for i in arr:
    c=i
    f=p[c]
    l=set()
    while(c!=1):
        if f in se:
            k=1
            break
        l.add(f)
        c//=f
        f=p[c]
    se|=l
    if k:
        break
if k==0:
    print("pairwise coprime")
else:
    gc=arr[0]
    for i in arr[1:]:
        gc=gcd(gc,i)
    if gc==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
import math
N= int(input())
A = list(map(int, input().split()))
M = [0] * (10**6+1)
g = A[0]
for i in A:
    M[i] += 1
    g = math.gcd(g, i)
if g > 1:
    print('not coprime')
    exit()
for i in range(2,10**6+1):
    c = 0
    for j in range(i,10**6+1,i):
        c += M[j]
    if c > 1:
        print('setwise coprime')
        exit()
print('pairwise coprime')

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class Osa_k():
    def __init__(self, n):
        self.sieve = list(range(n + 1))
        self.sieve[0] = 1 #素数でない
        self.sieve[1] = 1 #素数でない
        m = int(math.sqrt(n))
        for i in range(2, m + 1):
            if self.sieve[i] < i:
                continue
            for j in range(i * i, n + 1, i):
                if self.sieve[j] == j:
                    self.sieve[j] = i

    def factorize(self, n):
        prime = defaultdict(int)
        if n == 0 or n == 1:
            return n
        opt = n
        while opt > 1:
            prime[self.sieve[opt]] += 1
            opt //= self.sieve[opt]
        return sorted(prime.items())

N = getN()
A = getList()
O = Osa_k(10 ** 6 + 1)

pair = True
primes = set()
x = A[0]
for a in A[1:]:
    x = math.gcd(x, a)
    if pair and a != 1:
        factor = set()
        for i in O.factorize(a):
            factor.add(i[0])
        if not primes.isdisjoint(factor):
            pair = False
        else:
            primes |= factor

if pair:
    print("pairwise coprime")
elif x == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
def main():
    from math import gcd
    _ = int(input())
    A = [int(i) for i in input().split()]
    maxA = max(A)

    def Eratosthenes(sup: int) -> set:
        primes = [True]*(sup+1)
        primes[0] = False
        primes[1] = False
        for i in range(2, sup+1):
            if primes[i]:
                MINFact[i] = i
                mul = 2
                while i*mul <= sup:
                    primes[i*mul] = False
                    if MINFact[i*mul] == -1:
                        MINFact[i*mul] = i
                    mul += 1

    def prime_factor(n):
        while n != 1:
            prime = MINFact[n]
            while MINFact[n] == prime:
                n //= prime
            B[prime] += 1

    MINFact = [-1] * (maxA + 1)
    MINFact[0] = 0
    MINFact[1] = 1
    Eratosthenes(maxA)

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

    B = [0]*(maxA+1)
    for a in A:
        prime_factor(a)

    if g != 1:
        print("not coprime")
    elif max(B) <= 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
A=list(map(int,input().split()))
cnt=[0]*(10**6+10)
for i in A:
    cnt[i]+=1


if np.gcd.reduce(A) !=1:
    print("not coprime");exit()
elif np.all([sum(cnt[i::i])<=1 for i in range(2,10**6+1)]):
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Accepted

Solution code:
def main():
    from math import gcd
    _ = int(input())
    A = [int(i) for i in input().split()]

    class osa_k:
        def __init__(self, sup):
            if sup > 2 * 10**8:
                raise RuntimeError("too big")
            self.MINFact = [-1] * (sup + 1)
            self.MINFact[0] = 0
            self.MINFact[1] = 1
            primes = [True for i in range(sup+1)]
            primes[0] = False
            primes[1] = False
            for i in range(2, sup+1):
                if primes[i]:
                    self.MINFact[i] = i
                    mul = 2
                    while i*mul <= sup:
                        primes[i*mul] = False
                        if self.MINFact[i*mul] == -1:
                            self.MINFact[i*mul] = i
                        mul += 1

        def prime_factor(self, n, B):
            while n > 1:
                prime = self.MINFact[n]
                while self.MINFact[n] == prime:
                    n //= prime
                B[prime] += 1

    maxA = max(A)
    p = osa_k(maxA)
    B = [0] * (maxA + 1)
    for a in A:
        p.prime_factor(a, B)

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

    if g != 1:
        print("not coprime")
    elif max(B) <= 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
N = int(input())
A = list(map(int, input().split()))
M = [0] * (10**6+1)
for i in A:
    M[i] += 1
if gcd_list(A) > 1:
    print('not coprime')
    exit()
for i in range(2,10**6+1):
    c = 0
    for j in range(i,10**6+1,i):
        c += M[j]
    if c > 1:
        print('setwise coprime')
        exit()
print('pairwise coprime')

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

if reduce(gcd, A) != 1:
    print("not coprime")
    exit()
ma = max(A)
p = list(range(ma+1))
for x in range(2, int(ma ** 0.5) + 1):
    if p[x] == x:
        for i in range(x + x, ma+1, x):
            p[i] = x

s = [set() for _ in range(N)]
t = set()

for i, x in enumerate(A):
    while x != 1:
        s[i].add(x)
        t.add(x)
        x //= p[x]
l = sum(len(x) for x in s)
print("pairwise coprime" if l == len(t) else "setwise coprime")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, AS):
    num_division = 0
    maxAS = max(AS)
    eratree = [0] * (maxAS + 10)
    for p in range(2, maxAS + 1):
        if eratree[p]:
            continue
        # p is prime
        eratree[p] = p
        x = p * p
        while x <= maxAS:
            if not eratree[x]:
                eratree[x] = p
            x += p

    from collections import defaultdict
    count = defaultdict(int)
    for a in AS:
        factors = []
        while a > 1:
            d = eratree[a]
            factors.append(d)
            a //= d
            num_division += 1
        # debug(": ", factors)
        for f in set(factors):
            count[f] += 1

    # debug(": num_division", num_division)
    if any(x == N for x in count.values()):
        return "not coprime"
    if any(x >= 2 for x in count.values()):
        return "setwise coprime"
    return "pairwise coprime"


def main():
    # parse input
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


# tests
T1 = """
3
3 4 5
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
pairwise coprime
"""

T2 = """
3
6 10 15
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
setwise coprime
"""

T3 = """
3
6 10 16
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
not coprime
"""

T4 = """
3
100000 100001 100003
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
pairwise coprime
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


N = I()
A = LI()


def is_pair_coprime(A):
    n = max(A)
    D = [0] * (n + 1)
    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
            if not D[j]:
                D[j] = i

    used = [False] * (n + 1)
    for a in A:
        temp = a

        while D[temp]:
            mod = D[temp]
            if used[mod]:
                return False
            else:
                used[mod] = True
            while temp % mod == 0:
                temp //= mod

        if temp != 1:
            if used[temp]:
                return False
            else:
                used[temp] = True

    return True


# def pre_fac(n):
#     D = [0] * (n + 1)
#     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
#             if not D[j]:
#                 D[j] = i
#     return D


# def fac(prime, n):
#     if n == 1:
#         return [[1, 1]]
#     arr, temp = [], n
#
#     while prime[temp]:
#         mod = prime[temp]
#         cnt = 0
#         while temp % mod == 0:
#             cnt += 1
#             temp //= mod
#         arr.append([mod, cnt])
#
#     if temp != 1:
#         arr.append([temp, 1])
#
#     return arr

if is_pair_coprime(A):
    print("pairwise coprime")
elif np.gcd.reduce(A) == 1:
    print("setwise coprime")
else:
    print("not coprime")

# prime = pre_fac(10 ** 6)
#
# d = defaultdict(int)
# for a in A:
#     tmp = fac(prime, a)
#     for t in tmp:
#         d[t[0]] += 1
#
# flag = True
# for k, v in d.items():
#     if flag and v != 1:
#         if k != 1:
#             flag = False
#     if v == N:
#         if k == 1:
#             print("pairwise coprime")
#         else:
#             print("not coprime")
#             exit()
#
#
# if flag:
#     print("pairwise coprime")
# elif 1 in A:
#     print("not coprime")
# else:
#     print("setwise coprime")

Submission status: Accepted

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

if np.gcd.reduce(a) != 1:
    print('not coprime')
    exit()

m=max(a)
cnt=[0]*(m+1)

for i in range(len(a)):
    cnt[a[i]]+=1
#print(cnt)
for i in range(2, m + 1):
    #print(cnt[i::i])
    if sum(cnt[i::i]) > 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')

Submission status: Accepted

Solution code:
from math import gcd


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

# setwise validation
tmp = 0
for a in A:
    tmp = gcd(tmp, a)
isSetwise = (tmp == 1)

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

cnt = 0
isPairwise = True
for i in range(2, M + 1):
    isPairwise &= (sum(sieve[j] for j in range(i, M + 1, i)) <= 1)

# check
if isPairwise:
    ans = 'pairwise coprime'
elif isSetwise:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

Submission status: Accepted

Solution code:
#ソートなし版
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

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

def gcdlist(l):
    a = l[0]
    for i in range(1,len(l)):
        a = gcd(a,l[i])
    return a

def fctr1(n): 
    f = []
    c = 0
    for i in range(2,int(n**0.5)+2):
        while n%i == 0:
            c += 1
            n = n//i
        if c !=0:
            f.append([i,c])
            c = 0
    if n != 1:
        f.append([n,1])
    return f

n = int(readline())
a = list(map(int,readline().split()))
check = [True]*(10**6+5)
p1 = True
for ai in a:
    if not p1:
        break
    dlist = fctr1(ai)
    for d,c in dlist:
        if check[d]:
            check[d] = False
        else:
            p1 = False
            break

if p1:
    print("pairwise coprime")
else:
    p2 = gcdlist(a)
    if p2 == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
def resolve():
    import math
    n = int(input())
    a = list(set(map(int, input().split())))
    maxa = max(a)

    ggcd = a[0]
    for i in range(1, len(a)):
        ggcd = math.gcd(ggcd, a[i])
        if ggcd == 1:
            break

    pair = False

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

    for i in range(2, maxa+1):
        cnt = 0
        for j in range(i, maxa+1, i):

            cnt += c[j]
        if cnt > 1:
            pair = True

    if ggcd != 1:
        print("not coprime")
    else:
        if pair:
            print("setwise coprime")
        else:
            print("pairwise coprime")
resolve()

Submission status: Accepted

Solution code:
from math import gcd


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

# setwise validation
tmp = 0
for a in A:
    tmp = gcd(tmp, a)
isSetwise = (tmp == 1)

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

cnt = 0
isPairwise = True
for i in range(2, M + 1):
    tmp = 0
    for j in range(i, M + 1, i):
        tmp += sieve[j]
    isPairwise &= (tmp <= 1)

# check
if isPairwise:
    ans = 'pairwise coprime'
elif isSetwise:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

Submission status: Accepted

Solution code:
from math import gcd


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

# setwise validation
tmp = 0
for a in A:
    tmp = gcd(tmp, a)
isSetwise = (tmp == 1)

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

cnt = 0
for i in range(2, M + 1):
    tmp = 0
    for j in range(i, M + 1, i):
        tmp += sieve[j]
    cnt = max(cnt, tmp)
isPairwise = (cnt <= 1)

# check
if isPairwise:
    ans = 'pairwise coprime'
elif isSetwise:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

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

am = max(a)

memo = [1] * (am+1)
memo[0] = 0
memo[1] = 0

d = set([])

for ai in range(2, am+1):
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0

cs = set([])
for i, memoi in enumerate(memo):
    if memoi:
        cs.add(i)

# print(cs)


f1 = 1
f2 = 1

for ai in a:
    lim = int(ai**0.5)+1
    f0 = 0
    if ai in cs:
        if ai in d:
            f0 = 1
            f1 = 0
        else:
            d.add(ai)
    else:  
        for i in cs:
            if i >= lim:
                break
            if ai % i == 0:
                if i in d or ai//i in d:
                    f1 = 0
                    f0 = 1
                    break
                else:
                    d.add(i)
                    d.add(ai//i)
    if f0:
        break


if f1:
    print('pairwise coprime')
else:
    g = a[0]
    for ai in a:
        g = gcd(ai, g)
    if g == 1:
        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()))
exist = [0] * (10**6 + 1)
for a in A:
    exist[a] += 1

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

if g != 1:
    print('not coprime')
elif all([sum(exist[i::i]) <= 1 for i in range(2, 10**6+1)]):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))
exist = [0] * (10**6 + 1)
for a in A:
    exist[a] += 1

if np.gcd.reduce(A) != 1:
    print('not coprime')
elif np.all([sum(exist[i::i]) <= 1 for i in range(2, 10**6+1)]):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    min_pri = [i for i in range(10**6+1)]
    ps = []
    for i in range(2,10**3):
        if min_pri[i] != i:
            continue
        else:
            ps.append(i)
            for j in range(i,10**6+1,i):
                if min_pri[j] == j:
                    min_pri[j] = i

    a = [int(i) for i in ipt().split()]
    g = a[0]
    d = defaultdict(bool)
    f1 = True
    for i in a:
        g = math.gcd(g,i)
        if f1 and i != 1:
            ni = i
            pi = bisect.bisect_left(ps,min_pri[i])
            for j in ps[pi::]:
                ff = True
                while ni%j == 0:
                    if ff:
                        if d[j]:
                            f1 = False
                            break
                        d[j] = True
                        ff = False
                    ni //= j
                if not f1 or ni == 1:
                    break
            if ni != 1:
                if d[ni]:
                    f1 = False
                d[ni] = True

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




    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, AS):
    num_division = 0
    maxAS = max(AS)
    eratree = [0] * (maxAS + 10)
    for p in range(2, maxAS + 1):
        if eratree[p]:
            continue
        # p is prime
        x = p
        while x <= maxAS:
            if not eratree[x]:
                eratree[x] = p
            x += p

    from collections import defaultdict
    count = defaultdict(int)
    for a in AS:
        factors = []
        while a > 1:
            d = eratree[a]
            factors.append(d)
            a //= d
            num_division += 1
        # debug(": ", factors)
        for f in set(factors):
            count[f] += 1

    # debug(": num_division", num_division)
    if any(x == N for x in count.values()):
        return "not coprime"
    if any(x >= 2 for x in count.values()):
        return "setwise coprime"
    return "pairwise coprime"


def main():
    # parse input
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


# tests
T1 = """
3
3 4 5
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
pairwise coprime
"""

T2 = """
3
6 10 15
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
setwise coprime
"""

T3 = """
3
6 10 16
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
not coprime
"""

T4 = """
3
100000 100001 100003
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
pairwise coprime
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import math

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

def sieve_of_eratosthenes(n):
    sieve = list(range(n+1))
    m = int(math.sqrt(n))
    for i in range(2, m + 1):
        if sieve[i] < i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve

def factorize_by_sieve(x, sieve):
    factor = defaultdict(int)
    while sieve[x] != x:
        factor[sieve[x]] += 1
        x //= sieve[x]
    factor[x] += 1
    return factor

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

sieve = sieve_of_eratosthenes(max(a_list))
pairwise = True
setwise = True
primes = set()
x = a_list[0]
for a in a_list:
    x = gcd(x, a)
    if pairwise and a != 1:
        factor = set(factorize_by_sieve(a, sieve).keys())
        pairwise = primes.isdisjoint(factor)
        primes |= factor

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

Submission status: Accepted

Solution code:
from math import gcd


def factorization(n):
    global Ans, flag
    if n == 1:
        return
    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
            Ans[i] += 1
            if Ans[i] == 2:
                flag = True


    if temp != 1:
        Ans[temp] += 1
        if Ans[temp] == 2:
            flag = True

    return


N = int(input())
A = list(map(int, input().split()))
a = A[0]
flag = False
for b in A[1:]:
    a = gcd(a, b)

if a != 1:
    print('not coprime')
    exit()
ma = max(A) + 1
Ans = [0] * (ma)

Ans[0] = 1
for a in A:
    factorization(a)
    if flag:
        print('setwise coprime')
        exit()
print('pairwise coprime')

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
def Dlist(BIG):
    D=[1]*(BIG+1)
    for p in range(2,BIG+1):
        if D[p]!=1:
            continue
        for i in range(p,BIG+1,p):
            if D[i]==1:
                D[i]=p
    return D

D=Dlist(max(A))
def SOINSU(num,D): #素因数だけ列挙(setしただけ)
    now=num ; ans=set()
    while now>1:
        ans.add(D[now])
        now//=D[now]
    return ans

seen=[0]*(10**6+10)
flag=1
for num in A:
    for i in SOINSU(num,D):
        if seen[i]!=0: flag=0
        seen[i]+=1
if flag:
    print("pairwise coprime")
elif max(seen)!=n:
    print("setwise coprime")
else:
    print("not coprime")