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:
MAXN = 1000001
spf = [i for i in range(MAXN)] 
hash1 = [0 for i in range(MAXN)] 
def sieve(): 
    for i in range(4, MAXN, 2): 
        spf[i] = 2

    for i in range(3, MAXN): 

        if i * i < MAXN: 
            break
        if (spf[i] == i): 
            for j in range(i * i, MAXN, i): 
                if (spf[j] == j): 
                    spf[j] = i  
def getFactorization(x): 
    while (x != 1): 
        temp = spf[x] 
        if (x % temp == 0): 
            hash1[spf[x]] += 1
            x = x // spf[x] 
        while (x % temp == 0): 
            x = x // temp 
def check(x): 

    while (x != 1): 
        temp = spf[x] 
        if (x % temp == 0 and hash1[temp] > 1): 
            return False
        while (x % temp == 0): 
            x = x //temp 
	
    return True

def hasValidNum(arr, n): 
    sieve() 

    for i in range(n): 
        getFactorization(arr[i]) 
    f=0;
    for i in range(n): 
        if (check(arr[i])==False):
            #print(arr[i])
            f=1
    if(f==1):
        return False
    return True;

n=int(input())
arr=list(map(int,input().split()))
if (hasValidNum(arr, n)): 
    print("pairwise coprime")
else:
    f=0
    for i in range(n):
        if hash1[i]==n:
            print("not coprime")
            f=1
            break
    if f==0:
        print("setwise 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)
if len(s)!=n:
    print('not coprime')
    exit(0)
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:
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:
import math

def main():
    N = int(input())
    As = list(map(int, input().split()))
    pairwise_flag = True
    setwise_flag = True
    if N > 78498:
        pairwise_flag = False
    
    L = 1000 + 1
    isPrime = [True] * L
    isPrime[0] = isPrime[1] = False
    primes = []
    for n in range(2, L):
        if isPrime[n]:
            primes.append(n)
            isPrime[2*n::n] = [False] * ((L-n-1) // n)

    or_factor = 0
    or_factor_over1000 = set()
    all_gcd = None
    for i, a in enumerate(As):
        digit = 1
        factor = 0
        x = a
        if pairwise_flag:
            for p in primes:
                if x % p == 0:
                    factor += digit
                    x //= p

                while x % p == 0:
                    x //= p
                digit <<= 1

        if i > 0:
            all_gcd = math.gcd(all_gcd, a)
            if pairwise_flag:
                if or_factor & factor:
                    pairwise_flag = False
                or_factor |= factor
                if x > 1:
                    if x in or_factor_over1000:
                        pairwise_flag = False
                    or_factor_over1000.add(x)
        else:
            all_gcd = a
            or_factor |= factor
            if x > 1:
                or_factor_over1000.add(x)
    if pairwise_flag:
        print('pairwise coprime')
    elif all_gcd > 1:
        print('not coprime')
    else:
        print('setwise coprime')

main()

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:
        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 math import *
n=int(input())
l=list(map(int,input().split()))
l.sort()
g=l[0]
for i in range(1,n):
    g=gcd(g,l[i])
if(g!=1):
    print("not coprime")
else:
    f=0
    p=l[-1]
    for i in range(n-2,-1,-1):
        if(gcd(p,l[i])!=1):
            f=1
            break
    if(f==1):
        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 = 1
for i in range(1, N):
    ans1 = math.gcd(ans1, A[i])
    if (ans1 > 1):
        ans2 = 2

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

Submission status: Wrong Answer

Solution code:
import fractions
N = int(input())
flag = True
a = list(map(int, input().split()))
maxval = max(a)
m = [-1]*(1000010)
a.sort()
cnt=0

for i in range(len(a)):
  if(a[i]==1):
    continue
  if(a[i]%2==0):
    cnt+=1
  if(m[a[i]]==1 or cnt==2):
    flag = False
    break
  tmp=a[i]
  multi=2
  while(tmp<=maxval):
    m[tmp]=1
    tmp=a[i]*multi
    multi+=1
    
if(flag):
  print("pairwise coprime")
  
else:
  ans = a[0]
  for i in range(1, N):
    ans = fractions.gcd(ans, a[i])
  if ans==1:
    print("setwise coprime")
  else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict
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 [a[0] for a in arr]

N = int(input())
A = sorted([int(i) for i in input().split()])
dict_A = defaultdict(int)
dep_flag = False
for a in A:
  dict_A[a] += 1
  if a != 1 and dict_A[a] >= 2:
    dep_flag=True
if dep_flag == False:  
  all_flag = True
  devisors = set()
  for n in range(N-1):
      if n == 0:
          g = gcd(A[n],A[n+1])
      else:
          g = gcd(A[n+1],g)
      temp = factorization(A[n])
      for t in temp:
          if t in devisors:
              all_flag=False
          else:
              devisors.add(t)
  if all_flag and g == 1:
      print('pairwise coprime')
  elif g==1:
      print('setwise coprime')
  else:
      print('not coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
p=[1 for i in range(1001)]
p[0]=0
p[1]=0
for i in range(2,1001):
    if p[i]==1:
        for j in range(2,1001):
            if i*j<=1000:
                p[i*j]=0
#print(p[:25])
Prime=[]
for i in range(1001):
    if p[i]==1:
        Prime.append(i)
#print(Prime)
#print(len(Prime))
N=int(input())
L=list(map(int,input().split()))

def gcd(a,b):
    if b>a:
        a,b=b,a
    while a%b!=0:
        a,b=b,a%b
    return b
    
X=L[0]
for i in range(1,N):
    X=gcd(X,L[i])
    if X==1:
        break
if X>1:
    print("not coprime")
    exit()
        
D={}
if N>(10**5)*5:
    print("setwise coprime")
    exit()
for i in L:
    I=i
    for j in Prime:
        if I%j==0:
            if j not in D:
                D[j]=1
            else:
                print("setwise coprime")
                exit()
            while I%j==0:
                I//=j
    if I!=1:
        if I not in D:
            D[I]=1
        else:
            print("setwise coprime")
            exit()
#print(D)

print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
from math import gcd
from collections import Counter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

counter = Counter(A)
for val in counter.values():
    if val > 1:
        print('not coprime')
        sys.exit()


def max_gcd_pair(S):
    # Assumption 1: S is the list of numbers
    # Assumption 2: There are no duplicates in S
    s = set(S)
    m = max(S)
    res = 0
    i = m
    while i > 0:
        a = i
        cnt = 0
        while a <= m: # a maxed at max of the list
            if a in s:
                cnt += 1
            a += i

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

        i = i - 1
    return res


pair = max_gcd_pair(A)
if pair == 1:
    print('pairwise coprime')
    sys.exit()

setw = A[0]
for j in range(N):
    setw = gcd(setw, A[j])

if setw == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
n = I()
A = readInts()
left = [0] * (n+1)
right = [0] * (n+1)
for i in range(1,n):
    left[i] = gcd(left[i-1], A[i-1])
for i in range(n-2,-1,-1):
    right[i] = gcd(right[i+1], A[i+1])
res = 0
nya = set()
for i in range(n):
    l = left[i]
    r = right[i]
    nya.add(gcd(l,r))
lis = list(nya)
if len(lis) == 1:
    if lis[0] == 1:
        print('pairwise coprime')
    else:
        print('not coprime')
else:
    nya = A[0]
    for i in range(1,len(lis)):
        nya = gcd(nya,A[i])
    if nya == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

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

def primels(A):
    lsP = []
    for i in range(2, int(-(-A**0.5//1))+1):
        if A%i == 0:
            lsP.append(i)
    return set(lsP)

ans = ''
setwa = set()
ii = 0
for i in range(N):
    setA = primels(lsA[i])
    if (setA & setwa) != set():
        break    
    setwa = setwa | setA
    ii += 1
if ii == N:
    ans = 'pairwise coprime'

if ans == '':
    gcd = lsA[0]
    for i in range(1,N):
        gcd = math.gcd(gcd,lsA[i])
        if gcd == 1:
            ans = 'setwise coprime'
            break

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

Submission status: Wrong Answer

Solution code:
import math

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

t = A[0]
check = A[0]
for i in range(1, n):
    s = math.gcd(check, A[i])
    t = math.gcd(t, A[i])
    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:
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()) == N:
    answer = 'not coprime'
  else:
    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:
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("setwise 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:
# -*- coding: utf-8 -*-
from bisect import bisect_right

import math
from functools import reduce

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

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

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(10**6)

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

check = [0]*(10**6)
flag = 0
for a in A:
    for i in range(bisect_right(P, int(a**0.5)+10)):
        if a%P[i] == 0:
            if check[P[i]] == 1:
                flag = 1
            else:
                check[P[i]] = 1
    if flag:
        break

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

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int,input().split())))
    p = [i for i in range(2,int(a[-1]**0.5)+1)]
    for i in range(len(p)-1):
        if p[i]==0:
            continue
        for j in range(i+1,len(p)):
            if p[j]%p[i] == 0:
                p[j]=0
    prm = []
    for p_ in p:
        if p_ != 0:
            prm.append(p_)
    m_cnt = 0
    for p in prm:
        cnt = 0
        for a_ in a:
            if a_%p==0:
                cnt += 1
        if cnt > m_cnt:
            m_cnt = cnt
    if m_cnt == n:
        print('not coprime')
        return
    if m_cnt > 1:
        print('setwise coprime')
        return
    l = len(set(a))
    if l== 1:
        print('not coprime')
        return
    if l!=n:
        print('setwise coprime')
        return
    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

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

sorted(als)

ans = "not coprime"

a, b = als[1], als[0]
while a % b != 0:
    a, b = b, a % b

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

maxa = max(als)

existeven = False

failed = False

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

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 == 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:
from collections import deque
import sys, copy, itertools,heapq
input = sys.stdin.readline

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



nn = int(input())
A = list(map(int,input().split()))
suma = sum(A)
B = factorization(suma)
LISTB = [0]*(len(B))

for i in range(len(B)):
  for j in range(nn):
    if A[j] % B[i][0] == 0:
      LISTB[i] += 1

c = max(LISTB)


print(A)
print(suma)
print(B)
print(LISTB)
print(c)

if c == 1:
  print('pairwise coprime')
elif c== nn:
  print('not coprime')
else:
  print('setwise coprime')

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = list(map(int,input().rstrip().split(" ")))
    M = int(math.sqrt(max(A))) + 1
    sosuu = set()
    sosuu.add(2)
    for i in range(3,M,2):
        for j in sosuu:
            if i % j == 0:
                break
        else:
            sosuu.add(i)
    pair = True
    setw = True
    counter = 0
    lis = [0] * (10 ** 6 + 1)
    for q in range(len(A)):
        i = A[q]
        remset = set()
        for j in sosuu:
            if i % j == 0:
                while i % j == 0:
                    i = i // j
                lis[j] += 1
            
        if i != 0:
            lis[i] += 1
            if lis[i] == 2:
                pair = False
    for i in range(10 ** 6 + 1):
        if lis[i] == N:
            setw = False
        if lis[i] >= 2:
            pair = False
        if not setw and not pair:
            break

    if pair:
        print("pairwise coprime")
    elif setw:
        print("setwise coprime")
    else:
        print("not coprime")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    return gcd(b, a % b) if b > 0 else a


def judge_pairwise(array, n):
    array.sort()
    isOK = [True] * (n + 1)
    isOK[0] = False
    isOK[1] = True
    for num in array:
        if num == 1:
            continue

        if isOK[num] is False:
            return False

        for div in range(2, int(num ** 0.5) + 1):
            div = 2
            if num % div == 0:
                while num % div == 0:
                    num //= div
                if isOK[div] is False:
                    return False
                else:
                    isOK[div] = False

        if num != 1:
            if isOK[num] is False:
                return False
            else:
                isOK[num] = False

    return True


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

pairwiseFlag = judge_pairwise(a, 10 ** 6)

total = a[0]
for num in a:
    total = gcd(total, num)
if total == 1:
    setwiseFlag = True
else:
    setwiseFlag = False

if pairwiseFlag is True:
    print("pairwise coprime")
elif setwiseFlag is True:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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

yak=[0]*(10**7)

for i in a:
    if i%2==0:
        yak[2]+=1
for i in range(1,10**3+10):
    for j in a:
        if j%(2*i+1)==0:
            yak[2*i+1]+=1

if max(yak)<=1:print("pairwise coprime")
elif max(yak)<n:print("setwise coprime")
else:print("not coprime")

Submission status: Wrong Answer

Solution code:
import math

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

ans = a[0]
A = []

for x in a[1:]:
    ans = math.gcd(ans,x)
    A.append(ans)
#print(ans)
#print(A)

if A.count(1) == len(A):
    print('pairwise coprime')
elif A.count(1) != len(A) and ans == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)
n=int(input())
l=list(map(int,input().split())) 
c=0
h=list(filter(lambda x: x%2==0,l))
e=0
for i in h:
    if i==0:
        e=e+1
if e==n:
    print('not coprime')
else:
    for i in range(0,n):
        t=l[i%n]
        y=l[(i+1)%n]
        s=min(t,y)
        p=max(t,y)
        f=gcd(p,s)
        if f==1:
            c=c+1
    if c==3:
        print('pairwise  coprime')
    else:
        f=l[0]
        y=l[1]
        a=max(f,y)
        b=min(f,y)
        r=gcd(a,b)
        for w in range(2,len(l)):
            r=gcd(r,l[i])
        if r==1:
            print('setwise  coprime')
        else:
            print('not coprime')

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import deque
mod = 10**9 + 7

def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a
    
n = int(input())
li = deque(map(int, input().split()))

if gcdlist(li) != 1:
    print("not coprime")
    exit()

SUM = 1
for i in range(n):
    SUM *= li[i]
    SUM %= mod
    
for i in range(n):
    s = li.popleft()
    SUM //= s
    GCD = gcd(s, SUM)
    if GCD != 1:
        print("setwise coprime")
        exit()
    SUM *= s
else:
    print("pairwise coprime")

Submission status: Wrong Answer

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

def get_prime(n):
  res = [1]*(n+1)
  x = 2
  for i in range(2,x):
    if res[i]:
      for j in range(i*2,n+1,i):
        res[j] = 0
  return [i for i in range(2,n+1) if res[i]]

prime_list = {x:0 for x in get_prime(10**6+1)}
setwise = a[0]

def check(n):
  for p in prime_list.keys():
    if n < p:
      break
    if n % p==0:
      if prime_list[p]:
        return 0
      else:
        prime_list[p] = 1
  return 1

allwise = check(a[0])
for ai in a[1:]:
  allwise = check(ai)
  setwise = math.gcd(setwise,ai)
  #print(ai,allwise,setwise)
if allwise:
  print('pairwise coprime')
elif setwise == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
p=[1 for i in range(1001)]
p[0]=0
p[1]=0
for i in range(2,1001):
    if p[i]==1:
        for j in range(2,1001):
            if i*j<=1000:
                p[i*j]=0
#print(p[:25])
Prime=[]
for i in range(1001):
    if p[i]==1:
        Prime.append(i)
#print(Prime)
#print(len(Prime))
N=int(input())
L=list(map(int,input().split()))

def gcd(a,b):
    if b>a:
        a,b=b,a
    while a%b!=0:
        a,b=b,a%b
    return b
    
X=L[0]
for i in range(1,N):
    X=gcd(X,L[i])
    if X==1:
        break
if X>1:
    print("not coprime")
    exit()
        
D={}
if N>10**5:
    print("pairwise coprime")
    exit()
for i in L:
    I=i
    for j in Prime:
        if I%j==0:
            if j not in D:
                D[j]=1
            else:
                print("setwise coprime")
                exit()
            while I%j==0:
                I//=j
    if I!=1:
        if I not in D:
            D[I]=1
        else:
            print("setwise coprime")
            exit()
#print(D)

print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import numpy as np

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

gx=list()

jud=0

for i in range(n-1):
    g = np.gcd(a[i], a[i+1])
    if g!=1:
        jud=1
        break

if jud==0:
    print("pairwise coprime")
elif np.gcd.reduce(a)==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

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

ans = ["pairwise coprime", "setwise coprime", "not coprime"]
p_list = [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]
#print(p_list)

def factorization(n):
    arr = []
    temp = n
    for i in p_list:
      if (n >= i):
        if temp%i==0:
            #cnt=0
            while temp%i==0:
             #   cnt+=1
                temp //= i
            arr.append(i)
      else:
        break
        
    if temp != 1:
        arr.append(temp)

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

    return arr
  
B = factorization(A[0])
B_cnt = [0] * len(B)
for i in A:
  for j in range(len(B)):
    if i % B[j] == 0:
      B_cnt[j] += 1
#print(B, B_cnt)      
  
if max(B_cnt) == N:
  print(ans[2])
  quit()
  
ans_ = 0
used = [0] * len(p_list)
for i in range(N):
  x = factorization(A[i]) 
  #print(x)
  for j in x:
    if j in p_list:
      used[p_list.index(j)] += 1
      if used[p_list.index(j)] != 1:
        ans_ = 1
  #print(x, used[:10])
  
if max(used) == N:
  ans_ = 2
  
print(ans[ans_])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    N = int(input())
    A = list(map(int, input().split()))
    A = sorted(A)
    m = 100

    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, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487]

    table = [0] * len(prime)
    for i in range(len(prime)):
        for j in range(N):
            if A[j] % prime[i] == 0:
                table[i] += 1
        if table[i] == N:
            print('not coprime')
            return
        if table[i] > 1:
            print('setwise coprime')
            return
    print('pairwise coprime')


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    targets = LI()
    MAX_INT = max(targets) + 1
    targets = set(targets)
    is_pw = True

    if len(targets) != N:
        is_pw = False

    if len(targets) == 1:
        if 1 in targets:
            print("setwise coprime")
            return
        print("not coprime")
        return

    for i in range(2, MAX_INT):
        origin = i
        kosuu = 0
        while origin <= MAX_INT:
            if origin in targets:
                kosuu += 1
            origin += i

        if kosuu <= 1:
            continue
        elif kosuu < len(targets):
            is_pw = False
        else:
            print("not coprime")
            return

    if is_pw:
        print("pairwise coprime")
        return
    print("setwise coprime")


main()