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: Runtime Error

Solution code:
from math import sqrt
from collections import Counter

def factorize(n):
    rt = int(sqrt(n)+1)
    facts = []
    for i in range(2, rt+1):
        if n % i == 0:
            facts.append(i)
            while n % i == 0:
                n //= i
    if n != 1:
        facts.append(n)
    return facts

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

P = Counter()

for a in A:
    p = Counter(factorize(a))
    P += p
p_max = max(P.values())
if  p_max == 1:
    print('pairwise coprime')
elif  p_max <  n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[0]*(10**6+1)
for m in a:
  l[m]=1
x=0
j=2
#print(l)
for i in range(n):
  c=0
  k=1
  while j*k<=10**6+1 :
    if l[j*k]==1:
      c+=1
      l[j*k]=0
    k+=1
  if c==n:
    print("not coprime")
    exit()
  elif c>1:
    x=1
  j+=1 
if x==1:
  print("setwise coprime")
else:
  print("pairwise coprime")

Submission status: Runtime Error

Solution code:
from math import gcd

n = int(input())
A = list(map(int,input().split()))
d  =[0]*(2*10**6+1)
c = [0]*(2*10**6+1)
max_val = max(A)
for a in A:
    d[a] += 1
A.sort()
flag = True
for i in range(2,max_val+1):
    if c[i]==0:
        flag = True
        for j in range(i,max_val+1,i):
            c[j]=1
            if d[j] !=0 and flag:
                flag = False
                d[j] = 0
                break
for a in d:
    if d[i] != 0:
        flag = True
        break
                    

if not flag :
    print('pairwise coprime')
    exit()
d  =[0]*(2*10**6+1)
c = [0]*(2*10**6+1)
max_val = max(A)
cnt = True
for a in A:
    d[a] += 1
A.sort()
set_ = set()
for i in range(2,max_val+1):
    if c[i]==0:
        for j in range(i,max_val+1,i):
            c[j]=1
            if d[j] != 0:
                if i not in set_:
                    set_.add(i)
                d[j] = 0
if len(set_)==1:
    print('not coprime')
else:
    print('setwise coprime')