Problem:


Score : 500 points

Problem Statement

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

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

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

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

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

Constraints

2 \leq N \leq 10^6

1 \leq A_i\leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

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

Sample Input 1

3
3 4 5

Sample Output 1

pairwise coprime

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

Sample Input 2

3
6 10 15

Sample Output 2

setwise coprime

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

Sample Input 3

3
6 10 16

Sample Output 3

not coprime

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



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Accepted

Solution code:

import math
from functools import reduce


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


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


def eratosthenes(n):
    D = [0]*(n+1)
    for i in range(2, n+1):
        if D[i] > 0:
            continue
        for j in range(i, n+1, i):
            D[j] = i
    return D


N = int(input())
A = list(map(int, input().split()))
D = eratosthenes(10**6+1)
# D = eratosthenes(max(A))
dic = {}
for i in A:
    while i != 1:
        if i in dic:
            dic[i] += 1
        else:
            dic[i] = 1
        i //= D[i]
isPairwise = True
for i in dic.items():
    if i[1] > 1:
        isPairwise = False
        break


def is_pairwise():
    used_primes = [False] * (10**6 + 1)
    for a in A:
        while a > 1:
            prime = D[a]
            while a % prime == 0:
                a //= prime
            if used_primes[prime]:
                return False
            used_primes[prime] = 1
    return True


# if isPairwise:
if is_pairwise():
    print("pairwise coprime")
elif gcd_list(A) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

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

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

def prime_factorize(n):
  global a
  tmp = []
  while n % 2 == 0:
    if 2 not in a:
      tmp.append(2)
      n //= 2
    else:
      return False
  f = 3
  while f * f <= n:
    if n % f == 0:
      if f not in a:
        tmp.append(f)
        n //= f
      else:
        return False
    else:
      f += 2
  if n != 1:
    if n not in a:
      tmp.append(n)
    else:
      return False
  a |= set(tmp)
  return True

flag = True
for i in range(N):
  ans = prime_factorize(A[i])
  if not ans:
    flag = False
    break
if flag:
  print('pairwise coprime')
elif gcd_list(A) == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Accepted

Solution code:
import collections
import heapq
import math
import random
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500005)
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
rs = lambda: input().rstrip()

Nmax = 10**6 + 1

n = ri()
A = rl()

f = [0] * Nmax
for v in A:
    f[v] += 1
for i in range(2, Nmax//2+1):
    for j in range(i*2, Nmax, i):
        f[i] += f[j]

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

if max(f[2:]) <= 1:
    print("pairwise coprime")
else:
    x = 0
    for v in A:
        x = gcd(x, v)
    if x == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
"""E."""

import sys


def input() -> str:  # noqa: A001
    """Input."""
    return sys.stdin.readline()[:-1]


RESULT_TEXT = {
    1: 'pairwise coprime',
    2: 'setwise coprime',
    3: 'not coprime',
}

n = int(input())

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

ans = 0

MAX = 1000000 + 1
counts = [0] * MAX
for a in a_list:
    counts[a] += 1

max_count = 0

for i in range(2, MAX):
    max_count = max(max_count, sum(counts[i::i]))

if max_count == n:
    ans = 3
elif max_count >= 2:
    ans = 2
else:
    ans = 1

print(RESULT_TEXT[ans])

Submission status: Accepted

Solution code:
N=int(input())
from math import gcd
from functools import reduce
l=list(map(int,input().split()))
sw=0
c=[0]*1000001
for i in l:
   c[i]+=1
if all(sum(c[i::i])<=1 for i in range(2,1000001)):
   print("pairwise coprime")
elif reduce(gcd,l)==1:
   print("setwise coprime")
else:
   print("not coprime")

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
def prime_factorize(n):
    prime_fact = []
    while n%2 == 0:
        prime_fact.append(2)
        n//=2
    f = 3
    while f * f <= n:
        if n % f == 0:
            prime_fact.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        prime_fact.append(n)
    return prime_fact

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    prefix_gcd = a[0]
    dp = [0]*(max(a)+1)
    for i in range(n):
        prefix_gcd = math.gcd(prefix_gcd,a[i])

    for i in range(n):
        d = prime_factorize(a[i])
        d = set(d)
        for j in d:
            dp[j]+=1
    pair = True
    for i in range(len(dp)):
        if dp[i] > 1:
            pair = False
    if pair == True and prefix_gcd == 1:
        print("pairwise coprime")
    elif pair == False and prefix_gcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
import math
import collections
import copy
import sys

n = int(input())

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

limit = 10 ** 6

sCheck = math.gcd(a[0],a[1])
if n == 2:
    if sCheck == 1:
        print("pairwise coprime")
    else:
        print("not coprime")
    sys.exit()
else:
    for i in range(2,n):
        sCheck = math.gcd(sCheck,a[i])


beforeQ = collections.deque([int(i) for i in range(3,(limit + 1))])
D = dict()
p = 2
D[2] = 2
D[1] = 1

while p < math.sqrt(limit):
    afterQ = collections.deque()
    while len(beforeQ) > 0:        
        k = beforeQ.popleft()
        if k % p != 0:
            afterQ.append(k)
        else:
            D[k] = p
    beforeQ = copy.copy(afterQ)
    p = beforeQ.popleft()
    D[p] = p
while len(beforeQ) > 0:
    k = beforeQ.popleft()
    D[k] = k
    
ansSet = set()
count = 0

for i in a:
    k = i
    kSet = set()
    while k != 1:
        if D[k] in ansSet:
            if not(D[k] in kSet):
                count = 1
                break
        else:
            ansSet.add(D[k])
            kSet.add(D[k])
        k = int(k // D[k])
    if count == 1:
        break

if count == 0:
    print("pairwise coprime")
elif sCheck == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:

# A以下の数がN個与えられる。全て素因数分解せよ。
class SpeedPrime:
    # a以下の各数の最小の素因数を記録
    def __init__(self, a):
        self.d = [i for i in range(a+1)]

        i=2
        while i*i<=a:
            if self.d[i]==i:
                j=i*i
                while j<=a:
                    if self.d[j]==j:
                        self.d[j]=i
                    j+=i
            i+=1

    # nを高速素因数分解
    def fac(self, n):
        ret = dict()
        while n!=1:
            prime=self.d[n]
            if prime in ret:
                ret[prime]+=1
            else:
                ret[prime]=1
            n=n//prime
        return ret

import math
from functools import reduce
def gcd(numbers):
    return reduce(math.gcd, numbers)

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

sp=SpeedPrime(max(a))

d=set()
pc=True
for i in a:
    prime=sp.fac(i)
    for k in prime.keys():
        if k in d:
            pc=False
            break
        else:
            d.add(k)

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

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

Submission status: Accepted

Solution code:
from math import sqrt, gcd
import sys


def osk_a(M):
    p = [i for i in range(M+1)]
    for x in range(2, int(sqrt(M))+1):
        if p[x] == x:
            for y in range(2*x, M+1, x):
                if p[y] == y:
                    p[y] = x
    return p


def g(a):
    g = 0
    for x in a:
        g = gcd(g, x)
    return g


def main():
    n = int(sys.stdin.buffer.readline())
    a = list(map(int, sys.stdin.buffer.readline().split()))
    if g(a) > 1:
        print("not coprime")
        exit()
    p = osk_a(10**6)
    chk = set()
    while a[0] > 1:
        chk.add(p[a[0]])
        a[0] //= p[a[0]]
    for x in a[1:]:
        tmp = set()
        while x > 1:
            tmp.add(p[x])
            x //= p[x]
        if not chk.isdisjoint(tmp):
            print("setwise coprime")
            exit()
        chk |= tmp
    print("pairwise coprime")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import sqrt, gcd
import sys


def osk_a(M):
    p = [i for i in range(M+1)]
    for x in range(2, int(sqrt(M))+1):
        if p[x] == x:
            for y in range(2*x, M+1, x):
                if p[y] == y:
                    p[y] = x
    return p


def g(a):
    g = 0
    for x in a:
        g = gcd(g, x)
    return g


def main():
    n = int(sys.stdin.buffer.readline())
    a = list(map(int, sys.stdin.buffer.readline().split()))
    if g(a) > 1:
        print("not coprime")
        exit()
    p = osk_a(10**6)
    chk = set()
    t = a[0]
    while t > 1:
        chk.add(p[t])
        t //= p[t]

    for x in a[1:]:
        tmp = set()
        while x > 1:
            tmp.add(p[x])
            x //= p[x]
        if chk.isdisjoint(tmp):
            chk |= tmp
        else:
            print("setwise coprime")
            exit()
    print("pairwise coprime")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import sqrt, gcd
import sys


def osk_a(M):
    p = [i for i in range(M+1)]
    for x in range(2, int(sqrt(M))+1):
        if p[x] == x:
            for y in range(2*x, M+1, x):
                if p[y] == y:
                    p[y] = x
    return p


def g(a):
    g = 0
    for x in a:
        g = gcd(g, x)
    return g


def main():
    n = int(sys.stdin.buffer.readline())
    a = list(map(int, sys.stdin.buffer.readline().split()))
    if g(a) > 1:
        print("not coprime")
        exit()
    p = osk_a(10**6)
    chk = set()
    t = a[0]
    while t > 1:
        chk.add(p[t])
        t //= p[t]

    for x in a[1:]:
        tmp = set()
        while x > 1:
            tmp.add(p[x])
            x //= p[x]
        if len(chk & tmp):
            print("setwise coprime")
            exit()
        else:
            chk |= tmp
    print("pairwise coprime")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
a = list(map(int, input().split()))
max_a = max(a)
cnt_a = [0] * (max_a + 1)
for ai in a:
  cnt_a[ai] += 1
ans = 'pairwise'
for i in range(2, max_a + 1):
  cnt = 0
  for j in range(i, max_a + 1, i):
    cnt += cnt_a[j]
  if cnt > 1:
    ans = 'setwise'
g = 0
for ai in a:
  g = gcd(g, ai)

if ans == 'pairwise':
  print(ans, 'coprime')
elif ans == 'setwise' and g == 1:
  print(ans, 'coprime')
else:
  print('not coprime')

Submission status: Accepted

Solution code:
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))

flag = True

d_set = set()
for a in A:
    while a != 1:
        d = D[a]
        if d in d_set:
            flag = False
            break
        else:
            d_set.add(d)
        while a > 1 and a % d == 0:
            a = a // d
    if not(flag):
        break



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

if reduce(math.gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))

flag = True

d_set = set()
for a in A:
    while a != 1:
        d = D[a]
        if d in d_set:
            flag = False
            break
        else:
            d_set.add(d)
        while a > 1 and a % d == 0:
            a = a // d



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

if reduce(math.gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))

flag = True

d_set = set()
for a in A:
    while a != 1:
        d = D[a]
        if d in d_set:
            flag = False
            break
        else:
            d_set.add(d)
        
        while a % d == 0 and a > 1:
            a = a // d

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

if reduce(math.gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))

flag = True

d_set = set()
for k in A:
    while k != 1:
        div = D[k]
        if div in d_set:
            flag = False
            break
        else:
            d_set.add(div)
        
        while k % div == 0 and k > 1:
            k = k // div

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

if reduce(math.gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))
pairwise_coprime = True
use_divnum = set()
for k in A:
    while k != 1:
        div = D[k]
        if div in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(div)
        
        while k % div == 0 and k > 1:
            k = k // div

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

if reduce(math.gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))
pairwise_coprime = True
use_divnum = set()
for k in A:
    while k != 1:
        if D[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(D[k])
        div = D[k]
        while k % div == 0 and k > 1:
            k = k // div

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

if reduce(math.gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))
pairwise_coprime = True
use_divnum = set()
for i in range(N):
    k = A[i]
    while k != 1:
        if D[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(D[k])
        div = D[k]
        while k % div == 0 and k > 1:
            k = k // div

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

if reduce(math.gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    input_list[0] = 0
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = int(math.sqrt(num))
    
    for serial in range(3, sqrt + 1, 2):
        if bool_list[serial]:
            for s in range(serial ** 2, num+1, serial):
                if bool_list[s]:
                    input_list[s] = serial
                    bool_list[s] = False
    return input_list

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

D = getD(max(A))
pairwise_coprime = True
use_divnum = set()
for i in range(N):
    k = A[i]
    while k != 1:
        if D[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(D[k])
        div = D[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
from math import gcd


def osa_k(sieve, MAXN):
    p = 2
    while p * p <= MAXN:
        # まだチェックされていないなら
        if sieve[p] == p:
            # 次のqの倍数からp刻みでチェック入れていく
            for q in range(2 * p, MAXN + 1, p):
                if sieve[q] == q:
                    sieve[q] = p
        p += 1


input = lambda: sys.stdin.readline().rstrip()
n = int(input())
A = list(map(int, input().split()))
nowgcd = A[0]
# 全体のGCDを取る
for i in A:
    nowgcd = gcd(nowgcd, i)
if nowgcd != 1:
    print('not coprime')
    exit()

MAXN = 10**6 + 5
sieve = [i for i in range(MAXN + 1)]
p = 2
osa_k(sieve, MAXN)

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

Submission status: Accepted

Solution code:
import sys
from math import gcd
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
A = list(map(int, input().split()))
nowgcd = A[0]
# 全体のGCDを取る
for i in A:
    nowgcd = gcd(nowgcd, i)
if nowgcd != 1:
    print('not coprime')
    exit()

# osa_k法で前処理
MAXN = 10**6 + 5
sieve = [i for i in range(MAXN + 1)]
p = 2
while p * p <= MAXN:
    # まだチェックされていないなら
    if sieve[p] == p:
        # 次のqの倍数からp刻みでチェック入れていく
        for q in range(2 * p, MAXN + 1, p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1

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

Submission status: Accepted

Solution code:
def GCD(m, n):
    while n != 0:
        m, n = n, m % n
    return m

def gcd_all(a):
    n = len(a)
    gcd = a[0]
    for i in range(1, n):
        gcd = GCD(gcd, a[i])
    return gcd

def f(a):
    mx = 10**6
    p = set([])
    sieve = [i for i in range(mx + 1)]
    for i in range(2, int(mx**0.5 + 1)):
        for j in range(2 * i, mx + 1, i):
            if sieve[j] > i:
                sieve[j] = i
    pairwise_coprime = True
    for i in a:
        p2 = set([])
        while i > 1:
            p2.add(sieve[i])
            i //= sieve[i]
        for j in p2:
            if j in p:
                pairwise_coprime = False
                break
            p.add(j)
        if pairwise_coprime == False:
            break
    gcd = gcd_all(a)
    if pairwise_coprime == False and gcd == 1:
        return 'setwise coprime'
    elif pairwise_coprime:
        return 'pairwise coprime'
    else:
        return 'not coprime'

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

Submission status: Accepted

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


# number_to_prime[i]: i の最小の素因数, iが素数ならば0
number_to_prime = [0] * (10**6 + 1)

# preprocess
for i in range(2, 10**6+1):
    if not number_to_prime[i]:
        j = 1
        while j*i <= 10**6:
            number_to_prime[j*i] = i
            j += 1

def is_pairwise():
    used_primes = [False] * (10**6 + 1)
    pairwise_flag = 1
    for a in A:
        curr_primes = set()
        while a > 1:
            prime = number_to_prime[a]
            while a % prime == 0:
                a //= prime
            if used_primes[prime]:
                return False
            used_primes[prime] = 1
    return True

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pairwise():
    print("pairwise coprime")
elif is_setwise(*A):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

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


# number_to_prime[i]: i の最小の素因数, iが素数ならば0
number_to_prime = [0] * (10**6 + 1)

# preprocess
for i in range(2, 10**6+1):
    if not number_to_prime[i]:
        j = 1
        while j*i <= 10**6:
            number_to_prime[j*i] = i
            j += 1

def is_pair_copr(A):
    import numpy as np
    U = 1 << 20
    div_p = np.arange(U)
    for p in range(2, U):
        if div_p[p] != p:
            continue
        div_p[p::p] = p
    used = np.zeros(U, np.bool_)
 
    for x in A:
        while x > 1:
            p = div_p[x]
            while x % p == 0:
                x //= p
            if used[p]:
                return False
            used[p] = True
    return True

def is_pairwise():
    used_primes = set()
    pairwise_flag = 1
    for a in A:
        curr_primes = set()
        while a > 1:
            prime = number_to_prime[a]
            curr_primes.add(prime)
            a //= prime
        if used_primes & curr_primes:
            pairwise_flag = 0
            break
        else:
            used_primes = used_primes | curr_primes
    return pairwise_flag

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pair_copr(A):
    print("pairwise coprime")
elif is_setwise(*A):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

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

# 素因数分解、リストで返す
#############################################################
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)
    a.sort()
    return a
#############################################################

primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i])
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

# print(primes)

if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import sys

N=int(input())
A = list(map(int,input().split()))
 
import math
from functools import reduce

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

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

if gcd_list(A) > 1:
    print("not coprime")
    sys.exit()

D = [i for i in range(max(A)+1)] #iを割り切る最小の素数を格納
p = 2
 
while(p*p<=max(A)):
    if D[p]==p:
        for i in range(2*p,max(A)+1,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]

    for l in L:
        if l in prime:
            print("setwise coprime")
            sys.exit()
        else:
            prime.add(l)

print("pairwise coprime")

Submission status: Accepted

Solution code:
import sys

N=int(input())
A = list(map(int,input().split()))
 
import math
from functools import reduce

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

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

if gcd_list(A) > 1:
    print("not coprime")
    sys.exit()

D = [i for i in range(max(A)+1)] #iを割り切る最小の素数を格納
p = 2
 
while(p*p<=max(A)):
    if D[p]==p:
        for i in range(p*p,max(A)+1,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]

    for l in L:
        if l in prime:
            print("setwise coprime")
            sys.exit()
        else:
            prime.add(l)

print("pairwise coprime")

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class Sieve: #区間[2,n]の値の素因数分解 O(nloglogn+logn)
    def __init__(self,n): #nは計算対象としてありうる最大の値
        self.primes=[]
        self.f=[0]*(n+1) #ふるい（素数ならその値）
        self.f[0]=self.f[1]=-1
        self.f_lis = [0]*(n+1)
        for i in range(2,n+1): #素数リスト作成
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,n+1,i):
                if not self.f[j]:
                    self.f[j]=i  #最小の素因数を代入
    def prime_fact(self,A): #素因数分解 {2:p,3:q,5:r,...}
        for x in A:
            while x!=1:
                p=self.f[x]
                x//=p
                if x % p > 0:
                    if self.f_lis[p] > 0: return False
                    self.f_lis[p] += 1
        return True

import math
from functools import reduce
def gcd_all(numbers):#gcd(A)
    return reduce(math.gcd, numbers)

def main():
    n = int(input())
    A = list(map(int,input().split())) 
    Sieve_a = Sieve(max(A)+1)
    if Sieve_a.prime_fact(A):
        print("pairwise coprime")
    elif gcd_all(A) == 1:
        
        print("setwise coprime")   
    else:
        print("not coprime")

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def primeFactorization(n):
    D = list(range(n + 1))
    for i in range(2, int(n ** 0.5) + 1):
        if D[i] == i:
            for j in range(i, n + 1, i):
                if D[j] == j:
                    D[j] = i
    return D

def resolve():
    N = I()
    A = LI()

    # pairwise判定
    is_pc = True
    D = primeFactorization(max(A))
    pf = set()
    for i in A:
        tmp = i
        cnt = collections.Counter()
        while tmp != 1:
            cnt[D[tmp]] += 1
            tmp //= D[tmp]
        fact = set(cnt.keys())
        if pf & fact:
            is_pc = False
            break
        else:
            pf |= fact
    
    # setwise判定
    is_sc = False
    if not is_pc:
        gcd = A[0]
        for i in A[1:]:
            gcd = math.gcd(i, gcd)
        if gcd == 1:
            is_sc = True

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

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
dp = [0 for i in range(a[-1])]
p = [0 for i in range(a[-1])]
for i in range(n):
    p[a[i]-1] += 1
ans = 1
for i in range(2,a[-1]+1):
    if dp[i-1] == 1:
        continue
    u = 0
    k = 1
    while i*k <= a[-1]:
        dp[i*k-1] = 1
        if p[i*k-1] != 0:
            u += p[i*k-1]
        k += 1
    if u == n:
        ans = -1
    elif u > 1:
        ans = min(ans,0)
if ans == 1:
    print('pairwise coprime')
elif ans == 0:
    print('setwise coprime')
elif a[0] == 1:
    print('setwise coprime')
else:
    print('not coprime')