Problem:


Score : 500 points

Problem Statement

We have N integers. The i-th number is A_i.

\{A_i\} is said to be pairwise coprime when GCD(A_i,A_j)=1 holds for every pair (i, j) such that 1\leq i < j \leq N.

\{A_i\} is said to be setwise coprime when \{A_i\} is not pairwise coprime but GCD(A_1,\ldots,A_N)=1.

Determine if \{A_i\} is pairwise coprime, setwise coprime, or neither.

Here, GCD(\ldots) denotes greatest common divisor.

Constraints

2 \leq N \leq 10^6

1 \leq A_i\leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

If \{A_i\} is pairwise coprime, print pairwise coprime; if \{A_i\} is setwise coprime, print setwise coprime; if neither, print not coprime.

Sample Input 1

3
3 4 5

Sample Output 1

pairwise coprime

GCD(3,4)=GCD(3,5)=GCD(4,5)=1, so they are pairwise coprime.

Sample Input 2

3
6 10 15

Sample Output 2

setwise coprime

Since GCD(6,10)=2, they are not pairwise coprime. However, since GCD(6,10,15)=1, they are setwise coprime.

Sample Input 3

3
6 10 16

Sample Output 3

not coprime

GCD(6,10,16)=2, so they are neither pairwise coprime nor setwise coprime.



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Accepted

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

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

if val > 1:
    print("not coprime")
    exit()

D = [i for i in range(max(A)+1)]
p = 2

while(p*p<=max(A)):
    if D[p]==p:
        for i in range(2*p,len(D),p):
            if D[i]==i:
                D[i]=p

    p+=1

prime = set()
for a in A:
    tmp=D[a]
    L=set()
    while(a>1):
        a=a//tmp
        L.add(tmp)
        tmp=D[a]
    #print(L)
    for l in L:
        if l in prime:
            #print(D)
            #print(prime)
            print("setwise coprime")
            exit()
        else:
            prime.add(l)
#print(D)
#print(prime)
print("pairwise coprime")

Submission status: Accepted

Solution code:
import sys
import numpy as np
i4 = np.int32
i8 = np.int64
u4 = np.uint32

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    from numba import njit
    from numba.types import Array, int32, int64, uint32
    cc = CC('my_module')

    @njit
    def get_factorization(n):
        """
        nまでの割り切れる最小の素数を返す。
        """
        sieve_size = (n - 1) // 2
        sieve = np.zeros(sieve_size, u4)
        for i in range(sieve_size):
            if sieve[i] == 0:
                value_at_i = i*2 + 3
                for j in range(i, sieve_size, value_at_i):
                    if sieve[j] == 0:
                        sieve[j] = value_at_i
        return sieve


    @cc.export('solve', (Array(uint32, 1, 'C'),))
    @njit('(u4[::-1],)', cache=True)
    def solve(A):
        a = np.sort(A)
        p_max = a[-1]
        p = get_factorization(p_max)
        primes_num = 1
        for i in range(p.shape[0]):
            if i*2 + 3 == p[i]:
                primes_num += 1
        a_start = 0
        while a[a_start] == 1:
            a_start += 1
            if a_start == a.shape[0]:
                return 0
        a = a[a_start:]
        if len(a) > primes_num:
            return 1
        check = np.zeros(p_max + 1, u4)
        for d in a:
            if d & 1 == 0:
                check[2] += 1
                d //= 2
                while d & 1 == 0:
                    d //= 2
            prev = 2
            while d > 1:
                i = (d - 3) // 2
                f = p[i]
                if f > prev:
                    check[f] += 1
                    prev = f
                d //= f

        if check.max() > 1:
            return 1
        else:
            return 0

    cc.compile()
    exit(0)

else:
    from my_module import solve


def main(in_file):
    stdin = open(in_file)
    stdin.readline()
    A = np.fromstring(stdin.readline(), u4, sep=' ')
    ans = solve(A)
    if ans:
        g = np.gcd.reduce(A)
        if g > 1:
            ans = 2
        else:
            ans = 1
    p = ['pairwise coprime', 'setwise coprime', 'not coprime']
    print(p[ans])


main(0)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
i4 = np.int32
i8 = np.int64
u4 = np.uint32


@njit
def get_factorization(n):
    """
    nまでの割り切れる最小の素数を返す。
    """
    sieve_size = (n - 1) // 2
    sieve = np.zeros(sieve_size, u4)
    for i in range(sieve_size):
        if sieve[i] == 0:
            value_at_i = i*2 + 3
            for j in range(i, sieve_size, value_at_i):
                if sieve[j] == 0:
                    sieve[j] = value_at_i
    return sieve


@njit('(u4[::-1],)', cache=True)
def solve(A):
    a = np.sort(A)
    p_max = a[-1]
    p = get_factorization(p_max)
    primes_num = 1
    for i in range(p.shape[0]):
        if i*2 + 3 == p[i]:
            primes_num += 1
    a_start = 0
    while a[a_start] == 1:
        a_start += 1
        if a_start == a.shape[0]:
            return 0
    a = a[a_start:]
    if len(a) > primes_num:
        return 1
    check = np.zeros(p_max + 1, u4)
    for d in a:
        if d & 1 == 0:
            check[2] += 1
            d //= 2
            while d & 1 == 0:
                d //= 2
        prev = 2
        while d > 1:
            i = (d - 3) // 2
            f = p[i]
            if f > prev:
                check[f] += 1
                prev = f
            d //= f

    if check.max() > 1:
        return 1
    else:
        return 0


def main(in_file):
    stdin = open(in_file)
    stdin.readline()
    A = np.fromstring(stdin.readline(), u4, sep=' ')
    ans = solve(A)
    if ans:
        g = np.gcd.reduce(A)
        if g > 1:
            ans = 2
        else:
            ans = 1
    p = ['pairwise coprime', 'setwise coprime', 'not coprime']
    print(p[ans])


if __name__ == '__main__':
    main('/dev/stdin')

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
i4 = np.int32
i8 = np.int64
u4 = np.uint32


@njit
def get_factorization(n):
    """
    nまでの割り切れる最小の素数を返す。
    """
    sieve_size = (n - 1) // 2
    sieve = np.zeros(sieve_size, u4)
    for i in range(sieve_size):
        if sieve[i] == 0:
            value_at_i = i*2 + 3
            for j in range(i, sieve_size, value_at_i):
                if sieve[j] == 0:
                    sieve[j] = value_at_i
    return sieve


@njit
def solve(A):
    a = np.sort(A)
    p_max = a[-1]
    p = get_factorization(p_max)
    primes_num = 1
    for i in range(p.shape[0]):
        if i*2 + 3 == p[i]:
            primes_num += 1
    a_start = 0
    while a[a_start] == 1:
        a_start += 1
        if a_start == a.shape[0]:
            return 0
    a = a[a_start:]
    if len(a) > primes_num:
        return 1
    check = np.zeros(p_max + 1, u4)
    for d in a:
        if d & 1 == 0:
            check[2] += 1
            d //= 2
            while d & 1 == 0:
                d //= 2
        prev = 2
        while d > 1:
            i = (d - 3) // 2
            f = p[i]
            if f > prev:
                check[f] += 1
                prev = f
            d //= f

    if check.max() > 1:
        return 1
    else:
        return 0


def main(in_file):
    stdin = open(in_file)
    stdin.readline()
    A = np.fromstring(stdin.readline(), u4, sep=' ')
    ans = solve(A)
    if ans:
        g = np.gcd.reduce(A)
        if g > 1:
            ans = 2
        else:
            ans = 1
    p = ['pairwise coprime', 'setwise coprime', 'not coprime']
    print(p[ans])


if __name__ == '__main__':
    main('/dev/stdin')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
MAX = pow(10,6)
#L = get_sieve_of_eratosthenes(MAX)
 
def factorization(n):
    arr = []
    temp = n
    if temp%2 == 0:
      cnt = 0
      while temp%2 == 0:
        cnt += 1
        temp//=2
      arr.append(2)
    for i in range(3, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
 
    if temp!=1:
        arr.append(temp)
 
    return arr
 
#XX = factorization(121)
#print(XX)
import math
N = int(input())
A = list(map(int,input().split()))
GCD = math.gcd(A[0],A[1])
for i in range(2,N):
  GCD = math.gcd(GCD,A[i])
  if GCD == 1:
    break
if GCD != 1:
  print("not coprime")
  exit()
A.sort()
SET = set([])
for x in A:
  SL = factorization(x)
  for yakusu in SL:
    if yakusu not in SET:
      SET.add(yakusu)
    else:
      print("setwise coprime")
      exit()
print("pairwise coprime")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
MAX = pow(10,6)
#L = get_sieve_of_eratosthenes(MAX)
 
def factorization(n):
    arr = []
    temp = n
    if temp%2 == 0:
      cnt = 0
      while temp%2 == 0:
        cnt += 1
        temp//=2
      arr.append(2)
    for i in range(3, int(-(-n**0.5//1))+1,2):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
 
    if temp!=1:
        arr.append(temp)
 
    return arr
 
#XX = factorization(121)
#print(XX)
import math
N = int(input())
A = list(map(int,input().split()))
GCD = math.gcd(A[0],A[1])
for i in range(2,N):
  GCD = math.gcd(GCD,A[i])
  if GCD == 1:
    break
if GCD != 1:
  print("not coprime")
  exit()
#A.sort()
SET = set([])
for x in A:
  SL = factorization(x)
  for yakusu in SL:
    if yakusu not in SET:
      SET.add(yakusu)
    else:
      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()))

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

if g>1:
    print("not coprime")
    exit()

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

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

print("pairwise coprime")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7

n=I()
A=LI()
l=A[0]
num=[0]*(10**6+1)
for i in range(1,n):
    num[A[i]]+=1
    l=gcd(l,A[i])



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


for j in range(2,10**6):
    ret=0
    for k in range(j,10**6+1,j):
        ret+=num[k]
    if ret>1:
        print("setwise coprime")
        exit()

print("pairwise coprime")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
MAX_A = max(a)
divide_minimam_prime = [i for i in range(MAX_A + 1)]
is_prime = [True for i in range(MAX_A + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(2,int(MAX_A**0.5) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= MAX_A:
            is_prime[k] = False
            if divide_minimam_prime[k] == k:
                divide_minimam_prime[k] = div
            k += div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(divide_minimam_prime[k])
        div = divide_minimam_prime[k]
        while k % div == 0 and k > 1:
            k = k // div
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    pr = [0]*(max(a)+1)
    flag = True
    for num in a:
        pr[num] += 1
    for i in range(2, max(a)+1):
        count = sum(pr[i::i])
        if count == N:
            print("not coprime")
            exit()
        elif count > 1:
            flag = False
    if flag:
        print("pairwise coprime")
    else:
        print("setwise coprime")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():

    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")
    mod = 10**9 + 7

    import sys
    input = lambda: sys.stdin.readline().rstrip("\r\n")

    from math import gcd

    def prime_factorize(n):
        a = []
        while n % 2 == 0:
            a.append(2)
            n //= 2
        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

    n = int(input())
    a = [int(x) for x in input().split()]

    primes = set()

    flag = 1

    for i in a:
        prime_factors = set(prime_factorize(i))
        for j in prime_factors:
            if j in primes:
                flag = 0
            else:
                primes.add(j)


    if flag:
        print('pairwise coprime')
        sys.exit()
                
    
    import math
    from functools import reduce
    
    def gcd(*numbers):
        return abs(reduce(math.gcd, numbers))
    
    if gcd(*a) == 1:
        print('setwise coprime')
    else:
        print('not coprime')

main()

Submission status: Accepted

Solution code:
def main():

    import sys
    input = lambda: sys.stdin.readline().rstrip("\r\n")

    from math import gcd

    def prime_factorize(n):
        a = []
        while n % 2 == 0:
            a.append(2)
            n //= 2
        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

    n = int(input())
    a = [int(x) for x in input().split()]

    primes = set()

    flag = 1

    for i in a:
        prime_factors = set(prime_factorize(i))
        for j in prime_factors:
            if j in primes:
                flag = 0
            else:
                primes.add(j)


    if flag:
        print('pairwise coprime')
        sys.exit()
                
    
    import math
    from functools import reduce
    
    def gcd(*numbers):
        return abs(reduce(math.gcd, numbers))
    
    if gcd(*a) == 1:
        print('setwise coprime')
    else:
        print('not coprime')

main()

Submission status: Accepted

Solution code:
import math
N = int(input())
num = list(map(int, input().split()))
#N = 10**6
#num = list(range(1, N+1))

MAXX = 10**6 + 1
MAXZ = int(math.sqrt(MAXX)+2)
furui = [[] for _ in range(MAXX)]

furui[1].append(1)
count = [0]*MAXX
for i in range(2, MAXX):
    if len(furui[i]) == 0:
        for k in range(i, MAXX, i):
            furui[k].append(i)

setwise = True
pairwise = True
for i in range(N):
    if not setwise and not pairwise: break
    for fu in furui[num[i]]:
        count[fu] += 1
        if fu > 1 and count[fu] >= N:
            setwise = False
            pairwise = False
            break
        elif fu > 1 and count[fu] > 1:
            pairwise = False

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

from math import gcd

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    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

n = int(input())
a = [int(x) for x in input().split()]

primes = set()

flag = 1

for i in a:
    prime_factors = set(prime_factorize(i))
    for j in prime_factors:
        if j in primes:
            flag = 0
        else:
            primes.add(j)


if flag:
    print('pairwise coprime')
    sys.exit()
            
 
import math
from functools import reduce
 
def gcd(*numbers):
    return abs(reduce(math.gcd, numbers))
 
if gcd(*a) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
import math
a=A[0]
for i in range(1,N):
  a=math.gcd(a,A[i])
def f():
  a=A[0]
  for i in range(1,N):
    a=math.gcd(a,A[i])
  if a==1:
    print("setwise coprime")
    exit()
  else:
    print("not coprime")
    exit()
  
D=[0]*(10**6+1)
for i in range(2,10**6+1):
  for j in range(2*i,10**6+1,i):
    if D[j]==0:
      D[j]=i
for i in range(10**6+1):
  if D[i]==0:
    D[i]=i

s=set()
import copy
for i in range(N):
  tmp=set()
  k=A[i]
  while k>1:
    tmp.add(D[k])
    k=k//D[k]
  for i in tmp:
    if i in s:
      f()
    else:
      s.add(i)


print("pairwise coprime")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

from math import gcd
n = int(input())
a = list( map(int, input().split()))


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

MAXN = 10**6+10

def eratosthenes3(limit):
    sieve = [i for i in range(limit+1)]
    p = 2
    while p*p <= limit:
        if sieve[p] == p:
            for q in range(2*p,limit+1,p):
                if sieve[q] == q:
                    sieve[q] = p
        p += 1

    return sieve

sieve = eratosthenes3(MAXN)

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

Submission status: Accepted

Solution code:
def abc177_e():
    n = int(input())
    A = [int(x) for x in input().split()]

    def prime_factorize(n:int)->set:
        ''' nの素因数分解 '''
        arr = []
        while n % 2 == 0:
            arr.append(2)
            n = n // 2
        f = 3
        while f*f <= n:
            if n%f == 0:
                arr.append(f)
                n = n // f
            else:
                f += 2
        if n != 1:
            arr.append(n)
        return set(arr)

    import math
    gcd_all = A[0]
    factors = [0]*(10**6 + 1)
    pairwise = True

    for ai in A:
        gcd_all = math.gcd(gcd_all, ai)
        for p in prime_factorize(ai):
            if factors[p]: pairwise = False
            factors[p] = 1

    if pairwise: ans = 'pairwise coprime'
    elif gcd_all == 1: ans = 'setwise coprime'
    else: ans = 'not coprime'
    print(ans)

if __name__ == '__main__':
    abc177_e()

Submission status: Accepted

Solution code:
from math import gcd

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

prime = list(range(max(A) + 1))

for i in range(2, len(prime)):
    if prime[i] != i:
        continue
    for j in range(i, len(prime), i):
        if prime[j] != j:
            continue
        prime[j] = i

used = set()
pc = True
for a in A:
    used_this = set()
    while a != 1:
        div = prime[a]
        if div in used:
            pc = False
            break
        used_this.add(div)
        a //= div
    used.update(used_this)

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

buf = A[0]
for a in A[1:]:
    buf = gcd(buf, a)
if buf == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd
MAX = 10**6

sieve = [i for i in range(MAX+1)]

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


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

for a in A:
    tmp = set()
    b = a
    while b != 1:
        tmp.add(sieve[b])
        b //= sieve[b]
    pf.append(tmp)


soin = [0] * (10 ** 6 + 1)
for f in pf:
    for n in f:
        soin[n] += 1

if max(soin[2:]) <= 1:
    print('pairwise coprime')
    exit()


setwise = A[0]

for a in A:
    setwise = gcd(setwise, a)
    
if setwise == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

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

check = [0]*(nmax + 5)
for i in a:
    check[i] += 1

pairwise = True
for i in range(2, nmax + 5):
    cnt = 0
    for j in range(i, nmax + 5, i):
        cnt += check[j] 
    if cnt > 1:
        pairwise = False

if pairwise == True:
    print('pairwise coprime')
    exit()

x = 0
for i in a:
    x = math.gcd(x,i)
if x == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

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

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5) #ルートn以上で割れることはない
    data = [i + 1 for i in range(2, n, 2)] #最初から3スタートの奇数にしておく
    while True:
        p = data[0]
        if limit < p: #ここでイコールが入るとlimitが素数の時にlimit^2が残ってダメ。
            return prime + data
        prime.append(p) #ここで一番最初に取り出した素数を加える。
        data = [e for e in data if e % p != 0] #残りでその素数で割れない数字を取得。

MAX = pow(10,6)
#L = get_sieve_of_eratosthenes(MAX)

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

#XX = factorization(121)
#print(XX)
import math
N = int(input())
A = list(map(int,input().split()))
GCD = math.gcd(A[0],A[1])
for i in range(2,N):
  GCD = math.gcd(GCD,A[i])
  if GCD == 1:
    break
if GCD != 1:
  print("not coprime")
  exit()
A.sort()
SET = set([])
for x in A:
  SL = factorization(x)
  for yakusu in SL:
    if yakusu not in SET:
      SET.add(yakusu)
    else:
      print("setwise coprime")
      exit()
print("pairwise coprime")

Submission status: Accepted

Solution code:

def gen_factorization(N):
    tables=[-1]*(N+1)
    for i in range(2,N+1):
        if tables[i]!=-1:continue
        tmp=i
        while tmp<=N:
            tables[tmp]=i
            tmp+=i
    def fuctorization(n):
        if n==1:return {1:1}
        elif n<0:n=abs(n)
        if n>N:return "error"
        ans={}
        while n!=1:
            tmp=tables[n]
            #debug print
            #print(tmp,n)
            ans.setdefault(tmp,0)
            ans[tmp]+=1
            n//=tmp
        return ans
    return fuctorization

N=int(input())
f=gen_factorization(10**6+10)
A=list(map(int,input().split()))
primes={}
for i in A:
  d=f(i)
  for j in d:
    primes.setdefault(j,0)
    primes[j]+=1
primes[1]=1
ansMax=max(primes.values())

if ansMax==1:
  print('pairwise coprime')
elif ansMax==N:
  print('not coprime')
else:
  print('setwise coprime')

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

_INPUT = """\
3
6 10 15
"""

def main(*, input=input):
    sr = lambda: input()
    ir = lambda: int(sr())
    lr = lambda: list(map(int, sr().split()))

    n = ir()
    a = lr()
    factors = [i for i in range(10**6+1)]
    primes = []
    for i in range(2, (10**6+2)//2):
        if i == factors[i]:
            primes.append(i)
        for num in primes:
            if i*num < 10**6+1:
                factors[i*num] = factors[i]
            else:
                break

    pairwise = True
    
    judge = [False for i in range(10**6+1)]
    a.reverse()
    for num in a:
        if num != 1:
            tmp = num
            fac = -1
            f = []
            while tmp != 1:
                if fac != factors[tmp]:
                    fac = factors[tmp]
                    f.append(fac)
                tmp //= factors[tmp]
            for h in f:
                if judge[h]:
                    # 被った
                    pairwise = False
                    break
                else:
                    judge[h] = True
        if not pairwise:
            break

    if pairwise:
        print('pairwise coprime')
    else:
        tmp = a[0]
        for num in a[1:]:
            tmp = math.gcd(tmp, num)
            if tmp == 1:
                print('setwise coprime')
                sys.exit()
        print('not coprime')



if __name__ == "__main__":
    import io, sys

    # sys.stdin = io.StringIO(_INPUT)

    main()

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

N = input()
A = list(map(int, input().split()))
M = 10**6+1
spf = [i for i in range(M)]
for i in range(2, M):
    if spf[i] == i:
        for j in range(i+i, M, i):
            spf[j] = i
cnt = defaultdict(int)
for a in A:
    ps = set()
    while a != 1:
        ps.add(spf[a])
        a = a // spf[a]
    for p in ps:
        cnt[p] += 1
if all([x < 2 for x in cnt.values()]):
    print("pairwise coprime")
    exit()
gcd = lambda x, y : x if y == 0 else gcd(y, x % y)
x = A[0]
for a in A[1:]:
    x = gcd(x, a)
if x == 1:
    print("setwise coprime")
else:
    print("not coprime")