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:
def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    S = 1
    for x in A:
        S *= x
    start = time.time()

    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

    flag = True
    s = factorization(A[0])
    for x in A[1:]:
        tmp = 0
        now = time.time()
        if now - start > 2:
            break
        for y in s:
            if x % y == 0:
                flag = False
                break
        if flag:
            s |= factorization(x)
            continue
        else:
            break

    if flag:
        print("pairwise coprime")
    else:
        g = A[0]
        for i, x in enumerate(A[::-1]):
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce


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


n = int(input())
a = list(map(int, input().split()))
for i in range(n - 1):
    for j in range(i + 1, n):
        if math.gcd(a[i], a[j]) != 1:
            if gcd(a) == 1: print("setwise coprime")
            else: print("not coprime")
            exit()
else:
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math

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

pairwise_flag=True
total_set=set()
common_set=set()
i_max= max(a)
num_list = [i for i in range(2, i_max + 1)]
prime_list = set(num_list)
for i in num_list:
    if i in prime_list:
        tmp = i+i
        while tmp < i_max:
            tmp+=i
            prime_list.discard(tmp)

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

for i in range(n):
    tmp = a[i]
    tmp_list=[]
    for j in prime_list:
        if tmp%j ==0:
            while tmp%j==0:
                 tmp//=j
            tmp_list.append(j)
        if tmp < j:
            break
    for j in tmp_list:
        prime_list.discard(j)
    if tmp !=1:
        pairwise_flag=False
        break


if pairwise_flag:
    print("pairwise coprime")
elif total_gcd>1:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
# E

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

def gcd(a,b):
    if a>b:
        a,b=b,a
    while a%b:
        a,b=b,(a%b)
    return b

def factorization(N):
    res=[]
    for i in range(2,int(N**(1/2))+2):
        if not N%i:
            r=0
            while not N%i:
                N//=i
                r+=1
            res.append((i,r))
    if N>1:
        res.append((N,1))
    return res

res2=1
P=[]
for i in range(N):
    if i!=0:
        res1=gcd(A[i],res1)
    else:
        res1=A[0]
    fact=factorization(A[i])
    if res2!=0:
        for p in P:
            if A[i]%p==0:
                res2=0
                break
    for p in fact:
        P.append(p[0])
if res2==1:
    print('pairwise coprime')
elif res1==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

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

primes = []
def primeFinder(n):
    memo = [1]*(n+1)
    memo[0] = 0
    memo[1] = 0
    for i in range(2,n+1):
        if memo[i] == 1:
            primes.append(i)
            for j in range(i*2,n+1,i):
                memo[j] = 0

primeFinder(10**6)
primeNums = primes
"""
各Aiに関して素因数を算出。素因数を集計してカウントが2つある素因数がなければpairwise
"""
count = Counter([])
for i in range(N):
    tmp = []
    a = A[i]
    i = 0
    while a != 1:
        d = primeNums[i]
        if a % d == 0:
            tmp.append(d)
        while a % d == 0:
            a //= d
        i += 1
    count += Counter(tmp)

for v in count.values():
    if v >= 2:
        break
else:
    print("pairwise coprime")
    exit()

def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

#setwise coprimeを判断
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:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def soinsubunkai2(n):
    a = set()
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.add(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=n
    a.add(nokori)
    return a 

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def main():
    #l,r,d=map(int,input().split())
    n=int(input())
    a=list(map(int,input().split()))
    sosu=[]
    memo = defaultdict(int)
    for i in range(n):
        if a[i]!=1:
            temp=soinsubunkai2(a[i])
        else:
            temp={}
        for j in temp:
            memo[j]+=1

    memo.pop(1,None)
 #   print(sosu)
 #   print(memo)
 #   print(memo.values())
    if len(memo)>=1:
        mmm=max(memo.values())
    else:
        mmm=1
    if mmm<=1:
        print("pairwise coprime")
    elif mmm<n:
        print("setwise coprime")
    else:
        print("not coprime")








if __name__ == "__main__":

    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
As = map(int, input().split(" "))

is_set = False
out_min = 10**6+1

first = True
A0 = As[0]

def fctr1(n): 
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append([i,c])
            c=0
    if n!=1:
        f.append([n,1])
    return f


for i in range(1, n):
    if i == 1:
        g = gcd(A0, As[i])
    else:
        g = gcd(g, As[i])

    if g == 1:
        is_set = True
        break


hontai_flags = [False] * out_min
#flags = [False] * out_min

if is_set:
    is_pair = True
    
    #for A in As:
    #    hontai_flags[A] = True

    As = list(set(As))
    n = len(As)

    #for i in range(1, out_min):
    #    if hontai_flags[i]:
    #        A = i

    #        for A in As:
    #            r = 2  
    #            while True:
    #                A0 = A*r
    #                if out_min <= A0:
    #                    break

    #                cur_flag = hontai_flags[A0]
    #                if cur_flag:
    #                    is_pair = False
    #                    break
    #                #flags[A0] = True

    #                r += 1

    #        if not is_pair:
    #            break

    for i in range(n):
        ds = fctr1(As[i])
        for d, _ in ds:
            if hontai_flags[d]:
                is_pair = False
                break
            hontai_flags[d] = True
else:
    is_pair = False

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

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
        if k: ret[i] = k
        i += 1 + i % 2
    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
N=int(input())
L=list(map(int,input().split()))

gc=L[0]
for i in L:
  gc=gcd(i,gc)
  if gc==1:
    break
if gc!=1:
  print("not coprime")
  exit()


ans=set()
c=0
for i in L:
  c+=len(primeFactor(i))
  ans|=set(primeFactor(i))
if c==len(ans):
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math

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

pairwise_flag=True
total_set=set()
common_set=set()
i_max= max(a)
num_list = [i for i in range(2, i_max + 1)]
prime_list = set(num_list)
for i in num_list:
    if i in prime_list:
        tmp = i+i
        while tmp < i_max:
            tmp+=i
            prime_list.discard(tmp)

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

for i in range(n):
    tmp = a[i]
    tmp_list=[]
    for j in prime_list:
        if tmp%j ==0:
            while tmp%j==0:
                 tmp//=j
            tmp_list.append(j)
    for j in tmp_list:
        prime_list.discard(j)
    if tmp !=1:
        pairwise_flag=False
        break


if pairwise_flag:
    print("pairwise coprime")
elif total_gcd>1:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd


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


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


n = int(input())
a = list(map(int, input().split()))
g = a[0]
l = a[0]

new_a = list(map(factorize, a))
#print(new_a)
wa = new_a[0]
cnt = 0
flag = 1
for i in range(1, n):
    if gcd(l, a[i]) > 1:
        flag = 0
    g = gcd(g, a[i])
    l = lcm(l, a[i])
if g > 1:
    print("not coprime")
elif flag == 0:
    print("setwise coprime")
else:
    print("pairwise coprime")

# for i in range(1, n):
#     b = gcd(b, a[i])
#     if b == 1:
#         break
# else:
#     print("not coprime")
#     exit()
#
# new_a = list(map(factorize, a))
# wa = new_a[0]
# cnt = 0
# flag = 0
# for i in range(1, n):
#     if len(wa & new_a[i]) > 0 and flag == 0:
#         flag = 1
#         break
#     wa = wa | new_a[i]
#
# if flag:
#     print("setwise coprime")
# else:
#     print("pairwise coprime")

Submission status: Time Limit Exceeded

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

    S = 1
    for x in A:
        S *= x
    start = time.time()

    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

    flag = True
    s = factorization(A[0])
    for x in A[1:]:
        tmp = 0
        now = time.time()
        if now - start > 2000:
            break
        for y in s:
            if x % y == 0:
                flag = False
                break
        if flag:
            s |= factorization(x)
            continue
        else:
            break

    if flag:
        print("pairwise coprime")
    else:
        g = A[0]
        for i, x in enumerate(A[::-1]):
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import math

def f(n):
    yakusu = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            yakusu.append(i)
            if i != n // i:
                yakusu.append(n // i)
    for i in yakusu:
        if i != 1:
            d[i] += 1

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

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

if tmp != 1:
    print('not coprime')
    exit()

f(A[0])

for i, v in d.items():
    if v != 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')

Submission status: Time Limit Exceeded

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

def divisors(n):
	div = [1, n]
	
	for i in range(2, int(n**0.5)+1):
		if n % i == 0:
			div.append(i)
			if i != n//i:
				div.append(n//i)
	
	return div

flag = False
inter = set(divisors(A[0]))
union = set(divisors(A[0]))
s = len(set(divisors(A[0])))
for i in range(1,N):
    div = set(divisors(A[i]))
    s += len(div)
    inter &=  div
    union |= div
if len(union) == s - N + 1:
    print('pairwise coprime')
elif inter == {1}:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
# Date [ 2020-08-29 21:59:01 ]
# Problem [ e.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

class PrimeFactorization():
    def __init__(self, n):
        self.n = n
        self.prime = [2]
        self.data = [i for i in range(3, self.n+1, 2)]

    def eratosthenes(self):
        p = self.data[0]
        while p*p <= self.n:
            p = self.data[0]
            self.prime.append(p)
            self.data = [e for e in self.data if e % p != 0]
        
        return self.prime + self.data

def Main():
    n = read_int()
    a = read_int_list()
    a.sort()
    if a[-1] < 3:
        prime = [2]
    else:
        p = PrimeFactorization(a[-1])
        prime = p.eratosthenes()
    
    cnt = 0
    for i in range(n):
        if a[i] % 2 == 1:
            cnt += 1
    
    length = len(set(a))
    aa = set(a) & set(prime)
    not_prime = list(filter(lambda x: x not in a, prime))

    if len(not_prime) <= 1:
        print('pairwise coprime')
    elif 1 < len(not_prime) < n:
        print('setwise coprime')
    else:
        if len(aa) > 0 or cnt > 0:
            print('setwise coprime')
        else:
            print('not coprime')

if __name__ == '__main__':
    Main()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd, sqrt, ceil
_, *aa = map(int, open(0).read().split())

from collections import defaultdict
def factorize(n):
    factors = set()
    if n % 2 == 0:
        factors.add(2)
    while n % 2 == 0:
        n //= 2
    for i in range(3, ceil(sqrt(n + 1)) + 1):
        if n % i == 0:
            factors.add(i)
        while n % i == 0:
            n //= i
    if n > 2:
        factors.add(n)
    return factors

def main(aa):
    pair_co = True
    min_factors = None
    max_factors = set()
    for a in aa:
        factors = factorize(a)
        new_max_factors = max_factors | factors
        if len(new_max_factors) < len(max_factors) + len(factors):
            pair_co = False
        max_factors = new_max_factors
        if min_factors is not None:
            min_factors &= factors
        else:
            min_factors = factors
#     if min_factors:
#         return 'not coprime'
#     elif pair_co
    if pair_co:
        return 'pairwise coprime'
    elif min_factors:
        return 'not coprime'
    else:
        return 'setwise coprime'
        

print(main(aa))

Submission status: Time Limit Exceeded

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

k = Alst[0]
for i in range(1, l):
    k = math.gcd(k, Alst[i])
    if k == 1:
        break

if k == 1: 
    c = False
    for i in range(l):
        for j in range(i+1, l):
            k = math.gcd(Alst[i], Alst[j])
            if k != 1:
                c = True
                break
        if c:
            break

    if c:
        print('setwise coprime')

    else:
        print('pairwise coprime')

else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)


n=int(input())
a=list(map(int,input().split()))
b=gcd(a[0],a[1])
res1=True
c=[1]*n
for i in range(1,n):
    c[i]=lcm(c[i-1],a[n-i])

for i in range(n-1):
    d=a[i];e=a[i+1];f=c[n-i-1]
    if gcd(d,f)==1:
        continue
    else:
        res1=False
        b=gcd(b,e)

if res1:
    print("pairwise coprime")
elif b==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

pc = True
gg = False
cnt = Counter()

fs = set()
fm = {}

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp in fs:
            arr += fm[temp]
            break
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    fm[n] = arr
    fs.add(n)
    return arr

for a in factorization(A[0]):
    if a > 1:
        cnt[a] = 1

for i in range(1, N):
    for a in factorization(A[i]):
        if cnt[a] >= 1:
            pc = False
        if a > 1:
            cnt[a] += 1

if pc:
    print("pairwise coprime")
elif cnt.most_common(1)[0][1] < N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

N = int(input())
A = list(map(int,input().split()))
A.sort()
X = cf(A[0],A[1])
if len(X) != 0:
    for i in X:
        a = 0
        b = 0
        for j in range(N):
            if A[j] % i == 0:
                a += 1
            else:
                b += 1
        if a == N:
            print("not coprime")
            sys.exit()
        if b != 0:
            print("setwise coprime")
            sys.exit()
    print("setwise coprime")
else:
    for i in range(N-1):
        X = cf(A[i], A[i+1])
        if len(X) != 0:
            print("setwise coprime")
            sys.exit()
        else:
            for j in X:
                for k in range(N):
                    if A[k] % j == 0:
                        print("setwise coprime")
                        sys.exit()
    print("pairwise coprime")

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]

    S = 1
    for x in A:
        S *= x

    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

    flag = True
    s = factorization(A[0])
    for x in A[1:]:
        tmp = 0
        for y in s:
            if x % y == 0:
                flag = False
                break
        if flag:
            s |= factorization(x)
            continue
        else:
            break

    if flag:
        print("pairwise coprime")
    else:
        g = A[0]
        for i, x in enumerate(A[::-1]):
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()

Submission status: Time Limit Exceeded

Solution code:
#ceilevenoddformula
import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations
#map(int,input().split())
#int(x) for x in input().split()
def gcd(a, b) : 
    if (a == 0) : 
        return b 
      
    if (b == 0) : 
        return a   
    k = 0
      
    while(((a | b) & 1) == 0) : 
        a = a >> 1
        b = b >> 1
        k = k + 1
          
 
    while ((a & 1) == 0) : 
        a = a >> 1
  
    # From here on, 'a' is always odd.  
    while(b != 0) : 
          
        # If b is even, remove all  
        # factor of 2 in b  
        while ((b & 1) == 0) : 
            b = b >> 1
  
        # Now a and b are both odd. Swap if 
        # necessary so a <= b, then set  
        # b = b - a (which is even). 
        if (a > b) : 
          
            # Swap u and v. 
            temp = a 
            a = b 
            b = temp 
  
        b = (b - a) 
      
    # restore common factors of 2  
    return (a << k) 


def primeFactors(n,l): 
    q=set()    
    while n % 2 == 0: 
    	if 2 in l:
    		return False,set()
    	q.add(2)
    	n = n / 2      

    for i in range(3,int(math.sqrt(n))+1,2): 
        while n % i== 0:
        	if i in l:
        		return False,set()
        	q.add(i)
        	n = n / i 
              
    if n > 2: 
    	if n in l:
    		return False,set()
    	q.add(n)

    l=l.union(q)
    return True,l

n=int(input())
l=[int(x) for x in input().split()]
l.sort()
d=set()
ans=1
for i in range(n):
	f,d=primeFactors(l[i],d)
	if not f:
		ans=0
		break



if ans:
	print('pairwise coprime')
else:
	a=l[0]
	b=l[1]
	gc=gcd(a,b)
	for i in range(2,n):
		gc=gcd(gc,l[i])
		if gc==1:
			break
	if gc==1:
		print('setwise coprime')
	else:
		print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    d = set()
    if num&1 == 0:
        d.add(2)
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i==0:
            d.add(i)
        while num%i==0:
            num //= i
    if num>2:
        d.add(num)
    return list(d)

n = inp()
x = ip()
#x.sort(reverse=True)
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        for j in pfact(i):
            if dt[j]:
                dt[j] = 0
            else:
                ans = 'setwise coprime'
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
from operator import add


def _i(): return int(sys.stdin.readline().strip())


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


def gcd(a, b):
    if a < b:
        a, b = b, a
    r = a % b
    if r == 0:
        return b
    else:
        return gcd(b, r)


def main():
    n = _i()
    a = list(sorted(_ia()))
    r = a[0]
    for ai in a[1:]:
        r = gcd(r, ai)
        if r == 1:
            break
    else:
        return "not coprime"

    N = 10 ** 6 + 1
    f = [False] * N
    p = []
    k = {ai: [] for ai in a}
    for i in range(2, N):
        if f[i]:
            continue
        p.append(i)
        if k.get(i) is not None:
            k[i].append(i)
        for j in range(2*i, N, i):
            f[j] = True
            if k.get(j) is not None:
                k[j].append(i)

    ls = reduce(add, k.values(), [])
    if len(ls) != len(set(ls)):
        return "setwise coprime"
    else:
        return "pairwise coprime"


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

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

pc_flag = True
for i in range(n):
  for j in range(n):
    if (j >= i):
      continue
    ans = gcd(a[i], a[j])
    if (ans != 1):
      pc_flag = False
      

if (pc_flag):
  print("pairwise coprime")
  exit()

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main():  
    def factorization(num):
        result = []
        temp = num
        if temp % 2 == 0:
                while temp % 2 == 0:
                    temp /= 2
                d[2] += 1
                result.append(2)
        for i in range(3, int(num ** 0.5) + 1, 2):
            if temp % i == 0:
                while temp % i == 0:
                    temp /= i
                d[i] += 1
                result.append(i)
        if temp != 1:
            d[int(temp)] += 1
            result.append(int(temp))
        if result == []:
            d[num] += 1
    n = int(input())
    A = map(int, input().split())
    d = defaultdict(int)
    for a in A:
        factorization(a)
    d[1] = 0
    m = max(d.values())
    if m == n:
        print('not coprime')
    elif m >= 2:
        print('setwise coprime')
    else:
        print('pairwise coprime')
    



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def main():
  n=int(input())
  a=list(map(int,input().split()))
  pairwise_coprime=0 
  for i in range(n-1):
    a_i=a[i]
    for j in range(i+1,n):
      #print(np.gcd(6,10))
      if (np.gcd(a_i,a[j])==1):
        pairwise_coprime+=1
      else:
        if pairwise_coprime>1:
          break
  if pairwise_coprime==(n*(n-1))//2:
    print("pairwise coprime")
  elif np.gcd.reduce(a)==1:
    print("setwise coprime")
  else:
    print("not coprime")
main()

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
arr=list(map(int, input().rstrip().split()))
start=0
pair=0
set=0
for i in range(start,n-1):
  for j in range(start+1,n):
    if (math.gcd(arr[i],arr[j])) != 1:
        pair=1
        break
  start+=1
if pair==0:
    print("pairwise coprime")
else:
    gcd=math.gcd(arr[0],arr[1])
    for i in range(2,n):
        gcd=math.gcd(gcd,arr[i])
    if gcd==1:
        print("setwise coprime")
    else:
        print("not coprime")