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:
import sys
input = sys.stdin.readline

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

# n = 10**6
# A = [i+1 for i in range(n)]

A.sort()
p_ng = 0
l = 10**6 + 5
B = [0] * l

for i in range(2, l):
    if B[i] == 0:
        j = 2
        ind = j * i
        while ind < l:
            B[ind] = 1
            j += 1
            ind = j * i

C = [0] * l
for i in range(n):
    if A[B[i]] == 0:
        if C[B[i]] == 1:
            p_ng = 1
            break
        C[i] = 1
    else:
        a = A[i]
        w = 2
        while a != 1:
            f = 1
            while a%w == 0:
                a//=w
                if f == 1 and C[w] == 1:
                    p_ng = 1
                    break
                f = 0
                C[w] = 1
            w += 1
            # print(a,w)
            if p_ng== 1:
                break
        if p_ng == 1:
            break


# ind = 0
# while ind < n and A[ind] == 1:
#     ind += 1

# if ind < n:
#     for j in range(ind, n):
#         # print(B[:10])
#         for i in range(1, (l-1) // A[j] + 1):
#             indj = i * A[j]
#             # print(indj)
#             if i == 1 and B[indj] == 1:
#                 p_ng = 1
#                 break
#             B[indj] = 1
#         if j > 0 and A[j-1] == A[j]:
#             p_ng = 1
#             break
#         if p_ng == 1:
#             break

if p_ng == 0:
    print("pairwise coprime")
    sys.exit()

from math import gcd
g = A[0]
for i in range(1, n):
    g = gcd(g, A[i])

if g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]

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

    pairwise_coprime = A[0]
    setwise_coprime = A[0]
    for n in range(1, N):
        t = gcd(pairwise_coprime, A[n])
        if t > 1:
            pairwise_coprime = 0
        else:
            pairwise_coprime *= A[n]
        setwise_coprime = gcd(setwise_coprime, A[n])
    
    if pairwise_coprime:
        print('pairwise coprime')
    elif setwise_coprime == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def factorize(x):
    p = 2
    f = {}
    while x>=p*p:
        if x%p==0: f[p]=0
        while x%p==0:
            f[p]+=1
            x//=p
        p+=1
    if x>1: f[x]=1
    return f

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

F = {0:0}

for a in A:
    for f in set(factorize(a)):
        if f not in F: F[f] = 0
        F[f] += 1

m = max(F.values())
if m<=1:
    print('pairwise coprime')
elif m<N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

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

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

n = int(input())
a = list(map(int, input().split()))
b = gcd_list(a)
c = lcm_list(a)
d = 1
for i in range(n):
  d *= a[i]
if d == c:
  print('pairwise coprime')
elif b == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
#Code by Sounak, IIESTS
#------------------------------warmup----------------------------

import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict


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")
  
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

#-------------------game starts now-----------------------------------------------------
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
a.sort()
g=a[0]
for i in a:
    g=math.gcd(g,i)
d=dict()
for i in a:
    if i%2==0:
        if 2 in d:
            d[2]+=1
        else:
            d[2]=1
    while i%2==0:
        i//=2
    for j in range (3, int(math.sqrt(i))+1 ):
        if i%j==0:
            if j in d:
                d[j]+=1
            else:
                d[j]=1
            while i%j==0:
                i//=j
    if i>2:
        if i in d:
            d[i]+=1
        else:
            d[i]=1
c=1
for i in d:
    c=max(c,d[i])
if c==1:
    print("pairwise coprime")
elif g==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
def factorize(x):
    p = 2
    f = {}
    while x*x>=p:
        if x%p==0: f[p]=0
        while x%p==0:
            f[p]+=1
            x//=p
        p+=1
    if x>1: f[x]=1
    return f

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

F = {0:0}

for a in A:
    for f in set(factorize(a)):
        if f not in F: F[f] = 0
        F[f] += 1

m = max(F.values())
if m<=1:
    print('pairwise coprime')
elif m<N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=tuple(map(int,input().split()))
MAX_A=max(A)

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]]

prime=primes(MAX_A)
ans='pairwise coprime'

is_coprime=True

for p in prime:
    cnt=0
    for i,x in enumerate(A):
        if x%p==0:
            cnt+=1
    if cnt>=2:
        ans='setwise coprime'
    if cnt==N:
        is_coprime=False

if is_coprime:
    print(ans)
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
def yakusu(x):
    tmp=int(pow(x, 1/2))+1
    out=set()
    for i in range(1, tmp):
        if x%i==0:
            out.add(i)
            out.add(x//i)
    if pow(x, 1/2)%1==0:
        out.add(pow(x, 1/2))
    out=list(out)
    out.sort()
    return out

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

pairwise=True
X=[1]*(A[-1]+1)  

for a in A:
  tmp=yakusu(a)
  for i in tmp[1:]:
    if X[i]==0:
      pairwise=False
    else:
      for j in range(i, A[-1]+1, i):
        X[i]=0
      
import math
tmp=A[0]+0
for a in A[1:]:
  tmp=math.gcd(tmp, a)
  
if tmp==1:
  setwise=True
else:
  setwise=False
  
if pairwise==True:
  print('pairwise coprime')
elif setwise==True:
  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 f(n):
    e = set()
    if n < 2:
        return e
    if n % 2 == 0:
        e.add(2)
        while n % 2 == 0:
            n //= 2
    i = 3
    while i <= n:
        if n % i == 0:
            e.add(i)
            while n % i == 0:
                n //= i
        i += 2
    return e


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


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


if is_pairwise_coprime(n, a):
    print('pairwise coprime')
elif is_setwise_coprime(n, a):
    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]

    return mul == LCM

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:
from math import sqrt, gcd
def factoring(k): #kを因数分解し、素因数とその個数を辞書に入れて返す。
    dic = dict()
    n = int(sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] = count
    if k != 1: #sqrt(k)までチェックしてもkが1になっていない --> kが素因数
        dic[k] = 1
    return dic

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


from collections import defaultdict


dic = defaultdict(int)

count = 0
for a in A:
    tmp = factoring(a)
    for i in tmp:
        dic[i] = max(tmp[i], dic[i])
        count += tmp[i]

tmp = 0
for i in dic:
    tmp += dic[i]

if count == tmp:
    print ('pairwise coprime')
    exit()

GCD = A[0]
for a in A:
    GCD = gcd(GCD, a)

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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from collections import defaultdict
n = int(input())
A = tuple(map(int, input().split()))
x = A[0]
M1 = defaultdict(int)
M2 = defaultdict(int)
for a in A:
    x = gcd(x, a)
    cnt = 0
    while a%2 == 0:
        cnt += 1
        a //= 2
    if cnt >= M1[2]:
        M2[2] = M1[2]
        M1[2] = cnt
    elif cnt >= M2[2]:
        M2[2] = cnt
    f = 3
    cnt = 0
    while f*f <= a:
        if a%f == 0:
            cnt += 1
            a //= f
        else:
            if cnt >= M1[f]:
                M2[f] = M1[f]
                M1[f] = cnt
            elif cnt >= M2[f]:
                M2[f] = cnt
            f += 2
            cnt = 0
    if a != 1:
        if 1 >= M1[a]:
            M2[a] = M1[a]
            M1[a] = 1
        elif 1 >= M2[a]:
            M2[a] = 1
if x != 1:
    print("not coprime")
    exit()
for d in M2.values():
    if d >= 1:
        print("setwise coprime")
        exit()
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
def f(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


B=[0]*(10**6+10)
n=int(input())
A=list(map(int,input().split()))
for i in range(n):
  if A[i]==1:
    continue
  D=f(A[i])
  for j in range(len(D)):
    B[D[j][0]]+=1
f=0
for i in range(10**6+5):
  if B[i]>1:
    f=1
if f==0:
  print("pairwise coprime")
  exit()
for i in range(10**6+5):
  if B[i]>=n:
    f=0
if f==1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def factorize(n):
    b = 2
    fct = set()
    while b ** 2 <= n:
        while n % b == 0:
            n //= b
            fct.add(b)
        b += 1
    if n > 1:
        fct.add(n)
    return fct


def main():

    N = in_n()
    A = sorted(in_nl())

    M = 10**6 + 1
    ok = [True] * M

    pf = True
    for i in range(N):
        prime = factorize(A[i])
        for p in prime:
            if not ok[p]:
                pf = False
                break
            else:
                ok[p] = False

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

    if pf:
        ans = "pairwise coprime"
    else:
        if g == 1:
            ans = "setwise coprime"
        else:
            ans = "not coprime"

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# E - Coprime
from math import gcd

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

def prime(x):
    s = set()
    p = 2
    while x>1:
        if x%p==0:
            s.add(p)
            while x%p==0:
                x //= p
        p += 1
    return s

G = A[0]
pairwise = True
s = prime(A[0])

for i in range(1,N):
    a = A[i]
    t = prime(a)
    if len(s&t)>0:
        pairwise = False
    s = s|t
    G = gcd(G,a)

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

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
S=list(map(int,input().split()))
A=S[0]
B=1
Z=1
for i in range(N):
  A=math.gcd(A,S[i])
  if math.gcd(B,S[i])!=1:
    Z=0
  B*=S[i]
print("pairwise coprime" if Z==1 else "setwise coprime"if A==1 else "not coprime")

Submission status: Time Limit Exceeded

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

PAIR_WISE = "pairwise coprime"
SET_WISE = "setwise coprime"
NOT = "not coprime"

is_pair = True
is_set = True

cum = 1
set_gcd = a[0]
for i in a:
    res = gcd(cum, i)
    if res != 1:
        is_pair = False
    cum *= i
    set_gcd = gcd(i, set_gcd)
is_set = set_gcd == 1
if is_pair:
    print(PAIR_WISE)
    exit()
if is_set:
    print(SET_WISE)
    exit()
print(NOT)

Submission status: Time Limit Exceeded

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

n = max(A)

is_prime = [True]*(n+1)
is_prime[0] = 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
primes = [i for i in range(n+1) if is_prime[i]]

for p in primes:
    flag = 0
    for i in range(N):
        if A[i] % p == 0:
            if flag:
                break
            flag = 1
    else:
        continue

    # not pairwise coprime
    gcd_set = reduce(gcd, A)
    if gcd_set == 1:
        print("setwise coprime")
    else:
        print('not coprime')
    exit()
print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7




pair_flg=0
set_flg=0
n=I()
A=LI()
t_set=set()
s_set=set(range(2,n+1))
for j in range(n):
    a=A[j]
    prime_set = set()
    for i in range(2, int(a ** 0.5) + 1):
        while a % i == 0:
            prime_set.add(i)
            a //= i
        if a == 1:
            break
    if a != 1:
        prime_set.add(a)
    if prime_set&t_set:
        pair_flg=1
    t_set|=prime_set
    s_set&=prime_set


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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def factorize(n):
    b = 2
    fct = set()
    while b ** 2 <= n:
        while n % b == 0:
            n //= b
            fct.add(b)
        b += 1
    if n > 1:
        fct.add(n)
    return fct


def main():

    N = in_n()
    A = sorted(in_nl())

    M = 10**6 + 1
    ok = [True] * M

    pf = True
    for i in range(N):
        prime = factorize(A[i])
        for p in prime:
            if not ok[p]:
                pf = False
                break
            else:
                for j in range(p, M, p):
                    ok[j] = False

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

    if pf:
        ans = "pairwise coprime"
    else:
        if g == 1:
            ans = "setwise coprime"
        else:
            ans = "not coprime"

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


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


def main():
    N = ii()
    A = list(mi())

    l = 1
    g = A[0]
    k = 1

    for i in range(N):
        l = lcm(l, A[i])
        g = math.gcd(g, A[i])
        k *= A[i]

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd, sqrt

def Divisor_Set(n):
    s = set()
    for i in range(1, int(sqrt(n))+2):
        if n%i == 0:
            s.add(i)
            s.add(n//i)
    return s

def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = [0]*(10**6+1)
    for v in a:
        st = Divisor_Set(v)
        st.remove(1)
        for el in st:
            cnt[el] += 1
    f = True
    for i in range(10**6 + 1):
        if cnt[i] > 1:
            f = False
            break
    if f:
        print("pairwise coprime")
    else:
        all_gcd = a[0]
        for i in range(1, n):
            all_gcd = gcd(all_gcd, a[i])
        if all_gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

n = 1000_000

is_prime = [True]*(n+1)
is_prime[0] = 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
primes = [i for i in range(n+1) if is_prime[i]]

for p in primes:
    flag = 0
    for i in range(N):
        if A[i] % p == 0:
            if flag:
                break
            flag = 1
    else:
        continue

    # not pairwise coprime
    gcd_set = reduce(gcd, A)
    if gcd_set == 1:
        print("setwise coprime")
    else:
        print('not coprime')
    exit()
print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce
from collections import Counter
from itertools import chain


# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n


def solve(A):
    d = reduce(gcd, A)
    if d != 1:
        return 'not coprime'

    A = [a for a in A if a != 1]

    if len(set(A)) < len(A):
        return 'setwise coprime'

    c = Counter(chain.from_iterable(set(prime_factors(a)) for a in A))
    if c and max(c.values()) > 1:
        return 'setwise coprime'
    else:
        return 'pairwise coprime'


if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))

    print(solve(A))

Submission status: Time Limit Exceeded

Solution code:
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]]


def main():
    n = int(input())
    al = list(map(int, input().split()))
    ps = primes(n)
    pset = set()

    no_flag = False
    for a in al:
        for p in ps:
            if a%p == 0:
                if p in pset:
                    no_flag = True
                    break
                else:
                    pset.add(p)
        if no_flag:
            break
    else:
        print('pairwise coprime')
        exit()

    pset = set()
    for p in ps:
        if al[0]%p == 0:
            pset.add(p)

    for a in al[1:]:
        apset = set()
        for p in ps:
            if a%p == 0:
                apset.add(p)
        pset = pset&apset
        if len(pset) == 0:
            print('setwise coprime')
            break
    else:
        print('not coprime')



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
p = [0 for _ in range(10**6)]
for x in a:
  d = int(x)
  for y in range(2,10**3):
    if d % y == 0:
      p[y] += 1
      while d % y == 0:
        d //= y
  if d != 1:
    p[d] += 1
  #print(p)
if max(p) == 1:
  print('pairwise coprime')
  exit()
now = int(a[0])
for x in a:
  big,sml = x,now
  while big % sml != 0:
    #print(big,sml)
    big,sml = sml,big%sml
  now = sml
  #print(now)
if now == 1:
  print('setwise coprime')
else:
  print('not coprime')
  #print(now)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce


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


def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    arr_prod = reduce((lambda x, y: x*y), arr)
    total_gcd = gcd(arr[0], arr[1])
    total_lcm = lcm(arr[0], arr[1])
    for i in range(2, n):
        total_gcd = gcd(total_gcd, arr[i])
        total_lcm = lcm(total_lcm, arr[i])
    if total_lcm == arr_prod:
        print("pairwise coprime")
    elif total_lcm != arr_prod and total_gcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")


def main():
    t = 1
    while t > 0:
        solve()
        t -= 1


main()

Submission status: Time Limit Exceeded

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

    
from math import gcd

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

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

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

Submission status: Time Limit Exceeded

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

from math import gcd

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

tmp2 = a[0]
flg2 = True
for i in range(1, n):
    if gcd(tmp2, a[i]) != 1:
        flg2 = False
        break
    tmp2 *= a[i]

if flg2:
    print('pairwise coprime')
elif tmp1 == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
# E - Coprime
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)

def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

N = int(input())
A = list(map(int,input().split()))
seki = 1
for a in A:
    seki *= a
if lcm_list(A)==seki:
    print('pairwise coprime')
elif gcd_list(A)==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

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


MAX_N = 1000_000

primes = [1]*(MAX_N+1)
primes[1] = 1
for i in range(2, int(MAX_N**0.5)+1):
    if primes[i] > 1:
        continue
    for j in range(i, MAX_N+1, i):
        primes[j] = i

gcd_set = reduce(gcd, A)


b = {}

def prime_fact(n):
    ret = {}
    while n > 1:
        p = primes[n]
        if p in ret:
            ret[p] += 1
        else:
            ret[p] = 1
        n //= p


    for p in ret.keys():
        if p in b:
            return False
        else:
            b[p] = 1
    return True

for a in A:
    if not prime_fact(a):
        if gcd_set == 1:
            print('setwise coprime')
        else:
            print('not coprime')
        exit()

print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

n = int(input())


def p(x):
    a = []
    i = 2
    while True:
        if x % i == 0:
            j = 0
            while x % i == 0:
                x //= i
                j += 1
            a.append((i, j))
        if i * i > x:
            break
        i += 1
    if x != 1:
        a.append((x, 1))
    return a


pp = set()
a = [int(i) for i in input().split()]

j = 0
for i in a:
    j = gcd(j, i)
ok1 = j == 1

ok2 = True
for i in a:
    for (j, _) in p(i):
        if j in pp:
            ok2 = False
        else:
            pp.add(j)
if ok2:
    print("pairwise coprime")
else:
    if ok1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Accepted

Solution code:
# import itertools
import math
from functools import reduce
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# import heapq
# from collections import deque

N = int(input())
# S = input()
# n, *a = map(int, open(0))
# N, M = map(int, input().split())
A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# 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

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

if gcd_list(A) > 1:
    print("not coprime")
    exit()


MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p, MAXN+1, p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1

st = set()
for a in A:
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
    for p in tmp:
        if p in st:
            print('setwise coprime')
            exit()
        st.add(p)
print('pairwise coprime')

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
m=max(l)

from math import gcd
g=gcd(l[0],l[1])
for i in range(2,n):
  g=gcd(g,l[i])
if g!=1:
  print('not coprime')
  exit()

prime=[True]*(m+1)
prime[0]=False
prime[1]=False
d=[0]*(m+1)
for i in range(2,int(m**0.5)+1):
  if prime[i]:
    for j in range(i*2,m+1,i):
      prime[j]=False
      d[j]=i
s=[i for i in range(m+1) if prime[i]]
for ss in s:
  d[ss]=ss

sl=set()
for i in range(n):
  div=set()
  ll=l[i]
  while ll>1:
    div.add(d[ll])
    ll//=d[ll]
  div=list(div)
  for dd in div:
    if dd not in sl:
      sl.add(dd)
    else:
      print('setwise coprime')
      exit()

print('pairwise coprime')