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: Wrong Answer

Solution code:
#E_Coprime
import math
import functools

# エラトステネスの篩
        
def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    D_prime = [i for i in range(n+1)] 
    D_prime[0] = 0
    D_prime[1] = 1
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            D_prime[i] = i
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
            D_prime[j] = i
    return D_prime

    

Fnum_list2 = []
# 入力
N = int(input())
A = list(map(int,input().split()))

#Fnum_list = eratosthenes(N)

A.sort()
Amax = A[-1]
Fnum_list2 = primes(Amax)
j = A[0]
ans = 1
#Fnum_list = eratosthenes(N)
Ai_primes     = set()
Ai_primes_add = []
gcd_num = 0
for i in range(len(A) -1 ):
    p = A[i]
    while p != 1:
        j = p
        p = int (p / Fnum_list2[j])
        if Fnum_list2[j] in Ai_primes:
            ans = 0
        else:
            Ai_primes_add.append(Fnum_list2[j])
    if Fnum_list2[j] in Ai_primes:
        break
    else:
        Ai_primes |= set(Ai_primes_add)
        Ai_primes_add.clear()

gcd_num = functools.reduce(math.gcd,A)

if ans == 0:
    if gcd_num == 1:
        ans = 2

# 出力
if ans == 1:
    print("pairwise coprime")
else:
    if ans == 2:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
def eratosthenes2(n):
    D=[-1]*(n+1)
    D[0]=0
    D[1]=1
    for i in range(2, n+1):
        if D[i] == -1:
            D[i] = i
            for j in range(i*i, n+1, i):
                if D[j] == -1:
                    D[j] = i
    return D

N=int(input())
A=list(map(int,input().split()))
maxA=max(A)
D=eratosthenes2(maxA)
print(maxA)

Submission status: Wrong Answer

Solution code:
def eratosthenes2(n):
    D=[-1]*(n+1)
    D[0]=0
    D[1]=1
    for i in range(2, n+1):
        if D[i] == -1:
            D[i] = i
            for j in range(i*i, n+1, i):
                if D[j] == -1:
                    D[j] = i
    return D

N=int(input())
A=list(map(int,input().split()))
maxA=max(A)
D=eratosthenes2(maxA)
count=[0]*(maxA+1)
for x in A:
    pre=x+1
    while x>1:
        if pre!=D[x]:
            count[D[x]]+=1
            pre=D[x]
        x//=D[x]
maxc=max(count)
if maxc==N:
    print('not coprime')
elif maxc==1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
n = int(input())
a = list(map(int, input().split()))
maxn = 10 ** 6 + 1
numl = [0] * maxn
flag = 0
for i in a:
    for j in range(2, maxn):
        if(j*2 > i):
            if(numl[i] == 0):
                numl[i]+=1
            else:
                flag = 1
            break
        if(i % j == 0):
            if(numl[j] == 0):
                numl[j]+=1
            else:
                flag = 1
                break
    if(flag == 1):
        ans = a[0]
        for k in range(1, n):
            ans = gcd(ans, a[k])
        if(ans == 1):
            print("setwise coprime")
        else:
            print("not coprime")
        break
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
n = int(input())
a = list(map(int, input().split()))
maxn = 10 ** 6 + 1
numl = [0] * maxn
flag = 0
for i in a:
    for j in range(2, maxn):
        if(j*j > i):
            if(numl[i] == 0):
                numl[i]+=1
            else:
                flag = 1
            break
        if(i % j == 0):
            if(numl[j] == 0):
                numl[j]+=1
            else:
                flag = 1
                break
    if(flag == 1):
        ans = a[0]
        for k in range(1, n):
            ans = gcd(ans, a[k])
        if(ans == 1):
            print("setwise coprime")
        else:
            print("not coprime")
        break
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
sz=10**6+1
primes=[1]*(sz)

# l=[]
for i in range(2,sz):
	if primes[i]==1:
		primes[i]=i
		for j in range(i*i,sz,i):
			if primes[j]==1:
				primes[j]=i


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

# print(primes[:10])
ok=True

cnt=[0]*(10**6+1)
for i in arr:
	while i>1 :
		cnt[primes[i]]+=1
		while i!=1 and i%primes[i]==0:
			i//=primes[i]
		if cnt[primes[i]]>1:
			ok=False
		# print(i)
	if not ok :
		break


g=gcd(arr[0],arr[1])
for i in range(n):
	g=gcd(g,arr[i])

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

Submission status: Wrong Answer

Solution code:
from math import gcd
sz=10**3+1
primes=[1]*(sz)

# l=[]
for i in range(2,sz):
	if primes[i]:
		for j in range(i*i,sz,i):
			primes[j]=0

l=[i for i,j in enumerate(primes[2:],2) if j]
n=int(input())
arr=list(map(int,input().split()))

# print(l)
r=(max(arr))**(0.5)
ok=True
# print(r)
for pr in l:
	
	cnt=0
	for i in range(n):
		if arr[i]%pr==0:
			cnt+=1
	if cnt>1:
		ok=False
		break
	if pr**2>r:
		break

g=gcd(arr[0],arr[1])
for i in range(n):
	g=gcd(g,arr[i])

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

Submission status: Wrong Answer

Solution code:
from math import gcd
sz=10**3+1
primes=[1]*(sz)

l=[]
for i in range(2,sz):
	if primes[i]:
		l.append(i)
		for j in range(i*i,sz,i):
			primes[j]=0


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

ok=True
for pr in l:
	cnt=0
	for i in range(n):
		if arr[i]%pr==0:
			cnt+=1
	if cnt>1:
		ok=False
		break
g=gcd(arr[0],arr[1])
for i in range(n):
	g=gcd(g,arr[i])

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

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N = n1()
A = nn()

MAX = 10**6
dp = defaultdict(list)

p = 2
while p < MAX:
    i = p * 2
    while i < MAX:
        dp[i].append(p)
        i += p

    p += 1
    while len(dp[p]) >= 1:
        p += 1

if max(A) == 1:
    print("pairwise coprime")
    exit(0)

dic = defaultdict(list)

for ai in A:
    fact = dp[ai]
    for x in fact:
        dic[x].append(ai)

maxlen = 0
for k, v in dic.items():
    maxlen = max(len(v), maxlen)

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

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N = n1()
A = nn()

if max(A) == 1:
    print("pairwise coprime")
    exit(0)

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

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

dic = defaultdict(list)

for ai in A:
    fact = factorization(ai)
    for i in range(len(fact)):
        dic[fact[i][0]].append(ai)

maxlen = 0
for k, v in dic.items():
    maxlen = max(len(v), maxlen)

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

Submission status: Wrong Answer

Solution code:

import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N = n1()
A = nn()

if max(A) == 1:
    print("pairwise coprime")
    exit(0)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1)) + 1):
        if temp % i == 0:
            cnt = 0
            if 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

dic = defaultdict(list)

for ai in A:
    fact = factorization(ai)
    for i in range(len(fact)):
        dic[fact[i][0]].append(ai)

maxlen = 0
for k, v in dic.items():
    maxlen = max(len(v), maxlen)

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

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N = n1()
A = nn()

if max(A) == 1:
    print("pairwise coprime")
    exit(0)

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

dic = defaultdict(list)

for ai in A:
    fact = factorization(ai)
    for i in range(len(fact)):
        dic[fact[i][0]].append(ai)

#print(dic)

maxlen = 0
for k, v in dic.items():
    maxlen = max(len(v), maxlen)

#print(dic)

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

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N = n1()
A = nn()

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

dic = defaultdict(list)

for ai in A:
    fact = factorization(ai)
    for i in range(len(fact)):
        dic[fact[i][0]].append(ai)

#print(dic)

maxlen = 0
minlen = 10**6
for k, v in dic.items():
    maxlen = max(len(v), maxlen)
    minlen = min(len(v), minlen)

#print(dic)

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

Submission status: Wrong Answer

Solution code:

#素因数分解（10**6まで）
def soinsu_bunkai(m):
    pf=set()
    mm =m
    for i in pri_num:
        while mm %i==0:
            pf.add(i)
            mm //=i
    if mm !=1:
        pf.add(mm)
    return pf

    # 初期入力
import math
import sys
from bisect import bisect_left
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
intersect =set()
pair_w =set()

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
#pri_num =prime_numbers(sq_pri +10 )
pri_num =[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]

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    A.sort()
    x =bisect_left(A,2)
    if N -x >= 78498 +1:
        ans ="setwise coprime"
        sys.exit() #10**6以下の素数は78498個、鳩ノ巣原理により必ず素因数が重複、または素数以外の数が出ている
    else:
        for a in A:
            aa =soinsu_bunkai(a)
            if intersect & aa:
                print("setwise coprime")
                sys.exit() #共通要素があったらpair_wではない→set_w
            intersect |=aa

        ans ="pairwise coprime"
print(ans)

Submission status: Wrong Answer

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

def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor: GCD)を求める
    計算量: O(log(min(a, b)))
    """
    while b:
        a, b = b, a % b
    return a


def multi_gcd(array: list) -> int:
    """arrayのGCDを求める"""
    n = len(array)
    ans = array[0]
    for i in range(1, n):
        ans = gcd(ans, array[i])
    return ans


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


def get_prime_factors(num):
    res = []
    while mindiv[num] != 1:
        res.append(mindiv[num])
        num //= mindiv[num]
    return res


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


mindiv = make_mindiv_table(10 ** 6)

set_primes = set()
flag = True
for val in a:
    set_ = set(get_prime_factors(val))
    for v in set_:
        if v in set_primes:
            flag = False
        set_primes.add(v)
    if not flag:
        break
else:
    print("pairwise coprime")
    exit()

gcd_ = multi_gcd(a)
if gcd_ == 1:
    print("setwise coprime")
    exit()

print("no coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
flag=0
N=int(input())
A=list(map(int,input().split()))
Max=max(A)
a=[0]*(Max+1)
for i in A:
    a[i]+=1
s=2
while s*s<=Max:
    if sum(a[s::s])>=2:
        flag=1
        break
    s+=1
if flag==0:
    print('pairwise coprime')
else:
    r=A[0]
    for i in A:
        r=gcd(r,i)
    if r==1:
        print('setwise coprime')
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(max(A)+1)]
C = [0 for i in range(max(A)+1)]

for i in range(2, len(B)):
  if B[i] != 0:
    continue
  for j in range(i, len(B), i):
    B[j] = i
flag1 = False
flag2 = False

def func(X):
  while X>1:
    x = B[X]
    if C[x]==1:
      flag1 = True
    elif C[x]==N-1:
      flag2 = True
    C[x] += 1
    while X%x==0:
      X = X//x
for a in A:
  func(a)
if flag2:
  print("not coprime")
elif flag1:
  print("setwise coprime")
else:
  print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
import sys

MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p,MAXN+1,p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1
    
def pf(a):
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
        
    return list(tmp)




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

A=[i for i in A if i != 1]

g = 1
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    sys.exit()
    

B=[pf(A[i]) for i in range(len(A))]
B=sum(B,[])

if len(B) == len(set(B)):
    print("pairwise coprime")
    
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import collections
from math import gcd
import sys

MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p,MAXN+1,p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1
    
def pf(a):
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
        
    return list(tmp)

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

A=[i for i in A if i != 1]

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

B=[pf(A[i]) for i in range(len(A))]
B=sum(B,[])

if len(B) == len(set(B)):
    print("pairwise coprime")
    
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math,sys

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


ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n=int(math.sqrt(10**6))+20
count=[0 for _ in range(max_n)]

def fac(x):
    F=True
    for i in range(2,int(math.sqrt(x))+2):
        if x%i ==0:
            if count[i]>0:
                F=False
            count[i]+=1
    return F

flag=True
for each in Ns:
    flag_2=fac(each)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
    sys.exit()

gcd_ans=Ns[0]
for i in range(1,n):
    gcd_ans= math.gcd( gcd_ans , Ns[i])

if gcd_ans==1:
    print(ans_s)
else:
    print(ans_n)

"""
import math,sys

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

ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n= 10**6+100
count=[0 for _ in range(max_n)]

def Era(nn):
    prime = []
    limit = math.sqrt(nn)
    data = [i + 1 for i in range(1, nn)]
    while True:
        p = data.pop(0)
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def fac(x,T):
    P_list=Era(x)
    F=True
    ii=0
    pp=P_list[ii]
    while  pp < math.sqrt(x)+1:
        if x%pp==0:
            if T[pp]>0:
                F=False
            T[pp]+=1
        ii+=1
        pp=P_list[ii]
    return F

flag=True
for each in Ns:
    flag_2=fac(each,count)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
else:       
    gcd_ans=Ns[0]
    for i in range(1,n):
        gcd_ans= math.gcd( gcd_ans , Ns[i])
    if gcd_ans==1:
        print(ans_s)
    else:
        print(ans_n)
"""

Submission status: Wrong Answer

Solution code:
import collections

MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p,MAXN+1,p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1
    
def pf(a):
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
        
    return list(tmp)

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

A=[i for i in A if i != 1]

B=[pf(A[i]) for i in range(len(A))]
B=sum(B,[])

if len(B) == len(set(B)):
    print("pairwise coprime")
    
elif collections.Counter(B).most_common()[0][1] == len(A):
    print("not coprime")
    
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = sorted(list(map(int,input().split())))
d = [0]*(10**6+2)
d[1] = 1

def yakusuu(M):
    P = [M]
    for k in range(2,math.floor(math.sqrt(M))+1):
        if M % k == 0:
            P.append(k)
            P.append(M//k)
    return sorted(list(set(P)))

for e in A:
    for y in yakusuu(e):
        d[y] += 1


if max(d) == 1:
    print("pairwise coprime")
    exit(0)

t = A[0]
for e in A:
    t = math.gcd(e,t)

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

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = sorted(list(map(int,input().split())))
d = [0]*(10**6+2)
d[1] = 1

def yakusuu(M):
    P = [M]
    for k in range(2,math.floor(math.sqrt(M))+1):
        if M % k == 0:
            P.append(k)
            P.append(M//k)
    return set(P)

f = 1
for e in A:
    for y in yakusuu(e):
        if d[y] != 0:
            f = 0
            break
        else:
            d[y] = 1
    if f == 0:
        break
if f == 1:
    print("pairwise coprime")
    exit(0)

t = A[0]
for e in A:
    t = math.gcd(e,t)

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

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
d = [0]*(10**6+2)
d[1] = 1

def yakusuu(M):
    P = [M]
    for k in range(2,math.floor(math.sqrt(M))+1):
        if M % k == 0:
            P.append(k)
            P.append(M//k)
    return set(P)

f = 1
for e in A:
    for y in yakusuu(e):
        if d[y] != 0:
            f = 0
            break
        else:
            d[y] = 1
    if f == 0:
        break
if f == 1:
    print("pairwise coprime")
    exit(0)

t = A[0]
for e in A:
    t = math.gcd(e,t)

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

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
d = [0]*(10**6+2)

def yakusuu(N):
    P = [N]
    for k in range(2,math.floor(math.sqrt(N))+1):
        if N % k == 0:
            P.append(k)
            P.append(N//k)
    return set(P)

f = 1
for e in A:
    for y in yakusuu(e):
        if d[y] != 0:
            f = 0
            break
        else:
            d[y] = 1
    if f == 0:
        break
if f == 1:
    print("pairwise coprime")
    exit(0)
t = A[0]
for e in A[1:]:
    t = math.gcd(e,t)
if t == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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

def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
d = 0
for i,o in enumerate(A):
    if i == N:
        break
    for l in A[i+1:]:
        print(o,l)
        if math.gcd(o,l) != 1:
            d = 1
            break
            
if d == 0:
    print('pairwise coprime')
    exit()

if gcd(*A) == 1:
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Wrong Answer

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

def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
d = 0
for i,o in enumerate(A):
    for l in A[i:]:
        if math.gcd(o,l) != 1:
            d = 1
            break
            
if d == 1:
    print('pairwise coprime')
    exit()

if gcd(*A) == 1:
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
n=int(input())
l=list(map(int,input().split()))
mal=max(l)
e=[i for i in range(mal+1)]

x=2
while x*x <= mal:
    if x == e[x]:
        for m in range(x, len(e), n):
            if e[m] == m:
                e[m] = x
    x+=1
#print(e)    
s=set()
f=0
for i in l:
  st = set()
  while i > 1:
    st.add(e[i])
    i//=e[i]
  if not s.isdisjoint(st):
    f=1
    break
  s |= st

if f==0:
    print('pairwise coprime')
    exit()
p=l[0]
for i in range(1,n):
    p=gcd(p,l[i])
if p==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
n=int(input())
l=list(map(int,input().split()))
mal=max(l)
e=[i for i in range(mal+1)]

x=2
while x*x <= mal:
    if x == e[x]:
        for m in range(x, len(e), n):
            if e[m] == m:
                e[m] = x
    x+=1
#print(e)    
s=set()
f=1
for i in l:
  st = set()
  while i > 1:
    st.add(e[i])
    i//=e[i]
  if not s.isdisjoint(st):
    f=1
    break
  s |= st

if f==0:
    print('pairwise coprime')
    exit()
p=l[0]
for i in range(1,n):
    p=gcd(p,l[i])
if p==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

def factorization(n):
    temp = n
    f=0
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            f=1
            yak[i]+=1

    if temp!=1:
        f=1
        yak[temp]+=1

    if  f==0:
        yak[n]+=1

    return

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

c=max(A)
yak=[0]*(c+1)

for i in A:
    c=gcd(c,i)
    factorization(i)

if max(yak)==1:
    print('pairwise coprime')

elif c==1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

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

MAX = 1000005

is_prime = [1]*MAX
D = [None]*MAX
is_prime[0],is_prime[1] = 0,0

for i in range(2,MAX):
  if is_prime[i]:
    D[i] = i
    for j in range(i*2,MAX,i):
      is_prime[j] = 0
      D[j] = i
      
counts = [0]*MAX
pair = True

for a_i in a:
  if a_i == 1:
    continue
  while True:
    p = D[a_i]
    if counts[p]>0:
      pair = False
    counts[p] += 1
    if p == a_i:
      break
    else:
      a_i //= p

if pair:
  print('pairwise coprime')
else:
  g = a_i
  for a_i in a:
    g = math.gcd(a_i,g)
  if g == 1:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

ans=[0]*(A[-1]+1)
c=A[-1]

for i in A:
    c=gcd(c,i)
    for j in range(2, i//2):
        if i%j==0:
            ans[j]+=1
    ans[i]+=1   

if max(ans)==1:
    print('pairwise coprime')

elif c==1:
    print('setwise coprime')

else:
    print('not coprime')