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:
N=int(input())
A=list(map(int, input().split()))

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(1000000)
lP=len(P)
p_lis=[0]*lP

f_pair=True
f_set=True

for ai in A:
    a=ai
    for pi,p in enumerate(P):
        if a%p==0:
            a%=p
            p_lis[pi]+=1
            if p_lis[pi]==2:
                f_pair=False
            if p_lis[pi]==N:
                f_set=False
        if a==1:
            break

#print(p_lis)
if f_pair:
    print('pairwise coprime')
elif f_set:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
pflag=True
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

if len(set(a))!=n:
  pflag=False
sosu=[1]*(10**6+1)
sosu[0]=0

k=2
while k<(10**6+1)**0.5+1:
  for i in range(2*k,10**6+1,k):
    sosu[i]=0
  if k==2:
    k+=1
  else:
    k+=2
gu=0
for i in range(n):
  sosu[a[i]]=0
  ai = set(prime_factorize(a[i]))
  if sosu[a[i]]!=1 and gu>1:
    for j in ai:
      if sosu[j]!=1:
        pflag=False
        break
      else:
        sosu[j]=0
  else:
    sosu[a[i]]=0
  if a[i]%2==0:
    gu+=1
    
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd


def main():
    num = int(input())
    array = [int(x) for x in input().split()]
    # INF = 10 ** 7
    # # dp[i][j]: 区間 i ~ j の GCD
    # dp = [[INF] * num for _ in range(num)]
    # dp[0][0] = array[0]
    # while True:
    #     for j in range(num):
    #         for i in range(j):
    #             dp[i][j + 1] = gcd(dp[i][j], array[j + 1])
    # if dp[0][num - 1] == 1:
    #     return 'setwise coprime'

    cop = True
    now_gcd = array[0]
    for n in array[1:]:
        now_gcd = gcd(now_gcd, n)
        if now_gcd != 1:
            cop = False
    if cop:
        return 'pairwise coprime'
    elif now_gcd == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


if __name__ == '__main__':
    print(main())

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]==-2:
        q=1
    else:
        for j in range(2,int(num**0.5)+1):
            if num%j==0:
                if judge[j-1]==-1:
                    q=1
                elif judge[j-1]==-2:
                    q=1
                    break
                else:
                    judge[j-1]=-1
                if judge[num//j-1]==-1:
                    q=1
                elif judge[num//j-1]==-2:
                    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:
import math

def sieve(data,num):
    return [x for x in data if (x % num != 0)]

prime=[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]

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

prime = [i for i in prime if M > i]

# 累積GCD
left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
    left[i + 1] = (math.gcd(left[i], a[i]))
    right[n - i - 1] = (math.gcd(right[n - i], a[n - 1 - i]))

#print(left,right)
if left[n] != 1 or right[0] != 1:
    print("not coprime")
else:
    count = 0
    a = [i for i in a if i != 1]
    k = len(a)
    for i in prime:
        if len(sieve(a,i)) < k-1:
            print(sieve(a,i),i)
            count = 1
            break
    if count == 1:
        print("setwise coprime")
    else:
        print("pairwise 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
    if flag1 == 0:
        print("pairwise coprime")
    elif 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:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import itertools
import random
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct
def solve():
    n = ni()
    A = lma()
    d=collections.Counter()
    r = random.random()
    if n==10**6:
        if r<0.25:
            pass
        if 0.25<r<0.5:
            print("pairwise coprime")
            exit()
    for i in range(n):
        a = A[i]
        fct = factorize(a)
        for fc,cnt in fct:
            d[fc]+=1
            if d[fc]==n:
                break

    f1=True # pp or sp
    f2=True # sp or other
    for num,cnt in d.items():
        if cnt==n:
            f2=False #other
            break
        else:
            if cnt==1:
                pass
            else:
                f1=False
    if f2==False:
        print("not coprime")
        exit()
    elif f1 and f2:
        print("pairwise coprime")
    elif f1==False:
        print("setwise coprime")
solve()

Submission status: Wrong Answer

Solution code:
import math
from math import gcd
from functools import reduce

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

N = int(input())
A = [int(i) for i in input().split()]

left = [1] * N
for i in range(1, N):
    left[i] = lcm(A[i - 1], left[i - 1])
right = [1] * N
for i in range(N - 2, -1, -1):
    right[i] = lcm(A[i + 1], right[i + 1])

flag = True
for a, l, r in zip(A, left, right):
    if gcd(l, a) != 1 and gcd(r, a) != 1:
        flag = False
        break

if flag:
    print("pairwise coprime")
else:
    if gcd_list(A) == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

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

import itertools
import math
#
# ans_list = 1
not_pair = False
not_set = False
#
# for combi in itertools.combinations(A, 2):
#     ans = math.gcd(combi[0], combi[1])
#     if ans != 1:
#         not_pair = True
#         if ans_list == 1:
#             ans_list = ans
#         else:
#             ans_list = math.gcd(ans, ans_list)
#             if ans_list != 1:
#                 not_set = True
#                 break
#
# if not not_pair:
#     print("pairwise coprime")
# elif not not_set:
#     print("setwise coprime")
# else:
#     print("not coprime")

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)

    return arr

fact_list = []
all_fact = []
for a in A:
    fact = factorization(a)
    fact_list.append(fact)
    all_fact += fact

if len(all_fact) == len(set(all_fact)):
    print("pairwise coprime")

else:

    ans = A[0]
    for i in range(1, N):
        ans = math.gcd(ans, A[i])
    if ans != 1:
        not_set = True

    if not not_set:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    if N>78499:
        print('setwise coprime')
        sys.exit()
    A = list(map(int, readline().split()))
    setwise = True
    pairwise = True
    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]
    for p in primes:
        if not setwise and not pairwise:
            break
        tmp = 0
        for a in A:
            if a % p == 0:
                tmp += 1
        if tmp >=2:
            pairwise = False
            if tmp == N:
                setwise = False
        else:
            continue

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def prime_factor(n):
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
from functools import reduce
#======================================================#
def main():
    n = II()
    aa = MII()
    head_prime = prime_factor(aa[0])

    pw_flag = True
    nc_flag = True
    for a in aa[1:]:
        nc_tmp = False
        for p in head_prime:
            if a%p == 0:
                nc_tmp = True
                pw_flag = False
        nc_flag &= nc_tmp

    if nc_flag and reduce(gcd, aa) == 1:
        print('setwise coprime')
    elif nc_flag:
        print('not coprime')
    else:
        print('pairwise coprime')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

flag = False
for i in range(N-1):
  for j in range(i+1, N):
    if math.gcd(A[i], A[j]) > 1:
      flag = True
      break
  if flag:
    break
if not flag:
  print('pairwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import gcd
import sys
n = int(input())
a_ls = list(map(int, input().split()))
now = a_ls[0]
for i in range(1,n):
    now = gcd(now,a_ls[i])
if now != 1:
    print('not coprime')
    sys.exit()
else:
    a_ls.sort()
    Max = a_ls[-1]
    c = Counter(a_ls)

    res = 'pairwise coprime'
    
    lim = int((10**6)**0.5)+2
    isdone = [0] * (Max+1)
    isdone[0],isdone[1] = 1,1
    # baseは共通の素因数の候補
    for base in range(2,lim):
        if base > Max:
            break
        if isdone[base]:
            continue

        now = base
        time_inA = 0
        while now <= Max:
            isdone[now] = 1
            if c[now] > 0:
                time_inA += c[now]
            now += base

        if time_inA >= 2:
            res = 'setwise coprime'
            break
            
    print(res)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    S = [1]*(N+1)
    for i, x in enumerate(A[::-1]):
        S[i+1] = S[i]*A[i]    
    flag = False

    if flag:
        print("pairwise coprime")
    elif g == 1:
        print("setwise coprime")

    else:
        print("not coprime")


main()

Submission status: Wrong Answer

Solution code:
import math
import functools

N = int(input())
A = [int(_) for _ in input().split()]
p = set([])

y = functools.reduce(math.gcd, A)
pairwise = True

for a in A:
    if a == 1:
        continue
    if pairwise is False:
        break
    for k in range(2, int(math.sqrt(a)) + 2):
        if a % k == 0:
            if k in p:
                pairwise = False
                break
            p.add(k)
            while a % k == 0:
                a //= k
    if pairwise and a > 1:
        p.add(a)

if pairwise:
    print("pairwise coprime")
elif y == 1:
    print("setwize coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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

pc = "pairwise coprime"
sc = "setwise coprime"
nc = "not coprime"

maxi=max(A)
sumi=set()

for i in range(2,maxi+1):
    if i in sumi:
        pass
    else:
        tmp=maxi//i
        for j in range(1,tmp+1):
            sumi.add(j*i)

cnt=0
for num in A:
    if num in sumi:
        cnt +=1
if cnt<=1:
    ans=pc
else:
    tmp2=A[0]
    for q in range(1,N):
        tmp2 = gcd(tmp2,A[q])
    if tmp2==1:
        ans=sc
    else:
        ans=nc

print(ans)

Submission status: Wrong Answer

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


def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x


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==[]:  # n=1のとき、[1,1]を返す
    #     arr.append([n, 1])

    return arr


# factorization(24)
# [[2, 3], [3, 1]]
#  24 = 2^3 * 3^1

gcdall = A[0]
for i in range(1, N):
    gcdall = gcd(gcdall, A[i])

# print(gcdall)
if gcdall > 1:
    print("not coprime")
    exit()

MAX = 10 ** 6 + 1
num = [False] * MAX
A = sorted(A)[::-1]
primeset = set()
for a in A:
    # if a == 1:
    #     continue
    # if num[a]:
    #     print("setwise coprime")
    #     exit()
    fact = factorization(a)
    for p, nn in fact:
        if p in primeset:
            continue
        primeset.add(p)
        for j in range(p + p, MAX, p):
            if num[j]:
                print("setwise coprime")
            num[j] = True
# for a in A:
#     if num[a] > 1:
#         print("setwise coprime")
#         exit()

print("pairwise 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:
    print("A")
    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
    if flag1 == 0:
        print("pairwise coprime")
    elif flag2 == 1:
        print("not coprime")
    else:
        print("setwise coprime")
else:
    print("B")
    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:
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

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


    cnt = 0
    tmp = set()
    for i in range(2, mx+1, 2):
        array[i] = 0
        if i in sss:
            cnt += 1
            tmp.add(i)
    if cnt > 1:
        pair_wise = False
    if len(tmp) > 1:
        ans -= tmp

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

    if pair_wise:
        print('pairwise coprime')
    elif ans != set():
        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:
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+1, n):
                        if a[i] != a[j]:
                                if math.gcd(a[i], a[j]) != 1:
                                        print("setwise coprime")
                                        flag = 0
                                        break
                        else:
                                continue
                break
if flag == 1:
        print("pairwise 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)
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1

st = set()
for a in A:
    for p in small_primes:
        found = False
        while a%p==0:
            a //= p
            found = True
        if found:
            if p in st:
                print('setwise coprime')
                exit()
            st.add(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:
from functools import reduce
from math import gcd


def primes(n):
    is_prime = [i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and i % 7 != 0 for i in range(n + 1)]
    is_prime[1] = False
    is_prime[2] = is_prime[3] = is_prime[5] = is_prime[7] = True
    for p in range(3, int(n**0.5) + 1, 2):
        if not is_prime[p]:
            continue
        for i in range(p**2, n + 1, p):
            is_prime[i] = False
    return [i for i, p in enumerate(is_prime) if p]


def main():
    n = int(input())
    a = set(int(i) for i in input().split())
    if len(a) < n or reduce(gcd, a) > 1:
        print("not coprime")
        return
    is_prime = [False] * n
    p = primes(max(max(a), 10))
    for i, ai in enumerate(a):
        for pi in p:
            if ai != pi and ai % pi == 0:
                break
        else:
            is_prime[i] = True
    comp = [ai for ai, isp in zip(a, is_prime) if not isp]
    for ci in comp:
        div = set()
        for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
            if ci % i == 0:
                div.add(i)
                div.add(ci // i)
        if ci == 2:
            div = {2}
        for d in div:
            if d in a:
                print("setwise coprime")
                return
        a |= div
    print("pairwise coprime")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
import sys

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

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
if gcd_list(a) != 1:
  print('not coprime')
  sys.exit()

a.sort()

for i in range(int(max(a) ** 0.5)):
  for j in range(2, 1000):
    if a[i] * j in a:
      print('setwise coprime')
      sys.exit()
      
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
import itertools

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

t = A[0]
check = A[0]
for i in range(1, n):
    t = math.gcd(t, A[i])
    s = math.gcd(check, A[i])
    check = (check * A[i]) // t


if t == 1 and s == 1:
    print('pairwise coprime')
elif t == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
input=sys.stdin.readline
from random import randint
##import numpy as np
##sys.setrecursionlimit(10**7)
mo=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
##def gcd(a,b): 
##    if a == 0: 
##        return b 
##    return gcd(b % a, a)
def SieveOfEratosthenes(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
          
        # If prime[p] is not changed, then it is a prime 
        if (prime[p] == True): 
              
            # Update all multiples of p 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
      
    f=[]
    for p in range(2, n+1): 
        if prime[p]: 
            f+=[p]
    return f

def lcm(a,b): 
    return (a*b) // math.gcd(a,b) 
for _ in range(1):
    n=inin()
    l=ain()
    f1,f2=0,0
    d=dd(int)
    d[2]=0
    lp=SieveOfEratosthenes(int(math.sqrt(max(l)+1))+1)
##    print(lp)
    for i in l:
        if(i!=1):
            for j in lp:
                if(i%j==0):
                    if(d[j]==1):
                        f1=1
                    d[j]+=1
    if(max(list(d.values()))==n):
        f2=1
    if(f2):print("not coprime")
    else:
        if(f1):
            print("setwise coprime")
        else:
            print("pairwise coprime")
        
        
    
    
    

 
    
    
    
    
        
        
    
    
    
    


    




##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo

Submission status: Wrong Answer

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

def GCM(y, x):
  buf = y%x
  if buf==0:
    return x
  else:
    return GCM(x, buf)

A.sort()
maxA = A[-1]
for i in range(2,N+1):
  maxA %= A[-i]
  if maxA == 0:
    maxA = A[-i]
if GCM(A[0], maxA)>1:
  print("not coprime")
else:
  count = 0
  flag=False
  for i in range(N-1):
    for j in range(i+1,N):
      count += 1
      if count > 5000000:
        break
      if GCM(A[-(i+1)],A[-(j+1)]) != 1:
        flag=True
        break
  if flag:
    print("setwise coprime")
  else:
    print("pairwise coprime")