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:
from functools import reduce
import math
def gcd(x,y):
    if x%y==0:
        return y
    else:
        return (gcd(y, x%y))

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 ans(n, a):
    div = {}
    for i in range(n):
        k = (factorization(a[i]))
        for j in k:
            if j not in div:
                div[j]=1
            else:
                return True
    return False
    

n = int(input())
a = list(map(int, input().split()))
gcd = reduce(math.gcd, a)
if gcd !=1:
    print("not comprime")
else:
    if ans(n, a):
        print("setwise coprime")
    else:
        print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from collections import Counter


def eratosthenes(mx, arr):
    sss = set(arr) - {1}
    array = [1 for _ in range(mx + 1)]
    array[0] = array[1] = 0
    pair_wise = True
    set_wise = True

    if len(arr) - len([0 for i in arr if i == 1]) > len(sss):
        pair_wise = False


    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 = list(map(int, input().split()))
    eratosthenes(max(a), a)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))

am = max(a)

memo = [1] * (am+1)
memo[0] = 0
memo[1] = 0

p = -1
g = a[0]
d = defaultdict(int)

for ai in range(2, am+1):
    if ai == p:
        memo[ai] = 0
        continue
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0
    p = ai

cs = []
for i, memoi in enumerate(memo):
    if memoi:
        cs.append(i)

# print(cs)

def make_divisors(n):
    divisors = []
    lim = int(n**0.5)+1
    for i in cs:
        if i >= lim:
            break
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

f1 = 1 

for ai in a:
    for div in make_divisors(ai):
        if div != 1:
            d[div] += 1
            if d[div] > 1:
                f1 = 0
                break

if f1:
    print('pairwise coprime')
else:
    f2 = 1
    for key in d:
        if d[key] == N:
            f2 = 0
            break
    if f2:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
import os
import sys
from math import gcd

import numpy as np


def solve(inp):
    n = inp[0]
    aaa = np.unique(inp[1:])
    g = 0
    for i in range(len(aaa)):
        g = gcd(g, aaa[i])
    if g != 1:
        return -1

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

    if len(aaa) == n:
        pairwise = 1
    else:
        pairwise = 0

    one_count = 0
    for p in PRIMES:
        multiple_count = 0
        for i in range(len(aaa)):
            if aaa[i] % p == 0:
                multiple_count += 1
                aaa[i] //= p
                while aaa[i] % p == 0:
                    aaa[i] //= p

        if multiple_count > 1:
            pairwise = 0
        if multiple_count > 0:
            oc = (aaa == 1).sum()
            if oc > 1:
                one_count += oc - 1
            aaa = np.unique(aaa)

    if pairwise == 0:
        return 0

    if one_count + len(aaa) == n:
        return 1

    return 0


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(['setwise coprime', 'pairwise coprime', 'not coprime'][ans])

Submission status: Wrong Answer

Solution code:
import math
m = int(input())
a = list(map(int, input().split()))
max_int = math.ceil(math.sqrt(a[m-1]))

flg = 0
for i in range(max_int-1):
  tmp = list(map(lambda x: x % (i+2), a))
  c = tmp.count(0)
  if c == m:
    flg = 2
    break
  elif c >= 2:
    flg = 1
  
if flg == 1:
  print("setwise coprime")
elif flg == 2:
  print("not coprime")
else:
  print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def factorization(n):
    arr = set()
    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.add(i)

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

    if arr=={}:
        arr.add(n)

    return arr

N = int(input())
A = [factorization(int(n)) for n in input().split()]
#print(A)
ans = dict()
isPairwise = True

for st in A:
    for num in st:
        if num in ans.keys():
            ans[num] += 1
            isPairwise = False
        else:
            ans[num] = 1
#print(ans)
if isPairwise:
    print("pairwise coprime")
elif any([ans[n] >= N for n in ans.keys()]):
    print("not coprime")
else:
    print("set coprime")

Submission status: Wrong Answer

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

pc = True
gg = False
so = set()

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

for a in factorization(A[0]):
    if a > 1:
        so.add(a)

for a in A[1:]:
    ds = []
    for s in so:
        if a%s != 0:
            ds.append(s)
        else:
            pc = False
    for d in ds:
        so.discard(d)

if pc:
    print("pairwise coprime")
elif not so:
    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]]
n = int(input())
a = list(map(int, input().split()))
b = a[0]
c = 0
d = [0]*(10**6+1)
for i in range(1, n):
    b = gcd(b, a[i])
for i in range(n):
    d[a[i]] += 1
    if d[a[i]] == 2:
        c = 1
        break
if b != 1: print("not coprime")
elif c == 1: print("pairwise coprime")
else:
    data = primes(1000)
    count = [0]*(len(data))
    d = 0
    for j in range(len(data)):
        for i in range(n):
            if a[i]%data[j] == 0:
                if count[j] == 1:
                    print("setwise coprime")
                    d = 1
                    break
                else:
                    count[j] = 1
        if d == 1:
            break
    else: print("pairwise 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
    ssc = 1
    for j in range(N):
        if A[j]%i != 0:
            count += 1
    if count <= N-2:
        pc = 0
    if count == 0:
        sc = 0

if pc == 1:
    print("pairwise coprime")
elif sc == 1:
    print("setwise coprime")
else:
    print("not 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

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

ps = set()
for i,m in enumerate(sieve_eratosthenes(1000000)):
    if m == 1:
        ps.add(i)

from collections import defaultdict
import math

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
for i in range(n):
    if a[-1] == 1:
        a.pop()
        n -= 1
    else:
        break
if a == [] or len(a) == 1:
    print("pairwise coprime")
    exit()

a.sort()

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

if g == 1:
    if n > len(ps):
        print("setwise coprime")
    else:
        d = defaultdict(int)
        for i in range(n):
            f = factorization(a[i])
            for x, y in f:
                d[x] += 1
        for i in d.values():
            if i != 1:
                print("setwise coprime")
                exit()
        print("pairwise coprime")

else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

A = list(map(int, input().split()))
A.sort()
gcdAll = A[0]
isPairwise = True
check = set()
check.add(gcdAll)
for aj in A[1:]:
    if aj in check:
        continue
    gcdAll = math.gcd(gcdAll, aj)
    if not isPairwise:
        continue
    for ai in check:
        gcdNow = math.gcd(ai, aj)
        if gcdNow != 1:
            isPairwise = False
            break
    check.add(aj)

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

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
from math import gcd
n=int(stdin.readline())
a=list(map(int,stdin.readline().split()))
s=set(a)
p=2;d={}
N=max(a)+2
primes=[1]*N;not_pairwise=0
while p*p<=N:
    if primes[p]:
        for mul in range(p,N,p):
            primes[mul]=0
            if mul in s:
                d[p]=d.get(p,0)+1
                if d[p]>=2:not_pairwise=1;break;
        if not_pairwise:break
    p+=1
g=a[0]
for v in a:
    g=gcd(g,v)
if not_pairwise==0:print('pairwise coprime')
elif g==1:print('setwise coprime')
else:print('not coprime')

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
m = A[0]
M = A[-1]

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(M//2+1)
l = 0
for i in range(2, M//2+1):
    if checked[i]:
        continue
    
    while A[l] < i:
        l += 1
    
    if l == N-2:
        break
    
    tmp = 0
    for j in range(l, N):
        if A[j]%i == 0:
            tmp += 1
    
    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    
    if is_setwise_coprime == False:
        break
    
    n = i
    while n < M//2+1:
        checked[n] = 1
        n += i

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

Submission status: Wrong Answer

Solution code:
from math import gcd
least_prime = [0]*(10000009)
def leastPrimeFactor() : 
    n = 1000009
    least_prime[1] = 1
    for i in range(2, n + 1) : 
        if (least_prime[i] == 0) : 
            least_prime[i] = i 
            for j in range(2 * i, n + 1, i) : 
                if (least_prime[j] == 0) : 
                    least_prime[j] = i 
leastPrimeFactor()
n = input()
s = input().split(" ")
uniq = set()
count = 0
for c in s:
    if c == '1':
        count+=1
    uniq.add(least_prime[int(c)])
if len(uniq) == len(s) or count == len(s):
    print("pairwise coprime")
else:
    ans = 0
    for c in uniq:
        ans  = gcd(ans, c)
    if ans ==1:
        print("setwise coprime")
    else:
        print("not coprime")

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]

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

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

Submission status: Wrong Answer

Solution code:
import sys

prime = []

for i in range(2,1001):
    det = 0
    for j in range(2,int(i**(1/2))+1):
        if i%j==0:
            det = -1
            break
    if det == 0:
        prime.append(i)

N = int(input())
A = list(map(int,input().split()))
B = []###Aのうち1ではないもの
det = False###Aが1を含んでいたか否か

for i in range(N):
    if A[i] == 1:
        det = True
    else:
        B.append(A[i])

if len(B) <= len(prime):

    m = 1

    for p in prime:
        count = 0
        for b in B:
            if b%p==0:
                count += 1
        m = max(m,count)
        if m >= 2:
            break
    
    if m == 1:
        print('pairwise coprime')
        sys.exit(0)

if det:
    print('setwise coprime')

else:
    pp = prime[:]
    
    for b in B:
        pp_ = []
        for p in pp:
            if b%p == 0:
                pp_.append(p)
        pp = pp_[:]


        if pp == []:
            print('setwise coprime')
            sys.exit(0)
    
    print('not coprime')

Submission status: Wrong Answer

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

def sieve(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)
    for serial in range(3, num, 2):
        if serial >= sqrt:
            return input_list
        for s in range(serial ** 2, num, serial): 
            input_list[s] = False
            
def fact(num):
    arr = []
    temp = num
    for i in range(2, int(-(-num**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([num, 1])
    return arr

flg=True
prim=sieve(mxa+5)
table=[0]*(mxa+1)
for i in a:
  fc=fact(i)
  fct=[fc[j][0]for j in range(len(fc))]
  for j in fct:
    if table[j]==1:
      flg=False
    table[j]+=1

if flg:
  print("pairwise coprime")
elif n in table:
  print("not coprime")
else:
  print("setwise coprime")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 9
primes = [int(x) for x in '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'.split()]

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


def is_pairwise_coprime():
    for p in primes:
        count = 0
        for ai in a:
            if ai % p == 0:
                count += 1
        if count > 1:
            return False
    return True


def is_setwise_coprime():
    g = a[0]
    for i in range(n - 1):
        g = min(g, gcd(g, a[i + 1]))
    return g == 1


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

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
import math
ans = a[0]
for i in range(1, N):
    ans = math.gcd(ans, a[i])
anst = a[0]
for i in range(1, N):
    anst = anst * a[i] // math.gcd(anst, a[i])
y = 1
for i in range(N):
  y = y * a[i]
if ans != 1:
  print('not coprime')
else:
  if y == anst:
    print('pairwise comprime')
  else:
    print('setwise comprime')

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
dictA = dict()
for a in A:
  if a in dictA.keys():
    dictA[a] += 1
  else:
    dictA[a] = 1

def get_prime(p):
  result = []
  if p==1:
    return result
  else:
    integers = [1 for _ in range(p+1)]
    integers[0] = 0
    integers[1] = 0
    for i in range(p+1):
      if integers[i] == 1:
        result.append(i)
        for j in range(i,p+1,i):
          integers[j] = 0
    return result

def count_coprime(p):
  count = 0
  for a,v in dictA.items():
    if a%p == 0:
      count += v
  return count

maxA = max(A)
answer = 'pairwise coprime'
if maxA > 1:
  if max(dictA.values()) >= 2:
    answer = 'setwise coprime'
  for p in get_prime(1001):
    count = count_coprime(p)
    if count == N:
      answer = 'not coprime'
      break
    elif count >= 2:
      answer = 'setwise coprime'

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

def factorization(n):
    F = 0
    cnt = 1
    for i in range(2, int(-(-n**0.5//1))+1):
        if n%i==0:
            num[i] += 1
            cnt *= i
            F = 1
        if cnt == n:
            break
    if F == 0:
        num[n] += 1

N = i()
A = l()
num = [0]*(10**6+1)
for i in range(N):
    factorization(A[i])
if max(num) == 1:
    print('pairwise coprime')
elif max(num) == N:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

from math import gcd

def factor(n):
    ans = []
    i = 0
    while n & 1 == 0:
        n >>= 1
        i += 1

    if i > 0:
        ans.append((2, i))

    for i in range(3, int(n**.5) +1, 2):
        x, y = divmod(n, i)

        if y == 0:
            j = 1
            x1 = x
            while True:
                x1, y = divmod(x, i)
                if y == 0:
                    x = x1
                    j += 1
                else:
                    ans.append((i, j))
                    break
            n = x

    if n > 1:
        ans.append((n, 1))

    return ans

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = list(it)
    A.sort()
    M = A[-1]
    M1 = M + 1

    dp = [0] * M1

    g1 = A[0]
    for i, a in enumerate(A):
        g1 = gcd(g1, a)

        for x, _ in factor(a):
            for y in range(x, M1, x):
                if dp[y]:
                    for i in range(i, N):
                        a = A[i]
                        g1 = gcd(g1, a)
                        if g1 == 1:
                            print("setwise coprime")
                            return
                    print("not coprime")
                    return
                dp[y] = 1

    print("pairwise coprime")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
n=int(input()) 
c=list(map(int, input().split()))
ans = 1
 
import math
from functools import reduce
import fractions
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
 
for i in range(n-1):
    f=fractions.gcd(c[i],c[i+1])
    ans = max(ans,f)
 
Ans = gcd_list(c)
 
if ans == 1:
    print('pairwise coprime')
if ans > Ans and Ans == 1:
    print('setwise coprime')
if Ans > 1:
    print('not coprime')

Submission status: Wrong Answer

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

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

sa = set(A)
if len(sa) < N:
    print('setwise coprime')
    exit()

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
small_primes = []
while p*p <= MAXN:
    if sieve[p]:
        small_primes.append(p)
        c = 0
        if p in sa: c += 1
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
            if q in sa:
                c += 1
                if c > 1:
                    print('setwise coprime')
                    exit()
    p += 1

st = set()
for a in A:
    for p in small_primes:
        while a%p==0:
            a //= p
        if a==1: break
    else:
        if a in st:
            print('setwise coprime')
            exit()
        st.add(a)

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict
from functools import lru_cache


@lru_cache(None)
def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


def input():
    return sys.stdin.readline().strip()


def prime_factorization(N: int, d=None) -> dict:
    if d:
        primes = d
    else:
        primes = defaultdict(int)
    primes[1] = 1
    if N < 2:
        return primes
    i = 2
    while i * i <= N:
        while N % i == 0:
            primes[i] += 1
            N = N // i
        i += 1
    if N != 1:
        primes[N] = 1
    return primes


def main():
    n = int(input())
    A = [int(i) for i in input().split()]
    primes = defaultdict(int)
    is_pair_gcd = True
    # pre-process
    for i in range(n):
        if A[i] != 1:
            primes = prime_factorization(A[i], primes)

    set_gcd = A[0]
    for i in range(1, n):
        if set_gcd != 1:
            set_gcd = gcd(set_gcd, A[i])
        if is_pair_gcd:
            p = prime_factorization(A[i])
            for k, v in p.items():
                if k == 1:
                    continue
                if primes[k] != v:
                    is_pair_gcd = False
                    break
    if is_pair_gcd:
        print("pairwise coprime")
    elif not is_pair_gcd and set_gcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")

    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

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

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(min(1000,n-1)):
        for k in range(min(i+1,n-1),min(n,1000)):
            if math.gcd(a[i],a[k])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
import unittest
import collections


def f(n):
    e = set()
    if n < 2:
        return e
    if n % 2 == 0:
        e.add(2)
        n //= 2
        while n % 2 == 0:
            n //= 2
    i = 3
    while i <= n:
        if n % i == 0:
            e.add(i)
            n //= i
            while n % i == 0:
                n //= i
        i += 2
    return e


def is_pairwise_coprime(n, a):
    e = set()
    for i in range(n):
        e2 = f(a[i])
        if e & e2:
            return False
        e |= e2
    return True


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


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


def solve(n, a):
    if not is_setwise_coprime(n, a):
        return 'not coprime'

    a = [e for e in a if e > 1]
    n = len(a)
    # if n > 78498:
    #     return 'setwise coprime'
    # el
    if n < 10**3:
        if is_pairwise_coprime(n, a):
            return 'pairwise coprime'
    else:
        used_factor = set()
        for p in PRIMES:
            for i in range(n):
                if a[i] % p == 0:
                    if p in used_factor:
                        return 'setwise coprime'
                    else:
                        a[i] //= p
                        used_factor.add(p)
        return 'setwise coprime'
    if is_pairwise_coprime(n, a):
        return 'pairwise coprime'
    return 'setwise coprime'


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(n, a))


if __name__ == "__main__":
    main()


class Test(unittest.TestCase):
    def test_1(self):
        n = 3
        a = [3, 4, 5]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_2(self):
        n = 3
        a = [6, 10, 15]
        self.assertEqual(is_pairwise_coprime(n, a), False)
        self.assertEqual(is_setwise_coprime(n, a), True)
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_3(self):
        n = 3
        a = [6, 10, 16]
        self.assertEqual(solve(n, a), 'not coprime')

    def test_4(self):
        n = 3
        a = [1, 1, 1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_5(self):
        n = 3
        a = [1, 2, 2]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_6(self):
        n = 10
        a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_7(self):
        n = 11
        a = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_8(self):
        n = 2
        a = [1, 1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_9(self):
        n = 2
        a = [1, 2]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_10(self):
        n = 2
        a = [10**6, 10**6-1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_11(self):
        n = 3
        a = [10**6, 10**6-1, 10**6, ]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_12(self):
        n = len(PRIMES) * 2
        a = PRIMES + PRIMES
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_13(self):
        a = [1009, 1013, 1019, 1021, 1031, 1033, 1039,
             1049, 1051, 1061, 1063, 1069, 1087, ]
        n = len(a)
        self.assertEqual(solve(n, a), 'pairwise coprime')

Submission status: Wrong Answer

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

h = 0

for i in range(len(A)):
  if A[i] % 2 != 0:
    h = 1
    
l = 0
for i in range(len(A)):
  if A[i] % 3 != 0:
    l = 1
    
p = 0
for i in range(len(A)):
  if A[i] % 5 != 0:
    p = 1

if h == 0 or l == 0 or p == 0:
  print("not coprime")
  
elif A[0] % 2 != 0 or A[len(A)-1] % 2 != 0:
  print("pairwise coprime")
  
else:
  print("setwise coprime")