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:
#!/usr/bin/env python3
import math

def cal_primes(N):
    candidate = [*range(2, N+1)]
    primes = []

    while candidate[0]**2 <= N:
        primes.append(candidate[0])
        candidate = [*filter(lambda x: x % candidate[0] != 0, candidate)]
    
    primes.extend(candidate)
    return primes

def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N == 2:
        if math.gcd(A[0],A[1]) == 1:
            ans = 0
        else:
            ans = 2
    else:
        A.sort()
        nums = [0] * (10**6+1)
        for a in A:
            nums[a] += 1
        
        plist = cal_primes(10**6//2)

        ans = 0
        for p in plist:
            now = p
            cnt = 0
            while now <= 10**6:
                cnt += nums[now]
                now += p
            if cnt == N:
                ans = 2
                break
            elif cnt > 1:
                ans = 1
    
    if ans == 0:
        print('pairwise coprime')
    elif ans == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import sys
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
ma = max(a)
pc = True

if ma == 1:
    print("pairwise coprime")
    sys.exit()
    
bb = Counter(a)
    
if len(bb) - 1 == n - bb[1]:
    pc = True
elif len(bb) != n :
    pc = False
    
cu = [0]*(ma+1)
for i in a:
    cu[i] = 1

for i in range(2,ma+1):
    aa = 0
    for j in range(i,ma+1,i):
        aa += cu[j]
    if aa > 1:
        pc = False
        break

gc = a[0]
for i in a[1:]:
    gc = math.gcd(i,gc)
    
if pc:
    print("pairwise coprime")
elif gc == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from collections import Counter

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

def sieve(n):
    res=list(range(n))

    i=2
    while i*i<n:
        if res[i]<i:
            i+=1
            continue

        for j in range(i*i,n,i):
            if res[j]==j:
                res[j]=i
        i+=1
    
    return res
min_factor=sieve(10**6+1)
def factor(x):
    res=set()
    while x>1:
        res.add(min_factor[x])
        x//=min_factor[x]
    
    return list(res)

lst=[]

for aa in a:
    lst+=factor(aa)

cnt=list(Counter(lst).items())

if len(cnt)==len(lst):
    print('pairwise coprime')
else:
    for k,v in cnt:
        if v==n:
            print('not coprime')
            exit(0)
    
    print('setwise coprime')

Submission status: Accepted

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

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

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

    return arr


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

a.sort()

jd=[True]*(a[-1]+10)

pairwise=True

for i in a:
    if i==1:
        continue
    
    xxx=factorization(i)
    for j in xxx:
        if jd[j[0]]==True:
          jd[j[0]]=False
        else:
            pairwise=False
            break
    
    if pairwise==False:
        break

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

if 1 in a:
    print('setwise coprime')
    exit()


zzz=factorization(a[0])

for i in zzz:
    pin=i[0]
    flag=True
    cnt=0
    for j in a:
      if j%pin==0:
          cnt+=1
    
    if cnt==n:
        print('not coprime')
        exit()


print('setwise coprime')

Submission status: Accepted

Solution code:
def divisor(i):
    s = []
    for j in range(1, int(i ** (1 / 2)) + 1):
        if i % j == 0:
            s.append(i // j)
            s.append(j)
    return sorted(set(s))

import math

n = int(input())
a = list(map(int, input().split()))
ans = ["pairwise coprime", "setwise coprime", "not coprime"]
"""
if n >= 200000:
    g = a[0]
    for i in a:
        g = math.gcd(i, g)
        if g == 1:
            print(ans[1])
            exit()
    print(ans[2])
    exit()
"""
if n <= 1000000:
    x = [0] * 1000005
    for i in a:
        s = divisor(i)
        t = 1
        for j in s:
            if j == 1:
                continue
            if x[j] == 1:
                t = 0
                break
            x[j] = 1
        if t == 0:
            break
    if t == 1:
        print(ans[0])
        exit()
    g = a[0]
    for i in a:
        g = math.gcd(i, g)
        if g == 1:
            print(ans[1])
            exit()
    print(ans[2])
    exit()

Submission status: Accepted

Solution code:

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

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

def isPrime(n):
	if n <= 1:
		return False
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	i = 3
	while i * i <= n:
		if n % i == 0:
			return False
		i += 2
	return True

P = [n for n in range(10**3 + 1) if isPrime(n)]
used = [False for _ in range(10**6 + 1)]

isPC = True
s = A[0]

n = A[0]
for p in P:
	if p > n:
		break
	while n % p == 0:
		used[p] = True
		n = n // p
if n > 1:
	used[n] = True

for n in A[1:]:
	if isPC:
		a = n
		for p in P:
			if p > a:
				break
			if a % p == 0 and used[p]:
				isPC = False
				break
			while a % p == 0:
				a = a // p
		if a > 1 and used[a]:
			isPC = False
		else:
			used[a] = True

	if s > 1:
		s = gcd(s, n)

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip() # sys.setrecursionlimit(10**6)
from functools import reduce
from collections import defaultdict
from math import gcd

n = int(input())
A = list(int(x) for x in input().split())

if reduce(gcd, A) != 1:
    print("not coprime")
    exit()

def is_prime_miller_rabin(n):  # ミラー-ラビン素数判定法
    if n < 2:
        return False
    elif n in {2, 3, 5, 7, 11}:
        return True
    elif n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 or n % 11 == 0:
        return False

    if n < 4_759_123_141:
        witnesses = [2, 7, 61]
    elif n < 341_550_071_728_321:
        witnesses = [2, 3, 5, 7, 11, 13, 17]
    else:
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]

    d = n - 1
    d = d // (d & -d)

    for a in witnesses:
        y = pow(a, d, n)
        if y == 1:
            continue
        t = d
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1:
                return False
            t <<= 1
    return True

def find_factor_rho(n):  # ポラード・ロー素因数分解法
    if n < 2:
        return None
    m = 1<<n.bit_length() // 8 + 1
    for c in range(1, 99):
        def f(x):
            return (x * x + c) % n

        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if is_prime_miller_rabin(g):
                return g
            elif is_prime_miller_rabin(n // g):
                return n // g
    return None

def prime_factorize_dict(n):
    prime_dict = defaultdict(int)
    i = 2
    while i * i <= n:
        while n % i == 0:
            n //= i
            prime_dict[i] += 1
        i += 1 + i % 2
        if i != 101 or n < 1<<20:
            continue
        while n > 1:
            if is_prime_miller_rabin(n):
                prime_dict[n] = n = 1
                break
            j = find_factor_rho(n)
            while n % j == 0:
                n //= j
                prime_dict[j] += 1
    if n > 1:
        prime_dict[n] += 1
    return prime_dict

# ---------------------- #

pset = set()
for a in A:
    for k in prime_factorize_dict(a).keys():
        if k in pset:
            print("setwise coprime")
            exit()
        pset.add(k)

print("pairwise coprime")

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
from functools import reduce
from math import gcd
g=reduce(lambda x,y:gcd(x,y),A,0)
if g>1:
    print('not coprime')
    exit()
def prime(N):
    p=set(range(2,N+1))
    for i in range(int(N**.5)+1):
        if i in p:
            p-=set(range(i*2,N+1,i))
    return p
p=prime(1000)
r=1
s=set()
for a in A:
    f=0
    for x in p:
        if a%x==0:
            if f==0:
                p2=p.copy()
                f=1
            p2.remove(x)
        while a%x==0:
            a//=x
        if a==1:
            break
    if a>1:
        if 1000<a and a not in s:
            s.add(a)
        else:
            r=0
            break
    if f:
        p=p2
print(['setwise coprime','pairwise coprime'][r])

Submission status: Accepted

Solution code:
import math

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

# n以下の素数列挙(O(n log(n))
def primes(n):
    ans = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ans.append(i)
    return ans


def fctr1(n):
    f = []
    c = 0
    r = int(n ** 0.5)
    for i in range(2, r + 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


c = 0
for a in A:
    if a == 1:
        c += 1
    else:
        break


P = primes(A[-1])
L = len(P)

# MAX以下の素数の数より多い
if (N - c) <= L:
    USED = [False] * (10 ** 6 + 10)
    ok = True
    for a in A:
        if a == 1:
            continue

        f = fctr1(a)
        for x, c in f:
            if not USED[x]:
                USED[x] = True
            else:
                ok = False
                break

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

t = A[0]
for a in A:
    t = math.gcd(a, t)
    if t == 1:
        break

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

Submission status: Accepted

Solution code:
import sys,math
n=int(input())
a=list(map(int,input().split()))
sieve=[0]*(10**6+1)
numbers={}
flag=0
for i in range(n):
  if a[i] in numbers:
    numbers[a[i]]+=1
  else:
    numbers[a[i]]=1
pointer=2
while pointer<10**6+1:
  if sieve[pointer]==1:
    pointer+=1
    continue
  count=0
  pointer2=pointer
  while pointer2<10**6+1:
    if pointer2 in numbers:
      count+=numbers[pointer2]
    sieve[pointer2]=1
    pointer2+=pointer
  if count>=2:
    flag=1
    break
if flag==0:
  print('pairwise coprime')
  sys.exit()
ans=a[0]
for i in range(1,n):
  ans=math.gcd(a[i],ans)
if ans==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Accepted

Solution code:
import math

n = input()
As = list(map(int, input().split()))
gcd = As[0]
for a in As[1:]:
    tmp = gcd
    gcd = math.gcd(tmp, a)

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

era = [0] * (10**6 + 1)
for a in As:
    era[a] += 1
for d in range(2, 10**6+1):
    data = [i for i in range(d,10**6+1,d)]
    cnt = 0
    for i in data:
        cnt += era[i] 
    if cnt > 1:
        print("setwise coprime")
        exit()
print("pairwise coprime")

Submission status: Accepted

Solution code:
import math

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    N = int(input())
    A = list(map(int, input().split()))
    L = [False]*(max(A)+10)

    for i in range(N):
        divi =  make_divisors(A[i])
        for j in range(len(divi)):
            if L[divi[j]]==False:
                L[divi[j]] = True
            elif divi[j] != 1:
                gc = A[0]
                for k in range(1,N):
                    gc = math.gcd(gc,A[k])
                if gc == 1:
                    print('setwise coprime')
                    return
                else:
                    print('not coprime')
                    return


    print('pairwise coprime')
    return





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd

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

setgcd = A[0]
for i in range(N):
    setgcd = gcd(setgcd,A[i])
is_set = True
if setgcd != 1:
    is_set=False

M = max(A)
is_prime=[1]*(M+1)#Mまで行きたい
is_inA=[0]*(M+1)
for i in range(N):
    is_inA[A[i]]=1

is_pair = True
is_prime[0]=0
is_prime[1]=0
for i in range(2,M+1):
    count = 0
    if is_inA[i]==1:
        count=1
    if is_prime[i]==1:
        for j in range(2*i,M+1,i):
            is_prime[j]=0
            if is_inA[j]==1:
                count+=1
    if count >= 2:
        is_pair = False

if is_set and is_pair:
    print("pairwise coprime")
elif is_set:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

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

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
used = [False] * len(primes)
big = [0] * (10 ** 6)

g = A[0]
for v in A:
    g = gcd(v,g)
if g == 1:  
    works = 1
    for v in A:
        if v > 1:
            for i in range(len(primes)):
                if v % primes[i] == 0:
                    if used[i]:
                        works = 0
                        break
                    used[i] = True
                    while v % primes[i] == 0:
                        v //= primes[i]
                    if v == 1:
                        break
                    
            works -= big[v]
            big[v] = 1
            big[1] = 0
            
            if works != 1:
                break
    if works:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
n = int(input())
*arr, = map(int, input().split())

def pairwise_coprime(arr):
    mx = max(arr)
    data = [0] * (mx + 1)
    for v in arr:
        data[v] += 1
        if v > 1 and data[v] > 1:
            return False
    primes = [1] * (mx + 1)
    for v in range(2, mx + 1):
        if primes[v]:
            cnt = 0
            if data[v]:
                cnt += 1
            for nonprime in range(2 * v, mx + 1, v):
                primes[nonprime] = 0
                if data[nonprime]:
                    cnt += 1
            if cnt > 1:
                return False
    return True

def gcd(a, b):
    if a > b:
        a, b = b, a

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


def setwise_coprime(arr):
    common_gcd = arr[0]
    for i in range(1, len(arr)):
        common_gcd = gcd(common_gcd, arr[i])
    return common_gcd == 1


if pairwise_coprime(arr):
    print("pairwise coprime")
elif setwise_coprime(arr):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
import math


def simple_sol(N, A):
    is_pairwise_coprime = True
    for i in range(N - 1):
        for j in range(i + 1, N):
            g = math.gcd(A[i], A[j])
            if g == 1:
                continue
            is_pairwise_coprime = False
            break
        if not is_pairwise_coprime:
            break
    if is_pairwise_coprime:
        return 'pairwise coprime'
    g = A[0]
    for i in range(1, N):
        g = math.gcd(g, A[i])
        if g == 1:
            return 'setwise coprime'
    return 'not coprime'



def factorial(n): 
    f = []
    c = 0
    r = int(n**0.5)
    for i in range(2, r + 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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    # print(simple_sol(N, A))
    exponents = [0] *  (10 ** 6 + 1)
    is_pairwise_coprime = True
    for a in A:
        for x, e in factorial(a):
            if exponents[x] > 0:
                is_pairwise_coprime = False
                break
            exponents[x] = e
        if not is_pairwise_coprime:
            break
    if is_pairwise_coprime:
        print('pairwise coprime')
        return
    g = A[0]
    for i in range(1, N):
        g = math.gcd(g, A[i])
        if g == 1:
            print('setwise coprime')
            return
    print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
P = [1 for _ in range(10**6)]
P[0]=0
P[1]=0
for i in range(2,10**3+1):
    for j in range(i*i,10**6,i):
        P[j]=0
Q = []
for i in range(2,10**6):
    if P[i]==1:
        Q.append(i)
def gcd(x,y):
    while y>0:
        x,y = y,x%y
    return x
N = int(input())
A = list(map(int,input().split()))
a = A[0]
for i in range(1,N):
    a = gcd(a,A[i])
if a>1:
    print("not coprime")
else:
    hist = [0 for _ in range(10**6)]
    flag = 0
    for i in range(N):
        a = A[i]
        if P[a]==1:
            if hist[a]==0:
                hist[a]=1
            else:
                flag=1
                break
        else:
            for q in Q:
                if a%q==0:
                    if hist[q]==0:
                        hist[q]=1
                    else:
                        flag = 1
                        break
                    while a%q==0:
                        a = a//q
                if a==1:break
            if flag==1:break
    if flag==0:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Accepted

Solution code:
def factor(n):
    r = set()
    if n % 2 == 0:
        while n % 2 == 0:
            n //= 2
        r.add(2)
    i = 3
    while i * i <= n:
        if n % i == 0:
            while n % i == 0:
                n //= i
            r.add(i)
        i += 2
    if n > 1:
        r.add(n)
    return r

def main():
    N = int(input())
    A = list(map(int, input().split()))
    pairwise = True
    onef = factor(A[0])
    allf = onef.copy()
    
    for a in A[1:]:
        fa = factor(a)
        if pairwise:
            for f in fa:
                if f in onef:
                    pairwise = False
                    break
                onef.add(f)
        allf &= fa
        if not pairwise and not allf:
            return 'setwise coprime'
    if pairwise:
        return 'pairwise coprime'
    if len(allf) == 0:
        return 'setwise coprime'
    return 'not coprime'

print(main())

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

LEN = 1000000

ps = [[] for _ in range(LEN + 1)]
is_prime = [False] * (LEN + 1)
for i in range(2, LEN + 1):
    if not is_prime[i]:
        for j in range(i, LEN + 1, i):
            is_prime[j] = True
            ps[j].append(i)

def is_pairwise_coprime():
    s = set()
    for a in A:
        for p in ps[a]:
            if p in s:
                return False
            s.add(p)

    return True


def is_otherwise():
    m = min(A)

    for p in ps[m]:
        if all(map(lambda x: x % p == 0, A)):
            return True

    return False

if is_pairwise_coprime():
    print("pairwise coprime")
elif is_otherwise():
    print("not 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"

#nまでの素数の配列を返す関数
def primes(n):
    if n == 1:
        return []
    else:
        tbl = [True]*(n+1)
        pri = set([2])
        for i in range(2,n+1,2):
            tbl[i] = False
        k = 3
        while k <= n:
            if tbl[k]:
                pri.add(k)
                for i in range(k,n+1,k):
                    tbl[i] = False
            k += 2
        return pri

def main():
    n = int(ipt())
    ps = primes(10**3)
    d = defaultdict(bool)
    nm = 0
    a = []
    b = False
    for i in map(int,ipt().split()):
        if i != 1:
            a.append(i)
        else:
            b = True
    n = len(a)
    if n == 0:
        print("pairwise coprime")
        exit()
    g = a[0]
    if b:
        g = 1
    f = True
    if n > 78500:
        f = False

    for i in a:
        g = math.gcd(g,i)
        if f:
            ni = i
            for j in ps:
                ff = True
                while ni%j == 0:
                    if ff and d[i]:
                        f = False
                    d[i] = True
                    ff = False
                    ni //= j
                    if ni == 1:
                        break
            if ni == 1:
                continue
            if d[ni]:
                f = False
            d[ni] = True
        if g == 1 and not f:
            break

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




    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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

def gcd(a,b):
  while b:
    a,b = b,a%b
  return a  
  
n = int(input())
A = list(map(int,input().split()))

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

primes = [0]*(10**6+2)
primes[1] = 1

for a in A:
  B = set(prime_factorize(a))
  for b in B:
    primes[b]+=1
  
  
if p == 1:
  if max(primes)==1:
    print('pairwise coprime')
  else:
    print('setwise coprime')
else:
  print('not coprime')

Submission status: Accepted

Solution code:
#素因数分解(1に対しては空のリストを返す)
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

#入力の高速化
import sys
input = sys.stdin.readline

from collections import defaultdict
d = defaultdict(int)

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

v=prime_factorize(a[0])
v=set(v)
v=list(v)
for i in range(len(v)):
    d[v[i]]+=1

setwise=0
pairwise=0
for i in range(1,n):
    w=prime_factorize(a[i])
    flag=True
    w=set(w)
    w=list(w)
    for j in range(len(w)):
        if d[w[j]]!=0:
            pairwise=1
            if d[w[j]]==i:
                flag=False
        d[w[j]]+=1
    if flag:
        setwise=1


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

Submission status: Accepted

Solution code:
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")

def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7

from math import gcd

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

N = 10**6+1

prime = [True]*(N+1)
n = int(input())
a = Ri()
dic = {}
for i in a:
    dic[i] = dic.get(i, 0)+1
odic = {}
def sieve():
    for i in range(2,N):
        if prime[i]:
            for j in range(i , N,i):
                prime[j] = False
                if j in dic:
                    if i not in odic:
                        odic[i] = 0
                    odic[i]+= dic[j]
sieve()
# print(odic)
flag1,flag2 = True,True
for i in odic:
    if odic[i] >= 2:
        flag1 = False
    if odic[i] == n:
        flag2 = False

if not flag2:
    print("not coprime")
else:
    if flag1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Accepted

Solution code:
primeset = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009}

def gcd(n,m):
    while n:
        m,n = n,m%n
    return m

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

soinsu = set()
a,b = 0,0

def pariwise():
    global primeset,N,A,soinsu,a,b
    for i in range(N):
        a = A[i]
        b = set()
        for j in primeset:
            while a != 1 and a % j == 0:
                a //= j
                b.add(j)
        if a != 1:
            b.add(a)
        for j in b:
            if j in soinsu:
                return False
            soinsu.add(j)
    return True

def setwise():
    global primeset,N,A,soinsu,a,b
    a = A[0]
    for i in range(1,N):
        a = gcd(a,A[i])
    return (a == 1)

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
from math import gcd

primes = set([i for i in range(2,10**6+1)])

for i in range(2,1001):
  for j in range(i*2,10**6+1,i):
    if j in primes:
      primes.remove(j)
      
n = int(input())
a = list(map(int,input().split()))

ok = 1
tmp = a[0]

for i in range(1,n):
  tmp = gcd(tmp,a[i])
  
if tmp>1:
  print('not coprime')
else:
  used = set([])
  ok = 1
  
  for num in a:
    if num in primes:
      if num in used:
        ok = 0
      else:
        used.add(num)
    else:
      for i in range(2,int(num**0.5)+1):
        if num % i == 0:
          if i in used:
            ok = 0
          else:
            used.add(i)
          x = num//i
          if x!=i:
          
            if x in used:
              ok = 0
            else:
              used.add(x)
            
    if ok==0:
      break
      
  if ok==1:
    print('pairwise coprime')
  else:
    print('setwise coprime')