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:
A=list(range(2,10**3+1))
p=list()
while A[0]**2<=10**3+1:
	tmp=A[0]
	p.append(tmp)
	A=[e for e in A if e%tmp!=0]
primes = p+A

N = int(input())
L = map(int, input().split())
R = True
for p in primes:
  c = 0
  for l in L:
    if l%p==0:
      c += 1
  if c==N:
    print("not coprime")
    exit()
  if c>1:
    R = False
print("pairwise coprime" if R else "setwise coprime")

Submission status: Wrong Answer

Solution code:
def generate_primes(n):
    p = 2
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    return prime

prime = [True for i in range(10**6 + 1)]
generate_primes(10**6)
primenumbers = [ind for ind,val in enumerate(prime[2:],2) if val]
n = int(input())
ls = list(map(int,input().strip().split()))
maxi = max(ls)
flag = 0
ans = "pairwise coprime"
for prime_no in primenumbers:
    if prime_no>maxi: break
    f = 1
    c = 0
    for val in ls:
        if val%prime_no!=0:
            f = 0
        else:
            c += 1
        if f==0 and c>1: break
    if f:
        ans = "not coprime"
        break
    if c>1:
        flag = 1
if flag:
    ans = "setwise coprime"
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    primes = []
    isprime = [True for i in range(1001)]
    for i in range(2, 1001):
        if isprime[i]:
            primes.append(i)
            for j in range(i * i, 1001, i):
                isprime[j] = False
    x = a[0]
    f = True

    cnt = [0 for i in range(1000001)]
    for val in a:
        x = gcd(x, val)
        i = 0
        while i < len(primes) and primes[i] ** 2 <= val:
            if val % primes[i] == 0:
                cnt[primes[i]] += 1
                while val % primes[i] == 0:
                    val //= primes[i]
            i += 1
        if val > 1:
            cnt[val] += 1
    for i in range(2, n + 1):
        if cnt[i] > 1:
            f = False
            break
    if f:
        print('pairwise coprime')
    elif x == 1:
        print('setwise coprime')
    else:
        print('not coprime')



t = 1
while t > 0:
    solve()
    t -= 1

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from math import gcd
import math
# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
prime_list = callIsPrime(10**3)

N=int(input())
A=list(map(int,input().split()))
prime_flg = [True for i in range(10**3)]
pc_flg=True

if len(A)!=len(set(A)):
    pc_flg=False

x = A[-1]

for i in range(N):
    x=gcd(x,A[i])

A = list(set(A))

for i in range(len(A)):
    for j in range(len(prime_list)):
        p=prime_list[j]
        if A[i]%p == 0:
            if prime_flg[p]:
                prime_flg[p]=False
            else:
                pc_flg=False


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

Submission status: Wrong Answer

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n=int(input())

A=list(map(int,input().split()))
from math import sqrt
def eratosu(n):
  if not isinstance(n,int):
    raise TypeError("nがint型になってねえぞ")
  if n<2:
    raise ValueError('nが2よりちっちぇえぞ')
  prime = []
  limit = sqrt(n)
  data = [i+1 for i in range(1, n)]  #2,3,4,...,n
  while True:
    p = data[0]
    if limit <= p:
        return prime + data
    prime.append(p)
    data = [e  for e in data if e % p != 0]
PRIME=eratosu(10**6)
@lru_cache(maxsize=10**10)
def bunkai(n):
    ans=[]
    temp=n
    #そんな早くしなくてよかったり、何回もするわけじゃないなら、
    #for i in range(2,int(sqrt(n))+1): とかで
    primelist= PRIME
    for i in primelist:
        if i>sqrt(n):break
        if temp % i ==0:
            ji=0
            while temp%i==0:
                ji+=1
                temp//=i
            ans.append([i,ji])
    if ans==[]:return([[n,1]])  #素数のとき
    if temp!=1:
        ans.append([temp,1])  #4*5882353とか
    return ans

flag=1
seen=[0]*(10**6+1)
#print(bunkai(3))
for i in A:
    for l in bunkai(i):
        now=l[0] 
        if seen[now]!=0:
            flag=0
        seen[now]+=1
if flag:
    print("pairwise coprime")
elif max(seen)!=n:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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

def calc_primes(n):
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data

primes = calc_primes(int(math.sqrt(10**6)))

is_pairwise = False
prod = 1
all_gcd = A[0]
for a in A:
    all_gcd = math.gcd(all_gcd, a)
    if is_pairwise:
        g = math.gcd(prod, a)
        if g > 1:
            is_pairwise = False
        prod *= a

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 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


def can_factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  # ここにバグがないか心配
        if temp % i == 0:
            arr.append(i)

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

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

    return arr


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
if N > 10**4:
    flg = 0
    for a in A:
        g_set = gcd(g_set, a)
else:
    for a in A:
        g_set = gcd(g_set, a)
        for p, n in factorization(a):
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
def gcd(x,y):
  return y if x%y==0else gcd(y,x%y)

N=int(input())

A=list(map(int,input().split()))
primes=[];
isprime=[1 for i in range(0,1001)];
isprime[1]=0;isprime[0]=0
for i in range(2,1001):
  if isprime[i]:
    primes.append(i)
    j=2;
    while i*j<=1000:
      isprime[i*j]=0;
      j+=1
#s=set();


pc=1
s=[0 for i in range(0,1001)];
s2=set();
for i in range(N):
  a=A[i];
  
  for p in primes:
    if a==1:
      break
    if(a%p==0):
      #while(a%p==0):
      #  a//=p;
      #if p in s:
      if s[p]:
        pc=0
      #s.add(p)
      s[p]=1
    #if a>1000:
    #  if a in s2:
    #    pc=0
    #  s2.add(a)

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

Submission status: Wrong Answer

Solution code:
from math import gcd
def g(a):
    al=len(a)
    if al==2:
        return gcd(a[0],a[1])
    elif al==1:
        return a[0]
    return gcd(g(a[al//2:]),g(a[:al//2+1]))
n=int(input())
a=list(map(int,input().split()))
if g(a)!=1:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
inpl = lambda: list(map(int,input().split()))
def primes(N):
    P = []
    for i in range(2,N):
        sieve = 1
        for p in P:
            if p*p > i:
                break
            elif i % p == 0:
                sieve = 0
                break
        if sieve == 0:
            continue
        else:
            P.append(i)
    return P

N = int(input())
A = inpl()

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

P = primes(1000)
for p in P:
    n = 0
    for a in A:
        if a % p == 0:
            n += 1
            if n > 1:
                print('setwise coprime')
                exit()
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

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

npcf = False
for i in range(N - 1):
    for j in range(i + 1, N):
        if gcd(A[i], A[j]) != 1:
            npcf = True
            break
    if npcf:
        break

if not npcf:
    print('pairwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from sys import stdin
input=lambda : stdin.readline().strip()
from math import ceil,sqrt,factorial
from collections import deque
from bisect import bisect_left,bisect_right
def isPrime(n) : 
	# Corner cases 
	if (n <= 1) : 
		return False
	if (n <= 3) : 
		return True

	# This is checked so that we can skip 
	# middle five numbers in below loop 
	if (n % 2 == 0 or n % 3 == 0) : 
		return False

	i = 5
	while(i * i <= n) : 
		if (n % i == 0 or n % (i + 2) == 0) : 
			return False
		i = i + 6

	return True

# print all prime numbers 
# less than equal to N 
dp=[]
def printPrime(n): 
	for i in range(2, n + 1): 
		if isPrime(i): 
			dp.append(i)


n = 1000		
printPrime(n) 
# print(dp)
def gcd(a,b):
	while a%b!=0:
		a,b=b,a%b
	return b
n=int(input())
l=list(map(int,input().split()))
flag=1
a=l[n-1]
s=set()
z=list(l)
for i in range(n):
	j=0
	while l[i]>1 and j<len(dp):
		if l[i]%dp[j]==0:
			l[i]//=dp[j]
			if dp[j] in s:
				flag=0
				break
			while l[i]%dp[j]==0:
				l[i]//=dp[j]
			s.add(dp[j])
		j+=1
	if flag==0:
		break
	if l[i]>1:
		s.add(l[i])
if flag:
	print("pairwise coprime")
	exit()
a=z[0]
for i in range(1,n):
	a=gcd(max(a,z[i]),min(a,z[i]))
if a==1:
	print("setwise coprime")
	exit()
print("not coprime")

Submission status: Wrong Answer

Solution code:
def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

pl = eratosthenes(10**6)
pd = {}
for p in pl:
    pd[p] = 0

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


A.sort()

d = {}
ans = 0
if len(set(A)) != N:
    ans = 1
for i in range(N):
    if A[i] in d:
        ans = 1
        break
    if A[i] not in pd:
        primes = prime_decomposition(A[i])
        for p in primes:
            if p not in d:
                for j in range(1,(10**6)//p+1):
                    d[j*p] = 0
            else:
                ans = 1
                break




if ans == 0:
    print('pairwise coprime')
else:
    def gcd(a, b):
    	while b:
    		a, b = b, a % b
    	return a
    a = A[0]
    for i in range(N):
        a = gcd(a,A[i])
    if a==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd


def func(A):
    n = len(A) - len(set(A))
    if n > 0 and n+1 != A.count(1):
        return False
    is_A = [False] * (10**6+1)
    for a in A:
        is_A[a] = True
    n = 0
    for i in range(2, 10**6+1, 2):
        if is_A[i]:
            n += 1
    if n > 1:
        return False
    for i in range(3, 10**6+1, 2):
        n = 0
        for j in range(i, 10**6+1, 2*i):
            if is_A[j]:
                n += 1
        if n > 1:
            return False
    return True


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    if func(A):
        print('pairwise coprime')
    elif reduce(gcd, A) == 1:
        print('setwise coprime')
    else:
        print('not coprime')
    

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
import sys
import math
N=int(input())
alist=list(map(int,input().split()))
alist.sort()

all_GCD=alist[0]
for i in range(1,N):
  all_GCD=math.gcd(all_GCD,alist[i])
  if all_GCD==1:
    break
else:
  print("not coprime")
  sys.exit(0)
  
aset=set(alist)
if len(aset)<N:
  print("setwise coprime")
  sys.exit(0)

lcm_MOD=1
prod_MOD=1
for i in range(N):
  lcm_MOD=lcm_MOD*alist[i]//math.gcd(lcm_MOD,alist[i])
  lcm_MOD%=MOD
  prod_MOD*=alist[i]
  prod_MOD%=MOD
#print(lcm_MOD,prod_MOD)

if lcm_MOD==prod_MOD:
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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

check1 = False
check2 = True

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
def prime_decomposition(x):
  i = 2
  ls = []
  while i * i <= x:
    while x % i == 0:
      x /= i
      ls.append(i)
    i += 1
  if x > 1:
    ls.append(x)
  return ls
  

if gcd_list(A) == 1:
  check1 = True
  
  A.sort()
  for i in set(prime_decomposition(A[0])+prime_decomposition(A[N-1])):
    for j in A[1:]:
      if j % i == 0:
        check2 = False
        break
    if not check2:
      break

else:
  check1 = False
  check2 = False
    
if check1 and check2:
  print("pairwise coprime")
elif check1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
from functools import reduce


def calc_ggcd(arr):
    return reduce(gcd, arr)


def decomposition(n):
    i = 2
    is_coprime = True
    if appear[n]:
        is_coprime = False
    else:
        appear[n] = True
    while i * i <= n:
        if n % i == 0:
            if appear[i]:
                is_coprime = False
            else:
                appear[i] = True
        i += 1
    return is_coprime


n = int(input())
a = list(map(int, input().split()))
appear = [False] * (max(a) + 1)
keep_pair_coprime = True
for aa in a:
    if not decomposition(aa):
        keep_pair_coprime = False

        # 素因数分解 O(√N)
global_gcd = calc_ggcd(a)
if keep_pair_coprime:
    print('pairwise coprime')
elif global_gcd == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

def max_gcd_pair(S):
    # Assumption 1: S is the list of numbers
    # Assumption 2: There are no duplicates in S

    s = set(S)
    m = max(S)

    res = 0
    i = m

    while(i > 0):
        a = i
        cnt = 0
        while (a<=m): # a maxed at max of the list
            if a in s:   
               cnt += 1
            a += i

        if cnt >= 2:  # we have found the result
            res = i
            break

        i = i -1 

    return res

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

if max_gcd_pair(a) <= 1:
    print('pairwise coprime')
    sys.exit()

import math
from functools import reduce

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

if gcd(*a) == 1:
    print('setwise coprime')
    sys.exit()

else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

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

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

if ans!=1:
    print('not coprime')

else:
    for i in range(50):
        for j in range(i+1,n):
            if math.gcd(a[i],a[j])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
lis = list(map(int,input().split()))
lis.sort()
num = lis[0]
for nu in lis:
    num = math.gcd(num,nu)
exist = [0 for i in range(max(lis)+1)]
if num != 1:
    print("not coprime")
    exit()
for nu in lis:
    if nu != 1:
        for i in range(2,math.ceil(math.sqrt(nu))+1):
            if nu % i == 0:
                if exist[i] == 1:
                    print("setwise coprime")
                    exit()
                else:
                    exist[i] = 1
                    while nu % i == 0:
                        nu //= i
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")
def primes(n):
    ass = []
    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]:
            ass.append(i)
    return ass

#solve
def solve():
    n = II()
    a = LI()
    M = 10 ** 6 + 1
    p = [True] * M
    p[0] = False
    p[1] = False
    d = [-1] * M
    for xi in range(2, M):
        if p[xi]:
            d[xi] = xi
            for i in range(xi * 2, M, xi):
                p[i] = False
                if d[i] == -1:
                    d[i] = xi
    res = defaultdict(int)
    flg = 0
    for ai in a:
        tmp = []
        if d[ai] == -1:
            res[ai] = 1
            tmp = [ai]
        else:
            while d[ai] != -1:
                tmp.append(d[ai])
                ai = ai // d[ai]
        for t in set(tmp):
            if res[t]:
                flg = 1
            res[t] = 1
        if flg:
            break
    else:
        print("pairwise coprime")
        return
    g = a[0]
    for i in a:
        g = math.gcd(g, i)
    if g == 1:
        print("setwise coprime")
        return
    print("not coprime")
    
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

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

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

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

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

N = getN()
A = getList()

pair = True
semi = True
# not divisible
# 全部互いに素かどうか
judge = [0] * (10 ** 6 + 1)

now = A[0]
for i in A[1:]:
    now = gcd(now, i)
if now > 1:
    semi = False


for i in A:
    judge[i] += 1

for i in range(2, 10 ** 6 + 1):
    cnt = 0
    for j in range(i, 10 ** 6 + 1, i):
        cnt += judge[i]
    if cnt > 1:
        pair = False
        break

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

Submission status: Wrong Answer

Solution code:
import math

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
#pairwise coprime どの2つをとっても共通素因数がない
#setwise coprime すべてに共通する素因数が存在しない
#左から見ていって、素因数の個数をカウントしていく…？
#setwise はエラトステネスの篩を再帰的に行う
#pairwise はそもそも、maxまでの素数の個数までしか存在し得ない
N = int(input())
A = [int(hoge) for hoge in input().split()]
Pairwise = False
Setwise = False
SOSUU = [0]*(10**6+10)
A.sort()
Fail = False
G = A[0]
for a in A:
    G = math.gcd(G,a)
if G != 1:
    print("not coprime")
    exit()

if len(A) <= 80000:
    for a in A:
        Fact = factorization(a)
        for f in Fact:
            if f[0]==1:continue
            if SOSUU[f[0]] > 0:
                Fail = True
                break
            else:
                SOSUU[f[0]] += 1
        if Fail:
            break
    if not Fail:
        Pairwise = True

if Pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
def sieve_eratosthenes(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes

N = int(input())
B = list(map(int,input().split()))
A = []
for i in range(N):
    if B[i]!=1:
        A.append(B[i])
N = len(A)
if N==0:
    print("pairwise coprime")
else:
    P = sieve_eratosthenes(10**6)
    Ps = []
    for i in range(10**6):
        if P[i]==1:
            Ps.append(i)
    PN = len(Ps)

    if N>PN+1:
        print("not coprime")
    else:
        flag = 0
        pf={}
        for i in range(N):
            pf1 = {}
            m=A[i]
            for i in range(2,int(m**0.5)+1):
                while m%i==0:
                    pf1[i]=pf1.get(i,0)+1
                    m//=i
            if m>1:pf1[m]=1
            for i in pf1.keys():
                pf[i]=pf.get(i,0)+1
                if pf[i]>1:
                    flag = 1
        if flag==0:
            print("pairwise coprime")
        else:
            import fractions
            ans = A[0]
            for i in range(1, N):
                ans = fractions.gcd(ans, A[i])
            if ans==1:
                print("setwise coprime")
            else:
                print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
numbers = list(map(lambda x: int(x), input().split()))
if_set_has_gcd = False
if_pair_has_gcd = False

max_divider = int(max(numbers) ** 0.5) + 1

for divider in range(2, max_divider + 1):
    num_divided = sum([each % divider == 0 for each in numbers])
    if num_divided == n:
        if_set_has_gcd = True
    if num_divided >= 2:
        if_pair_has_gcd = True

# print(if_set_has_gcd, if_pair_has_gcd)    
if not if_pair_has_gcd:
    print('pairwise comprime')
    sys.exit()
    
if not if_set_has_gcd:
    print('setwise comprime')
    sys.exit()
    
print('not comprime')

Submission status: Wrong Answer

Solution code:
def generate_primes(n):
    p = 2
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    return prime

prime = [True for i in range(10**6 + 1)]
generate_primes(10**6)
primenumbers = [ind for ind,val in enumerate(prime[2:],2) if val]
n = int(input())
ls = list(map(int,input().strip().split()))

flag = 0
ans = "pairwise coprime"
for prime_no in primenumbers:
    f = 1
    c = 0
    for val in ls:
        if val%prime_no!=0:
            f = 0
        else:
            c += 1
        if f==0 and c>1: break
    if f:
        ans = "not coprime"
        break
    if c>1:
        flag = 1
if flag:
    ans = "setwise coprime"
print(ans)

Submission status: Wrong Answer

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

A = sorted(A)

ansN = A[0]
for i in range(1, n):
    ansN = math.gcd(ansN, A[i])
if ansN > 1:
    print('not coprime')
else:
    a0 = A[0]
    ans2 = True
    for a in A[1:]:
        ans2 = ans2 and math.gcd(a0, a) == 1
    if ans2:
        print('pairwise coprime')
    else:
        print('setwise coprime')

Submission status: Wrong Answer

Solution code:
def eratosthenes(mx, sss):
    array = [1 for _ in range(mx + 1)]
    array[0] = array[1] = 0
    pair_wise = True
    set_wise = True
    cnt = 0
    for i in range(2, mx+1, 2):
        array[i] = 0
        if i in sss:
            cnt += 1
    if cnt > 1:
        pair_wise = False
    if cnt == len(sss):
        set_wise = False

    for i in range(3, mx + 1, 2):
        if not array[i]:
            continue
        cnt = 0
        for j in range(i, mx + 1, i):
            array[j] = 0
            if i in sss:
                cnt += 1
        if cnt > 1:
            pair_wise = False
        if cnt == len(sss):
            set_wise = False
            break

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

def resolve():
    n = int(input())
    a = set(map(int, input().split()))

    eratosthenes(max(a), a)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import math

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

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

if ans!=1:
    print('not coprime')

else:
    for i in range(10):
        for j in range(i+1,n):
            if math.gcd(a[i],a[j])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
import sys

N = int(input())
A = list(map(int, input().split()))
P = 10 ** 9 + 7

lcm = 1
flg = True
for a in A:
    if gcd(lcm, a) != 1:
        flg = False
        break
    lcm = (lcm*a)%P
if flg:
    print('pairwise coprime')
    sys.exit()


gcd_ = A[0]
for a in A[1:]:
    gcd_ = gcd(gcd_, a)
    if gcd_ == 1:
        print('setwise coprime')
        sys.exit()

print('not coprime')

Submission status: Wrong Answer

Solution code:
def PrimeFactorization(n):
    pf = set()
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            pf.add(i)
            n //= i
            while n % i == 0:
                n //= i
    if n > 1:
        pf.add(n)
    return pf


def resolve():
    import copy
    n = int(input())
    a = list(map(int, input().split()))
    pairwise = True
    union = PrimeFactorization(a[0])
    intersection = copy.deepcopy(union)
    for i in a[1:]:
        p = PrimeFactorization(i)
        if pairwise:
            for j in p:
                if j in union:
                    pairwise = False
                    break
                    union.add(j)
        intersection = intersection & p
    if intersection:
        print("not coprime")
        return
    if pairwise:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    resolve()