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:
import math
from functools import reduce
n=int(input())
a=list(map(int, input().split()))
q=0
size=10**6

judge=[0]*(size)

for i in range(len(a)):
    num=a[i]
    if judge[num-1]==-1:
        q=1
    else:
        for j in range(int(num**0.5),1,-1):
            if num%j==0:
                if judge[j-1]==-1:
                    q=1
                    break
                else:
                    judge[j-1]=-1
                if judge[num//j-1]==-1:
                    q=1
                    break
                else:  
                    judge[num//j-1]=-1

    if judge[num-1]<0:
        q=1
    else:
        judge[num-1]=-2

m=min(a)
for i in range(2,int(m**0.5)+1):
    if m%i==0:
        m=i
        break

if q>0:
    for i in range(n):
        if a[i]%m!=0:
            q=2
            break

if q==0:
    print('pairwise coprime')

elif q==2:
    print('setwise coprime')
        
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb  # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

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")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

# ===============================================================================================
### START ITERATE RECURSION ###
from types import GeneratorType


def iterative(f, stack=[]):
    def wrapped_func(*args, **kwargs):
        if stack: return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
                continue
            stack.pop()
            if not stack: break
            to = stack[-1].send(to)
        return to

    return wrapped_func


#### END ITERATE RECURSION ####

# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input

def out(var): sys.stdout.write(str(var))  # for fast output, always take string

def lis(): return list(map(int, inp().split()))

def stringlis(): return list(map(str, inp().split()))

def sep(): return map(int, inp().split())

def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n

def nextline(): out("\n")  # as stdout.write always print sring.

def testcase(t):
    for p in range(t):
        solve()

def printlist(a):
    for p in range(0, len(a)):
        out(str(a[p]) + ' ')

def lcm(a, b): return (a * b) // gcd(a, b)


def ncr(n, r): return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))


def primesbelow(N):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
    correction = N % 6 > 1
    N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N ** .5) // 3 + 1):
        if sieve[i]:
            k = (3 * i + 1) | 1
            sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
            sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

smallprimeset = set(primesbelow(1000000))
_smallprimeset = 1000000
def isprime(n, precision=7):
    # http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Algorithm_and_running_time
    if n < 1:
        raise ValueError("Out of bounds, first argument must be > 0")
    elif n <= 3:
        return n >= 2
    elif n % 2 == 0:
        return False
    elif n < _smallprimeset:
        return n in smallprimeset

    return True

# https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/

smallprimes = primesbelow(1000) # might seem low, but 1000*1000 = 1000000, so this will fully factor every composite < 1000000
def primefactors(n, sort=False):
    factors = []

    for checker in smallprimes:
        while n % checker == 0:
            factors.append(checker)
            n //= checker
        if checker > n: break

    if n < 2: return factors

    return factors


from functools import reduce

n=int(inp())
ar=lis()
tt=ar.count(1)
if (n-tt)<1000000:
    t=1
    for i in ar:
        k=primefactors(i)
        s=set(k)
        for temp in s:
            if temp not in smallprimeset:
                t=-1
                break
            else:
                smallprimeset.remove(temp)
    if t==1:
        print("pairwise coprime")
    else:
        k=reduce(gcd,ar)
        if k==1:
            print("setwise coprime")
        else:
            print("not coprime")
else:
    k = reduce(gcd, ar)
    if k == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
def primes(n):#nまでの素数を列挙0は入れちゃダメ
    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
    return is_prime
A = list(map(int,input().split()))
MAX = max(A)
prime = primes(MAX)
pri = [i for i in  range(2,MAX+1) if prime[i]]
n = len(pri)
cnt = defaultdict(int)
def factorization(n): #2以上の整数n => [[素因数, 指数], ...]の2次元リストを返す
    arr = []
    temp = n
    for i in pri:
        if i > int(n**0.5):
            break
        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 factorization1(n): #2以上の整数n => [[素因数, 指数], ...]の2次元リストを返す
    arr = []
    temp = n
    for i in pri:
        if i > int(n**0.5) or i > MAX/N:
            break
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        if temp > int(n**0.5) or temp >= MAX/N:
            arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
flag1 = 0
flag2 = 0
if N >= n+2:
    flag1 = 1
    for i in range(N):
        a = A[i]
        li = factorization1(a)
        for tu in li:
            b = tu[0]
            cnt[b] += 1
    for i in pri:
        a = cnt[i]
        if a == N:
            flag2 = 1
            break
    if flag2 == 1:
        print("not coprime")
    else:
        print("setwise coprime")
else:
    for i in range(N):
        a = A[i]
        li = factorization(a)
        for tu in li:
            b = tu[0]
            cnt[b] += 1
    for i in pri:
        a = cnt[i]
        if a == N:
            flag2 = 1
        if a >= 2:
            flag1 = 1
    if flag1 == 0:
        print("pairwise coprime")
    elif flag2 == 1:
        print("not coprime")
    else:
        print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math
def eratos(n):
    isprime = [[] for i in range(n+1)]
    # isprime[0] = 0
    isprime[1] = 1
    for i in range(2, int(math.sqrt(n))+1):
        if isprime[i] == []:
            j = i
        while j <= n:
            isprime[j] += [i]
            j = j + i
    return isprime

N = int(input())
A = list(map(int, input().split()))
isprime = eratos(10**6)
count = [0 for i in range(10**6+1)]

for ai in A:
    if ai == 1:
        continue
    for i in isprime[ai]:
        count[i] += 1
max_c = max(count)
if max_c == 1:
    print('pairwise coprime')
elif max_c == N:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import math, sys
from functools import reduce

def gcd_set(n):
    return reduce(math.gcd, n)

N = int(input())
A = set(map(int, input().split()))
for a in A:
    for b in A:
        if a == b:
            continue
        if math.gcd(a, b) != 1:
            if gcd_set(A) == 1:
                print('setwise coprime')
            else:
                print('not coprime')
            sys.exit()
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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


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


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


def is_coprime(x, y):
    return math.gcd(x, y) == 1


allCoprime = True
allNotCoprime = True

minA = min(A)
for x in range(N):
    if not is_coprime(A[x], minA) and A[x] != minA:
        allCoprime = False

if gcd_list(A) == 1:
    allNotCoprime = False

if allCoprime:
    print("pairwise coprime")
elif allNotCoprime:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]

primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    while k**2 <= mA:
      sgn[k] = 1
      k += add
  k += 2
#prime_num が用意されているとき
def factorization(n):
  M = n
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if counter[p] == 0:
          counter[p] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      return False
  return True


g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)
if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split(" ")))
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            arr.append(i)
    if temp!=1:
        arr.append(temp)

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

    return arr

base=A[0]
condition=0
check=0
for i in range(1,len(A),1):
    arr=factorization(A[i])
    for a in arr:
        if base%a==0:
            check=1
    base*=A[i]
    if check==1:
        condition=1
        break

if condition!=0 and i==1:
    base=A[0]
    for j in range(i,len(A),1):
        base=gcd(base,A[j])
    if base!=1:
        condition=2
ans=["pairwise coprime","setwise coprime","not coprime"]
print(ans[condition])

Submission status: Wrong Answer

Solution code:
import math

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

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)

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

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

    return arr


def setwise_coprime(a):
    b=a.copy()
    one=b.pop()
    for i in range(n-1):
        two=b.pop()
        one=math.gcd(one,two)
    if one==1:
        return True
    return False

def pairwise_coprime(an):
    frui=[0]*(10**6+1)
    for a in an:
        soinnsuu_list=factorization(a)
        for i in soinnsuu_list:
            if frui[i]==1:
                return False
            for k in range(1,int(10**6/i)+1):
                frui[i*k]=1
    return True


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

Submission status: Wrong Answer

Solution code:
from math import gcd
def primes(n):
    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
    return [i for i in range(n + 1) if is_prime[i]]
p = primes(4000)
c = [0]*4001
# print(len(p))

n = int(input())
# a = [999983] * 100 + [1]
a = list(map(int,input().split()))
a = [1] * (1 in a) + [i for i in a if i != 1]
# print(a)
n = len(a)

f = 1
if n>80000:
    # print("not coprime")
    # exit()
    f = 0
g = 0
c1 = 0
if len(set(a)) != n:
    f = 0
for i in a:
    g = gcd(g,i)
    if f == 1:
        for j in p:
            if i%j == 0:
                c[j] += 1
                if c[j] > 1:
                    f = 0
if g == 1:
    if f == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")
# print(a,g,f)

Submission status: Wrong Answer

Solution code:
def primeFactors(x):
    factors = []
    i = 2
    while x > 1:
        if x % i == 0:
            x = x // i
            factors.append(i)
        else:
            i += 1
    return factors

N = int(input())
Arr = list(map(int, input().split()))
factors = [primeFactors(x) for x in Arr]
nc = False
for factor in factors[0]:
    this = True
    for f in factors:
        if not factor in f:
            this = False
            break
    if this:
        nc = True
        break

if nc:
    print("not coprime")
else:
    sc = False
    seen = set()
    for factor in factors:
        for f in factor:
            if f in seen:
                sc = True
                break
            else:
                seen.add(f)
        if sc: break
    if sc:
        print("setwise coprime")
    else:
        print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
ans1 = A[0]
ans2 = 0
f = True
for i in range(1, N):
    ans1 = math.gcd(ans1, A[i])
    for j in range(i+1, N):
        ans2 = math.gcd(A[i-1],A[j-1])
        if (ans2 > 1):
            f = False
            break
    if f==False and ans1 !=1:
        break


if f:
    print('pairwise coprime')
else:
    if ans1==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

# エラトステネスの篩による素数判定（0:非素数，1：素数）
def make_is_prime(N):
    prime = [1 for i in range(N+1)]
    prime[0] = prime[1] = 0
    for i in range(2,N+1):
        if prime[i] == 0: continue
        j = i**2
        while (j <= N):
            prime[j] = 0
            j += i
    return prime

a = make_is_prime(10**3+1)
b = []

for i in range(len(a)):
    if a[i] == 1:
        b.append(i)

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

pc = 1
sc = 1

for i in b:
    count = 0
    for j in range(N):
        if A[j]%i == 0:
            count += 1
    if count >= 2:
        pc = 0
    if count == N:
        sc = 0
        break

if pc == 1 and len(set(A)) == N:
    print("pairwise coprime")
elif sc == 1 and len(set(A)) >1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math

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

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    tmp = b
    b = a
    a = tmp 
while a % b != 0:
    a, b = b, a % b
    if n == 2 and b == 1:
        ans = "pairwise coprime"
        failed = True

for i in range(2, n):
    a = als[i]
    if a < b:
        tmp = b
        b = a
        a = tmp 
    while a % b != 0:
        a, b = b, a % b
    if b == 1:
        ans = "setwise coprime"
        break

existeven = False

failed = False

for i in range(n):
    if als[i] >= 2 and als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

maxa = max(als)

if not failed:
    for i in range(3, int(math.sqrt(maxa))+1, 2):
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        ans = "pairwise coprime"

print(ans)

Submission status: Wrong Answer

Solution code:
##https://www.codechef.com/viewsolution/20131475

from math import gcd

def main():
    n = int(input())
    A = list(map(int , input().split()))
    N = max(A)+1

    sv = [i for i in range(N)]
    for i in range(2 ,int(N**2)+1) :
        if i * i >= N : break
        if sv[i] < i : continue
        for j in range(i * i , N , i) :
            sv[j] = min(sv[j] , i)

    def getPrimes(a) :
        pr = []
        if a == 1 : return pr
        pr.append(sv[a])
        while a > 1 :
            if sv[a] != pr[-1] :
                pr.append(sv[a])
            a //= sv[a]
        return pr

    np = [0] * N
    F = [0] * N

    for a in A :
        pr = getPrimes(a)
        for i in range(1 << len(pr)) :
            prod , nb = 1 , 0
            for j in range(len(pr)) :
                if i & (1<<j) :
                    prod *= pr[j]
                    nb += 1
            F[prod] += 1
            np[prod] = nb

    ans = 0
    for i in range(N) :
        cnt = F[i]
        cnt = (cnt * (cnt-1))//2
        if np[i] & 1 : ans -= cnt
        else : ans += cnt

    if ans == (n*(n-1))//2:
        print("pairwise coprime")
        exit()
    
    return
    A.sort()
    d = A[0]

    for i in A:
        d = gcd(i,d)
        if d == 1 or d > 10**2:
            break

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

main()

Submission status: Wrong Answer

Solution code:


def seachPrimes(N):
    max = int(N ** 0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

def main():
    primes = seachPrimes(10**3)
    n = int(input())
    A = list(map(int, input().split()))


    cnts = []
    for prime in primes:
        cnt = 0
        for a in A:
            if a % prime == 0:
                cnt += 1
        cnts.append(cnt)
    if max(cnts) == n or (min(A) == max(A) and min(A) != 1):
        print("not coprime")
    elif max(cnts) >= 2:
        print("setwise coprime")
    else:
        print("pairwise coprime")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math 
def findMaxGCD(arr, n): 
    high = max(arr) 
    divisors = [0] * (high + 1) 
    for i in range(n) : 

        for j in range(2, int(math.sqrt(arr[i])) + 1): 

            if (arr[i] % j == 0) : 
                divisors[j] += 1
                break
                if (j != arr[i] // j): 
                    divisors[arr[i] // j] += 1
                    break
                    
    pairwise_coprime=True
    setwise_coprime=True
    for i in range(2,high):
        if (divisors[i] >= 2): 
            pairwise_coprime=False
        if divisors[i]==n:
            setwise_coprime=False
    if pairwise_coprime:
        print('pairwise coprime')
    elif setwise_coprime:
        print('setwise coprime')
    else:
        print('not coprime')
            
n = int(input())
a= [int(i) for i in input().split()]
findMaxGCD(a, n)

Submission status: Wrong Answer

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

m = max(A)
is_prime = [True] * (m + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, m + 1):
    for j in range(i * 2, m + 1, i):
        is_prime[j] = False
primes = [i for i in range(m + 1) if is_prime[i]]

Amap = {a: 0 for a in range(1, m + 1)}
for a in A:
    Amap[a] += 1

# Pmap[p]はAにでてくるpの倍数の数
Pmap = {p: 0 for p in primes}
Pmap[1] = 0
for p in primes:
    for a in range(p, m + 1, p):
        Pmap[p] += Amap[a]

score = max(Pmap.values())

if score == 1:
    print('pairwise coprime')
elif score != n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

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

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

s = [0] * (max(a)+1)
for i in range(n):
  for j in range(2,max(a)):
    if j*j > max(a):
      break
    if a[i] % j == 0:
      s[j] += 1
  
if tmp != 1:
  print('not coprime')
elif max(s) != 1:
  print('setwise coprime')
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

def lcm(x,y):
  return x*y//gcd(x,y)

n=int(input())

a=input().split()

gcd_all=10000000
lcm_all=1

for i in a:
  if gcd_all!=1:
    gcd_all=gcd(gcd_all,int(i))
  lcm_all=lcm(lcm_all,int(i))
  lcm_all=lcm_all//int(i)
  
if lcm_all==1:
  print("pairwise coprime")
elif gcd_all==1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
import sys

def sieve(N):
    # 昇順リストの用意
    A_list = [i for i in range(2, N+1)]
    limit = A_list[-1]

    # ふるいにかけられたかどうかを示すbooleanの辞書
    sieve = {i: True for i in A_list}

    # 順にふるいにかける
    for a in A_list:
        if not sieve[a]:
            continue
        for i in range(2*a, limit+1, a):  # 2a, 3a, 4a, ..., と調べる
            if i in sieve:
                sieve[i] = False

    # 結果をまとめる
    primes = []
    for a in A_list:
        if sieve[a]:
            primes.append(a)
    return primes


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


sorted_A = sorted(A)

is_pairwise = True  #同じ数が含まれるかどうか
global_gcd = A[0]
for i in range(1, N):
    if A[i-1] == A[i]:
        is_pairwise = False
    global_gcd = gcd(global_gcd, A[i])
    
if global_gcd > 1:
    print('not corprime')
    sys.exit()
elif not is_pairwise:
    print('setwise coprime')
    sys.exit()
else:
    # 素数列挙
    primes = sieve(A[-1]// 2)
    
    for p in primes:
        divided_once = False
        for a in sorted_A:
            if a % p == 0:
                if divided_once:
                    print('setwise corprime')
                    sys.exit()
                divided_once = True
    print('pairwise corprime')

Submission status: Wrong Answer

Solution code:
#ここまでテンプレ
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))

import math

ans = a[0]
sosu = a[0]

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 set(a)

an = prime_factorize(a[0])
flag = True

for i in range(1, n):
    ans = math.gcd(ans, a[i])
    pri = prime_factorize(a[i])
    for j in pri:
        if j in an:
            flag = False
    
if ans == 1 and flag == True:
    print("pairwise coprime")
elif ans == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

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

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)
    if temp != 1:
        arr.append(temp)
    if arr == []:
        arr.append(n)
    return arr


def list_check(list1, list2):
    for i in list1:
        if i in list2:
            return True
    return False
    # return set(list1).issubset(list2)

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

so_list = []
no_pairwise = False
no_setwise = False
for a in A:
    fac_list = factorization(a)
    # print(fac_list, so_list, no_pairwise)
    if list_check(fac_list, so_list):
        no_pairwise = True
        break
    else:
        so_list.extend(fac_list)

'''
if gcd_list(A) != 1:
    no_setwise = True
'''

if not no_pairwise:
    print("pairwise coprime")
elif not no_setwise:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# --------------------------------------------------------------

n = int(input())
lis = map(int,input().split())

now = 0
total = 0

flg1 = 0
flg2 = 0

for i in range(n-1):
    if i>0:
        total = gcd(now,i+1)
    now = gcd(i,i+1)
    
    if now != 1:
        flg1 = 1
    if total==1:
        flg2 = 1

if flg1==1:
    print('pairwise coprime')
elif flg2==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()))
a = A[0]
s = 0
t = 0
for i in range(1,N):
    a = math.gcd(A[i],a)  # すべてでGCD()=1かどうか
    b = math.gcd(A[i-1],A[i]) # どこかでGCD != 1になるかどうか
    if b > 1:
        t = 1
if t != 1:
    print("pairwise coprime")
else:
    if a > 1:
        print("not 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()))
flag =1
if reduce(math.gcd, a) != 1:
        print("not coprime")
        flag = 0
if flag == 1:
        for i  in range(n):
                for j in range(i, n):
                        if i != j:
                                if math.gcd(a[i], a[j]) != 1:
                                        print("setwise coprime")
                                        flag = 0
                                        break
                        else:
                                continue
                break
if flag == 1:
        print("pairwise coprime")