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: Time Limit Exceeded

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

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

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

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

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None


    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


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


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

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

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


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

    return wrapped_func


#### END ITERATE RECURSION ####

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

mod = 1000000007


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

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

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

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

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

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


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

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

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

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

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



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

def power(x, y, p):
    res = 1  # Initialize result
    x = x % p  # Update x if it is more , than or equal to p
    if (x == 0):
        return 0
    while (y > 0):
        if ((y & 1) == 1):  # If y is odd, multiply, x with result
            res = (res * x) % p

        y = y >> 1  # y = y/2
        x = (x * x) % p
    return res

import random

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

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


    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    for repeat in range(precision):
        a = random.randrange(2, n - 2)
        x = power(a, d, n)

        if x == 1 or x == n - 1: continue

        for r in range(s - 1):
            x = power(x, 2, n)
            if x == 1: return False
            if x == n - 1: break
        else: return False

    return True

# https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/
def pollard_brent(n):
    if n % 2 == 0: return 2
    if n % 3 == 0: return 3

    y, c, m = random.randint(1, n-1), random.randint(1, n-1), random.randint(1, n-1)
    g, r, q = 1, 1, 1
    while g == 1:
        x = y
        for i in range(r):
            y = (power(y, 2, n) + c) % n

        k = 0
        while k < r and g==1:
            ys = y
            for i in range(min(m, r-k)):
                y = (power(y, 2, n) + c) % n
                q = q * abs(x-y) % n
            g = gcd(q, n)
            k += m
        r *= 2
    if g == n:
        while True:
            ys = (power(ys, 2, n) + c) % n
            g = gcd(abs(x - ys), n)
            if g > 1:
                break

    return g

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

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

    if n < 2: return factors

    while n > 1:
        if isprime(n):
            factors.append(n)
            break
        factor = pollard_brent(n) # trial division did not fully factor, switch to pollard-brent
        factors.extend(primefactors(factor)) # recurse to factor the not necessarily prime factor returned by pollard-brent
        n //= factor

    if sort: factors.sort()

    return factors

def factorization(n):
    factors = {}
    for p1 in primefactors(n):
        try:
            factors[p1] += 1
        except KeyError:
            factors[p1] = 1
    return factors


from functools import reduce

n=int(inp())
ar=lis()
if n<=1000000:
    temp=set()
    temps=0
    t=1
    for i in ar:
        k=factorization(i)
        s=set(k.keys())
        l=len(s)
        temp=temp.union(s)
        if len(temp)!=l+temps:
            t=-1
            break
        temps+=l
    if t==1:
        print("pairwise coprime")
    else:
        k=reduce(gcd,ar)
        if k==1:
            print("setwise coprime")
        else:
            print("not coprime")
else:
    k = reduce(gcd, ar)
    if k == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
import sys

N = int(input())
A = list(map(int, input().split()))
# P = 10 ** 9 + 7

# pairwise = lcd(A)!=pi A
lcm = 1
pia = 1
for a in A:
    lcm =  lcm*(a//gcd(lcm, a))
    pia = pia * a
if lcm == pia:
    print('pairwise coprime')
    sys.exit()

gcd_ = A[0]
for a in A[1:]:
    gcd_ = gcd(gcd_, a)
    if gcd_ == 1:
        print('setwise coprime')
        sys.exit()

print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

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

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

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

if gcd_list(a)==1:
  c=[]
  for i in range(n-1):
    for j in range(i+1,n):
      if math.gcd(a[i],a[j])!=1:
        c.append(False)
        break
  if c==[]:
    print("pairwise coprime")
  else:
    print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

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 lcm(a,b): 
    return (a*b) // math.gcd(a,b) 
for _ in range(1):
    n=inin()
    l=ain()
    f1,f2=0,0
    gc=lc=l[0]
    for i in range(1,n):
        gc=math.gcd(gc,l[i])
        if(f1==0):
            if(math.gcd(l[i],lc)!=1):f1=1
        if(f1==0):lc=lcm(lc,l[i])
    if(gc!=1):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: Time Limit Exceeded

Solution code:
import math
mod = 10 ** 9 + 7

n = int(input())
a = [int(i) for i in input().split()]
tmp = a[0]
set_v = a[0]
pairwise = True
for i in range(1, n):
    gcd = math.gcd(tmp, a[i])
    set_v = math.gcd(set_v, a[i])
    if gcd  > 1:
        pairwise = False
    tmp = (a[i] * tmp) // gcd
if pairwise == True:
    ans = 'pairwise coprime'
elif set_v == 1:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

Submission status: Time Limit Exceeded

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]

    def factorization(n):
        ret = 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
                ret.add(i)

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

        if len(ret) == 0 and n != 1:
            ret.add(n)

        return ret

    s = factorization(g)
    ls = len(s)
    flag = True
    for x in A[1:]:
        g = gcd(g, x)
        tmp = factorization(x)
        l = len(tmp)
        s |= tmp
        if len(s) != ls + l:
            flag = False
        ls = len(s)

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

    else:
        print("not coprime")


main()

Submission status: Time Limit Exceeded

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

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
P = get_prime(10**6)
  
def soinsu(a):
  result = []
  i = 0
  p = P[i]
  n = a
  while p <= n:
    if n%p == 0:
      result.append(p)
      while n%p == 0:
        n //= p
    i + 0
    p = P[i]
  return result

dict_prime = dict()

for a in A:
  for p in soinsu(a):
    if p in dict_prime.keys():
      dict_prime[p] += 1
    else:
      dict_prime[p] = 1

if len(dict_prime)==0:
  answer = 'pairwise coprime'
else:
  v = max(dict_prime.values())
  if v == N:
    answer = 'not coprime'
  elif v == 1:
    answer = 'pairwise coprime'
  else:
    answer = 'setwise coprime'

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from itertools import zip_longest

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

npcf = False
while True:
    B = []
    for x, y in zip_longest(A[:len(A)//2], A[len(A)//2:], fillvalue=1):
        if gcd(x, y) != 1:
            npcf = True
            break
        B.append(x*y)
    if len(B) == 1:
        break
    A = B

if not npcf:
    print('pairwise coprime')
    exit()

buf = A[0]
for a in A[1:]:
    buf = gcd(buf, a)
if buf == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
primes = [0 for i in range(10**6 + 5)]
idx = 0
ps=[0 for i in range(10**6)]

for i in range(2,len(primes)):
    if primes[i] == 0:
        ps[idx] = i
        idx +=1
        j = i+i
        while j <len(primes):
            primes[j] = 1
            j+=i

# print(ps[:100])

n=int(input())
arr=[int(c) for c in input().split()]
pariwise = True
setWise = True
ct = 0

for i in range(idx):
    prime = ps[i]
    # print(prime)
    count = 0
    for j in arr:
        if j%prime == 0:
            count+=1
    
    if count == n:
        setWise = False
    if count > 1:
        pariwise = False
    if (not setWise) and (not pariwise):
        break

if pariwise :
    print("pairwise coprime")
elif not pariwise and setWise:
    print("setwise coprime") 
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
import sys
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=gcd(ans,a[i])
  return ans



  


for i in range(n-1):
  for j in range(i+1,n):
    num=gcd(a[i],a[j])
    if num!=1:
      if setwise_coprime(a)==1:
        print("setwise coprime")
        sys.exit()
      else:
        print("not coprime")
        sys.exit()
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
primes = [0 for i in range(10**6 + 5)]
idx = 0
ps=[0 for i in range(10**6)]

for i in range(2,len(primes)):
    if primes[i] == 0:
        ps[idx] = i
        idx +=1
        j = i+i
        while j <len(primes):
            primes[j] = 1
            j+=i

# print(ps[:100])

n=int(input())
arr=[int(c) for c in input().split()]
pariwise = True
setWise = True
ct = 0

for i in range(idx):
    prime = ps[i]
    # print(prime)
    count = 0
    for j in arr:
        if j%prime == 0:
            count+=1
    
    if count == n:
        setWise = False
    if count > 1:
        pariwise = False
    if (not setWise) and (not pariwise):
        break

if pariwise :
    print("pairwise coprime")
elif not pariwise and setWise:
    print("setwise coprime") 
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    r = a % b

    while r:
        a = b
        b = r
        r = a % b

    return b

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

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

def pairwise():
    LCM = p[0]
    mul = p[0]

    for i in range(1, n):
        LCM = lcm(LCM, p[i])
        mul *= p[i]

        if mul != LCM:
            return False

    return True

def setwise():
    GCD = p[0]
    for i in range(1, n):
        GCD = gcd(GCD, p[i])

    return GCD == 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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



def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    D = [False] * (10 ** 6 + 1)
    D[1] = True
    pairwise = True
    setwise = [0] * (10 ** 6 + 1)
    for a in A:
        for i in range(2, int(-(-a ** 0.5 // 1)) + 1):
            if a % i == 0:
                setwise[i] += 1
                if D[i]:
                    pairwise = False
                else:
                    D[i] = True
                while a % i == 0:
                    a //= i
        if a!= 1:
            setwise[a] += 1
            if D[a]:
                pairwise = False
            else:
                D[a] = True
    if pairwise:
        print('pairwise coprime')
    else:
        if max(setwise)<N:
            print('setwise coprime')
        else:
            print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def fact(n):
    arr = []
    ret = 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.append([i, cnt])
            ret.add(i)
    if temp!=1:
        arr.append([temp, 1])
        ret.add(temp)
    if arr==[]:
        arr.append([n, 1])
        ret.add(n)

    return ret

from collections import defaultdict
cntd=defaultdict(int)
for i in range(len(a)):
    lis = fact(a[i])
    for num in lis:
        if num==1:
            continue
        cntd[num]+=1

flg=False

for c in cntd.values():
    if c==n:
        print("not coprime")
        exit()
    if c>1:
        flg=True
if flg:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
from functools import reduce
from math import gcd
g=reduce(lambda x,y:gcd(x,y),A,0)
if g>1:
    print('not coprime')
    exit()
def prime(N):
    p=set(range(2,N+1))
    for i in range(int(N**.5)+1):
        if i in p:
            p-=set(range(i*2,N+1,i))
    return p
p=prime(1000)
r=1
s=set()
for a in A:
    p2=p.copy()
    for x in p:
        if a%x==0:
            p2.remove(x)
        while a%x==0:
            a//=x
        if a==1:
            break
    if a>1:
        if 1000<a and a not in s:
            s.add(a)
        else:
            r=0
            break
    p=p2
print(['setwise coprime','pairwise coprime'][r])

Submission status: Time Limit Exceeded

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

def prime(n):
    p = []
    flag = [True] * (n - 1)
    for i in range(n - 1):
        if flag[i] == True:
            p.append(i + 2)
            num = i
            while num <= n - 2:
                flag[num] = False
                num += i + 2
    return p

gcd = 0
for i in range(n):
    gcd = math.gcd(gcd, a[i])
if gcd != 1:
    print("not coprime")
else:
    p = prime(1000)
    flag = True
    for i in p:
        temp = 0
        for j in range(n):
            if a[j] % i == 0:
                temp += 1
            if temp == 2:
                flag = False
                break
            while a[j] % i == 0:
                a[j] //= i
        if flag == False:
            break
    if flag == False:
        print("setwise coprime")
    else:
        num = set()
        for i in a:
            if i == 1:
                continue
            if i in num:
                print("setwise coprime")
                break
            else:
                num.add(i)
        else:
            print("pairwise coprime")

Submission status: Time Limit Exceeded

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

from math import gcd

g = a[0]
l = 1
f = True
for i in range(n):
    x = gcd(a[i],l)
    if x!=1:
        f = False
    l = (l*a[i])//x
    g = gcd(g,a[i])

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

Submission status: Time Limit Exceeded

Solution code:
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

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

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]
used = [False] * len(primes)
big = [0] * (10 ** 6)

g = A[0]
for v in A:
    g = gcd(v,g)
if g == 1:  
    works = 1
    for v in A:
        for i in range(len(primes)):
            if v % primes[i] == 0:
                if used[i]:
                    works = 0
                    break
                used[i] = True
                while v % primes[i] == 0:
                    v //= primes[i]
                if v == 1:
                    break
                
        works -= big[v]
        big[v] = 1
        big[1] = 0
        
        if works != 1:
            break
    if works:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

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

def calc_primes(n):
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data

primes = calc_primes(int(math.sqrt(10**6)))

is_pairwise = True
prod = 1
all_gcd = A[0]
for a in A:
    g = math.gcd(prod, a)
    all_gcd = math.gcd(all_gcd, a)
    if g > 1:
        is_pairwise = False
    prod *= a

if is_pairwise:
    print('pairwise coprime')
elif all_gcd == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

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

def prime_fact2(num):
    ret = set()
    while True:
        if num == 1: break
        tmp = num
        div = 2
        while div * div <= num:
            if num % div == 0:
                ret.add(div)
                ret.add(num//div)
                num //= div
                break
            div += 1
        if num == tmp:
             ret.add(num)
             break
    return ret

def is_prim(n,m):
    ret = []
    N = [False, False] + [True] * (m-1)
    for j in range(m+1):
        if N[j]:
            if n <= j: ret.append(j)
            if j*j<=m:
                k=2
                while k*j <= m:
                    N[k*j]=False
                    k+=1
    return ret

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    Primes = is_prim(0, 1000)
    COUNT = [0] * 1000001
    B = [[] for _ in range(N)]
    for i in range(N):
        k = A[i]
        for prime in Primes:
            if k % prime == 0:
                B[i].append(prime)
                COUNT[prime] += 1
                while k > 1 and k % prime == 0:
                    k //= prime
        if k != 1:
            B[i].append(k)
            COUNT[k] += 1

    pairwise = True
    setwise = True
    for i in range(N):
        for prime in B[i]:
            if COUNT[prime] == N:
                setwise = False
            if COUNT[prime] != 1:
                pairwise = False


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

Submission status: Time Limit Exceeded

Solution code:
'''بِسْمِ اللَّهِ الرَّحْمَٰنِ الرَّحِيمِ'''
#codeforces
from math import gcd
from functools import reduce
gi = lambda : list(map(int,input().split()))
def lcm(x, y):
	return (x * y) * gcd(x, y);
n, = gi()
a = gi()
lcmm = reduce(lcm, a);
prod = 1
for e in a:
	prod *= e
	if e > lcmm:
		break;
if prod == lcmm:
	print("pairwise coprime")
	exit(0)
gcdd = reduce(gcd, a);
if gcdd == 1:
	print("setwise coprime")
	exit(0)
print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
N = int(input())
a = list(map(int, input().split()))
ans = a[0]
flag = True

for i in range(N):
  if i != 0:
    ans = gcd(ans,a[i])
  for j in range(i+1,N):
    if gcd(a[i],a[j]) != 1:
      flag = False
  
if flag:
  print("pairwise coprime")
  exit()     
elif flag == False and ans == 1:
  print("setwise coprime")
elif ans != 1:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math 
from functools import reduce

def read():
    N = int(input()) 
    As = list(map(int, input().split(' ')))
    return N, As


def func(N, As):
    if reduce(math.gcd, As) != 1:
        print('not coprime')
        return
    for i in range(N):
        ai = As[i]
        for j in range(i+1, N):
            aj = As[j]
            if math.gcd(ai, aj) != 1:
                print('setwise coprime')
                return
    print('pairwise coprime')
    return


if __name__ == '__main__':
    N, As = read()
    func(N, As)

Submission status: Time Limit Exceeded

Solution code:
import math
mod = 10 ** 9 + 7

n = int(input())
a = [int(i) for i in input().split()]
tmp = a[0]
set_v = a[0]
pairwise = True
for i in range(1, n):
    gcd = math.gcd(tmp, a[i])
    set_v = math.gcd(set_v, a[i])
    if gcd  > 1:
        pairwise = False
    elif gcd == 1:
        setwise = True
    tmp = (a[i] * tmp) // gcd
if pairwise == True:
    ans = 'pairwise coprime'
elif set_v == 1:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
Ai = list(map(int, input().split(" ")))
pairwiseI = False
for i in range(N - 1):
    for k in range(i + 1, N):
        if np.gcd(Ai[i], Ai[k]) != 1:
            pairwiseI = True
if (not pairwiseI) == True:
    print("pairwise coprime")
else:
    gcdall = Ai[0]
    for i in range(1, N):
        gcdall = np.gcd(gcdall, np.gcd(Ai[i-1], Ai[i]))
    if gcdall == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
flg = True
for i in range(N-1):
    if sum(np.gcd(A[i], A[i+1:])) != N-i-1:
        break
else:
    print('pairwise coprime')
    exit()
if np.gcd.reduce(A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

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

def eratosthenes(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]]


pairwise = True
setwise = True
for x in eratosthenes(10**6):
    cnt = 0
    for a in A:
        if a % x == 0:
            cnt += 1
    
    if cnt >= 2:
        pairwise = False
    
    if cnt == N:
        setwise = False
    
if pairwise:
    print('pairwise coprime')
elif setwise:
    print('setwise coprime')
else:
    print('not coprime')