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 itertools
from functools import reduce
import math

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

N = int(input())
A = [int(x) for x in input().split(" ")]


pair = list(itertools.combinations(A, 2))

for i in range(len(pair)):
    if(math.gcd(pair[i][0], pair[i][1]) != 1):
        if(gcd_list(A) == 1):
            print("setwise coprime")
            break
        else:
            print("not coprime")
            break
    else:
        print("pairwise coprime")
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter 
import sys

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

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A.sort()
if A[0] == 1:
    s = 0
else:
    d = prime_factorize(A[0])
    dlist = list(Counter(d).keys())
    for i in dlist:
        for j in range(1,N):
            if A[j] % i != 0:
                break
            if j == N-1:
                print("not coprime")
                sys.exit()


t = 0
cnt = [0] * (10 ** 6)
for i in A:
    a = prime_factorize(i)
    alist = list(Counter(a).keys())
    for j in alist:
        cnt[j] += 1
        if cnt[j] >= 2:
            t = 1
            break
    if t == 1:
        break

if t == 0:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
##https://www.codechef.com/viewsolution/20131475

from math import gcd

def main():
    n = int(input())
    A = list(map(int , input().split()))
    N = max(A)+1

    sv = [i for i in range(N)]
    for i in range(2 , N) :
        if i * i >= N : break
        if sv[i] < i : continue
        for j in range(i * i , N , i) :
            sv[j] = min(sv[j] , i)

    def getPrimes(a) :
        pr = []
        if a == 1 : return pr
        pr.append(sv[a])
        while a > 1 :
            if sv[a] != pr[-1] :
                pr.append(sv[a])
            a //= sv[a]
        return pr

    np = [0] * N
    F = [0] * N


    for a in A :
        pr = getPrimes(a)
        for i in range(1 << len(pr)) :
            prod , nb = 1 , 0
            for j in range(len(pr)) :
                if i & (1<<j) :
                    prod *= pr[j]
                    nb += 1
            F[prod] += 1
            np[prod] = nb

    ans = 0
    for i in range(N) :
        cnt = F[i]
        cnt = (cnt * (cnt-1))//2
        if np[i] & 1 : ans -= cnt
        else : ans += cnt

    if ans == (n*(n-1))//2:
        print("pairwise coprime")
        exit()

    A.sort()
    d = A[0]

    for i in A:
        d = gcd(i,d)
        if d == 1:
            break

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

main()

Submission status: Time Limit Exceeded

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

isSetWise = False
gcd = A[0]
for i in range(1, N):
    gcd = math.gcd(gcd, A[i])
if gcd == 1:
    isSetWise = True

isPairWise = True
tmp = A[0]
for i in range(1, N):
    gcd = math.gcd(tmp, A[i])
    tmp *= A[i]
    if gcd != 1:
        isPairWise = False

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

if isSetWise:
    print("setwise coprime")
    exit()

print("not coprime")

Submission status: Time Limit Exceeded

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

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_right

import math
from functools import reduce

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

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

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

P = primes(10**6)

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

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

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

Submission status: 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()
    while num%2==0:
        d.add(2)
        num //= 2
    for i in range(3,int(sqrt(num))+1,2):
        while num%i==0:
            d.add(i)
            num //= i
    if num>2:
        d.add(num)
    return list(d)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

n = int(input())
a_list = list(map(int, input().split()))
flag1 = 1
ans2 = a_list[n - 1]
for i in range(n - 1):
    if a_list[i] == 1:
        continue
    if ans2 != 1:
        ans2 = gcd(ans2,a_list[i])
    if flag1 == 1:
        for j in range(i + 1, n):
            if gcd(a_list[i], a_list[j]) != 1:
                flag1 = 0
                break

if flag1 == 1:
    print("pairwise coprime")
elif ans2 == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
f = 0
m = 10**6 + 10
t = [0] * (10**6 + 10)

def bunkai(n):
    global f
    if n % 2 == 0 and t[2] == 0:
        t[2] = 1
    elif n % 2 == 0 and t[2] == 1:
        f = 1
        return
    while n % 2 == 0:
        n //= 2
    l = 3
    while l * l < n:
        if n % l == 0:
            if t[l] == 1:
                f = 1
                return
            while n % l == 0:
                n //= l
        l += 2
    if n != 1:
        if t[n] == 1:
            f = 1
        else:
            t[n] = 1

for i in range(N):
    bunkai(A[i])
    if f == 1:
        break

from math import gcd
g = A[0]
if f == 1:
    for i in range(1, N):
        g = gcd(g, A[i])
        if g == 1:
            break

if f == 0:
    print("pairwise coprime")
elif g == 1 and f == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
## 素因数分解
#nを素因数分解したリストを返す
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

N = INT()
A = LIST()
flag = True
A.sort(reverse=True)

memo = defaultdict(int)
s = set()
for a in A:
    d = divisor(a)
    # print(d)
    s = s.union(set(d))
    for y in d:
        if y == 1:
            continue
        elif memo[y] == 0:
            memo[y] += 1
        else:
            # print(d)
            flag = False
# print(s)
# exit()
# for a in A:
#     d = divisor(a)
#     set(d)
#     diff = s - set(d)
# for i in range(len(A) - 1):
# A[i]
# cnt = 0
# for a in A:
#     d = divisor(a)
#     # print(d)
#     for y in d:
#         if y == 1:
#             continue
#         if memo[y] == 1:
#             continue
#         else:
#             # print("d:", d)
#             cnt += 1
# if cnt == 0:
#     flag = True
    
if flag == True:
    print("pairwise coprime")
elif reduce(gcd, A) == 1:
        print("setwise coprime")
else:
    print("not coprime")
    

    # A.sort()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import gcd
from functools import reduce

from random import randint

def find_gcd(list):
    x = reduce(gcd, list)
    return x


def solve(N: int, A: "List[int]"):
    # A = list(set(A))

    q2 = True
    for a in A:
        for b in A:
            if a!=b and gcd(a, b) != 1:
                q2 = False
                break

    q1 = reduce(gcd, A) == 1


    if q1 and q2:
        print('pairwise coprime')
    elif q1:
        print('setwise coprime')
    else:
        print('not coprime')
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

flag = False
for i in range(N-1):
  for j in range(i+1, N):
    if math.gcd(A[i], A[j]) != 1:
      flag = True
      break
  if flag:
    break
if not flag:
  print('pairwise coprime')
  exit()

b = gcd_list(A)
if b == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n, ela):
    if n == 1:
        return {1: 1}
    if ela[n]:
        return {n: 1}

    prime_dict = {}
    for i, b in enumerate(ela):
        if not b:
            continue
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1000001)

    if max(A) == 1:
        print("pairwise coprime")
        exit()

    g = 10**8
    for i, a in enumerate(A):
        if i == 0:
            g = a
        else:
            g = math.gcd(g, a)

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    for a in A:
        if a == 1:
            continue

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela)
        PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    elif max_p == N:
        print("not coprime")
    else:
        print("setwise coprime")



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# # Make IO faster
# import sys
# input = sys.stdin.readline

# # get single (or) multiple str
# X = input()

# # get single int
# N = int(input())
# # get multiple int (e.g., 2)
# X, Y = map(int, input().split())
# # get multiple int (e.g., 2) for N lines
# XY = [list(map(int, input().split())) for _ in range(N)]

# from IPython import embed; embed(); exit();

# 全部入り
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


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

    if temp!=1:
        # arr.append([temp, 1])
        arr.add(temp)

    if arr==[]:
        # arr.append([n, 1])
        arr.add(n)

    return arr

N = INT()
A = list(MAP())

is_pw = True
pw_set = sw_set = factorization(A[0])
for a in A[1:]:
    nums = factorization(a)
    len_pw = len(pw_set)
    pw_set = pw_set | nums
    if len_pw + len(nums) != len(pw_set):
        is_pw = False
    sw_set = sw_set & nums

if is_pw:
    print("pairwise coprime")
elif len(sw_set) == 0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
def prime(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes
pp=prime(10**3)
p=[]
for i in range(2,1001):
  if pp[i]:
    p.append(i)
n=int(input())
a=list(map(int,input().split()))
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

g=a[0]
for i in a[1:]:
  g=gcd(g,i)
if g==1:
  mm=[0 for i in range(10**6+1)]
  f=True
  for i in a:
    if mm[i] and i!=1:
      f=False
      break
    mm[i]=1
    for j in range(168):
      if i%p[j]==0 and i!=p[j]:
        if mm[p[j]]:
          f=False
          break
        mm[p[j]]=1
        t=i//p[j]
        if mm[t] and t!=p[j]:
          f=False
          break
        mm[t]=1
    if not f:
      break
  if f:
    print("pairwise coprime")
  else:
    print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
def primeFactors(n):
    ret = set()
    x = 2
    while n > 1:
        while n%x == 0:
            ret.add(x)
            n = n//x
        x += 1
    return ret

N = int(input())
Arr = list(map(int, input().split()))
factors = [primeFactors(x) for x in Arr]
nc = False
for factor in factors[0]:
    this = True
    for f in factors:
        if not factor in f:
            this = False
            break
    if this:
        nc = True
        break

if nc:
    print("not coprime")
else:
    sc = False
    seen = set()
    for factor in factors:
        for f in factor:
            if f in seen:
                sc = True
                break
            else:
                seen.add(f)
        if sc: break
    if sc:
        print("setwise coprime")
    else:
        print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            while temp % i == 0:
                temp //= i
            arr.append(i)

    if temp != 1:
        arr.append(temp)

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

    a = set(arr)
    if 1 in a:
        a.remove(1)

    return a


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

is_pairwise = True
is_setwise = False

f_set = set()
n_set = set()

for item in a:
    if item in n_set:
        is_pairwise = False
        break
    else:
        if item != 1:
            n_set.add(item)
    for fc in make_divisors(item):
        if fc in f_set:
            is_pairwise = False
            break
        else:
            f_set.add(fc)
    if not is_pairwise:
        break

s_set = make_divisors(a[0])
for item in a[1:]:
    tmp_set = make_divisors(item)
    s_set = s_set & tmp_set
    if len(s_set) == 0:
        is_setwise = True

if is_pairwise:
    print('pairwise coprime')
elif is_setwise:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = tuple(map(int, input().split()))

fact_counts = [0] * (10**6+1)
def fact(n):
    if n%2 == 0:
        fact_counts[2] += 1
    while n%2 == 0:
        n //=2

    for f in range(3, int(n**0.5)+ 1, 2):
        if n%f == 0:
            fact_counts[f] += 1
        while n%f == 0:
            n //= f
    if n != 1:
        fact_counts[n] += 1

for a in A:
    fact(a)

pairwise = True
for c in fact_counts:
    if c > 1:
        pairwise = False

if pairwise:
    print('pairwise coprime')
else:
    if max(fact_counts) == n:
        print('not coprime')
    else:
        # すべてに共通する素因数が見つからなかったら
        print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:

import math
#素数列挙
def get_primes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        A = [i for i in A if i%prime!=0]

    for a in A:
        P.append(a)
            
    return P


def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    sosus = set(get_primes(max(A)+1))
    dvd = set()






    for i in A:
        tmp=[]
        for j in sosus:
            if i % j ==0:
                tmp.append(j)
                while i % j ==0:
                    i //=j
            if i ==1:
                break
        sosus.difference_update(tmp)
        
        if i != 1:
            break
    else:
        print('pairwise coprime')
        return

    val = A[0]
    for i in A:
        val = math.gcd(i,val)

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

resolve()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from math import gcd 

n = int(input())
A = list(map(int, input().split()))
pr = [True]*(10**6+5)
for a in A:
    vals = [i for i in range(2, a) if a % i == 0]
    for v in vals:
        for i in range(v, 10**6+2, v):
            if not pr[i]:
                break
            pr[i] = False
        else:
            continue
        break
    else:
        continue
    break
else:
    print('pairwise coprime')
    exit()

if reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	nn=II()
	A=LI()
	ans="pairwise coprime"

	n = 1000000
	primes = set(range(2, n+1))
	for i in range(2, int(n**0.5+1)):
		primes.difference_update(range(i*2, n+1, i))
	primes=set(primes)

	#print(primes)


	B=set(range(1,10**6+1))
	C=set()
	for i in A:
		a=set()
		while i%2==0:
			a.add(2)
			i//=2
		f=3
		while f*f<=i:
			if i in primes:
				break
			elif i%f==0:
				a.add(f)
				i//=f
			else:
				f+=2
		if i!=1:
			a.add(i)
		B&=a
		if C&a:
			ans="setwise coprime"
		C|=a

	if B:
		ans="not coprime"

	print(ans)





















if __name__ == "__main__":
	main()

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


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


pair_flg=0
set_flg=0
n=I()
A=LI()
prime=primes(10**6)
    
t_set=set()
s_set=set()
D=defaultdict(set)
for i in prime:
    D[i]={i}

for j in range(n):
    a=A[j]
    prime_set = D[A[j]]
    flg=0
    if not prime_set:
        for i in range(2, int(a ** 0.5) + 1):
            while a % i == 0:
                prime_set.add(i)
                a //= i
                if D[a]:
                    prime_set|=D[a]
                    flg=1
                    break
            if a == 1 or flg:
                break
        if a != 1:
            prime_set.add(a)
        D[A[j]]=prime_set
    if prime_set&t_set:
        pair_flg=1
    if pair_flg==0:
        t_set|=prime_set
    if j:
        s_set&=prime_set
    else:
        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 math
from functools import reduce

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

check1 = False
check2 = True

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
def prime_decomposition(x):
  i = 2
  ls = []
  while i * i <= x:
    while x % i == 0:
      x /= i
      if i not in ls:
        ls.append(i)
    i += 1
  if x > 1:
    ls.append(x)
  return ls

if gcd_list(A) == 1:
  check1 = True
  
  divisors = []
  for a in A:
    for i in prime_decomposition(a):
      if i in divisors:
        check2 = False
        break
      else:
        divisors.append(i)
    
    if not check2:
      break
  
else:
  check1 = False
  check2 = False
    
if check1 and check2:
  print("pairwise coprime")
elif check1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd, sqrt


def Calc_Divisors(num):
    divisors = []
    for i in range(1, int(sqrt(num)) + 1):
        if num % i == 0:
            if i != 1:
                divisors.append(i)
            if i != num // i:
                divisors.append(num//i)
    # divisors.sort()
    return divisors


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

    s_tmp = A[0]
    p_flag = True
    p_dic = []
    for a in A:
        s_tmp = gcd(s_tmp, a)
        if p_flag:
            tmp = Calc_Divisors(a)
            for t in tmp:
                if t not in p_dic:
                    p_dic.append(t)
                else:
                    p_flag = False
                    continue

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy
n = int(input())
arr = list(map(int,input().split()))
x = 1
for i in range(n-1):
  for j in range(i+1,n):
    if numpy.gcd(arr[i],arr[j]) != 1 :
      x = 0
      break
    
if x == 0:
  if numpy.gcd.reduce(arr) == 1: print('setwise coprime')
  else: print('not coprime')
else : print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
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 primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

n=int(input())
alist=list(map(int, input().split()))
blist=[0]*1000001
for i in alist:
  for j in factorization(i):
    blist[j[0]]+=1
cnt=1
for i in primes(1000001):
  cnt=max(cnt,blist[i])
if cnt==1:
  print('pairwise coprime')
else:
  num=alist[0]
  for i in range(n):
    num=math.gcd(num,alist[i])
  if num==1:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n=int(input())

A=list(map(int,input().split()))
from math import sqrt
def eratosu(n):
  if not isinstance(n,int):
    raise TypeError("nがint型になってねえぞ")
  if n<2:
    raise ValueError('nが2よりちっちぇえぞ')
  prime = []
  limit = sqrt(n)
  data = [i+1 for i in range(1, n)]  #2,3,4,...,n
  while True:
    p = data[0]
    if limit <= p:
        return prime + data
    prime.append(p)
    data = [e  for e in data if e % p != 0]
PRIME=eratosu(10**6+10)
@lru_cache(maxsize=10**10)
def bunkai(n):
    if n==1:return []
    ans=[]
    temp=n
    #そんな早くしなくてよかったり、何回もするわけじゃないなら、
    #for i in range(2,int(sqrt(n))+1): とかで
    primelist= PRIME
    for i in primelist:
        if i>sqrt(n):break
        if temp % i ==0:
            ji=0
            while temp%i==0:
                ji+=1
                temp//=i
            ans.append([i,ji])
    if ans==[]:return([[n,1]])  #素数のとき
    if temp!=1:
        ans.append([temp,1])  #4*5882353とか
    return ans

flag=1
seen={i:0 for i in PRIME}
#print(bunkai(3))
for i in A:
    for l in bunkai(i):
        now=l[0] 
        if now==1:continue
        if seen[now]!=0:
            flag=0
        seen[now]+=1
if flag:
    print("pairwise coprime")
elif max(seen.values())!=n:
    print("setwise coprime")
else:
    print("not coprime")

#print(seen)