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

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

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

for i in range(n):
    is_pair_wise_coprime = True
    for j in range(i + 1, n):
        if math.gcd(numbers[i], numbers[j]) != 1:
            is_pair_wise_coprime = False
            break
    if not is_pair_wise_coprime:
        break
else:
    print('pairwise coprime')
    exit(0)

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

Submission status: Time Limit Exceeded

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

def eratosthenes(n):
    multiples = set()
    for i in range(2, n+1):
        if i not in multiples:
            yield i
            for j in range(i*i, n+1, i):
                multiples.add(j)

primes = list(eratosthenes(1000000))
seen = [0] * len(primes)
pc = True
for x in a:
    for i, p in enumerate(primes):
        if p > x: break
        if x % p == 0:
            seen[i] += 1
            if seen[i] > 1: pc = False
            while x % p == 0: x //= p
if pc:
    print('pairwise coprime')
elif n in seen:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd


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


n = int(input())
a = list(map(int, input().split()))
b = a[0]
for i in range(1, n):
    b = gcd(b, a[i])
    if b == 1:
        break
else:
    print("not coprime")
    exit()

a = list(map(factorize, a))
wa = a[0]
cnt = 0
flag = 0
for i in range(1, n):
    if len(wa & a[i]) > 0 and flag == 0:
        flag = 1
    wa = wa | a[i]

if flag:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Time Limit Exceeded

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

pairwise = True
for i in range(n - 1):
    for j in range(i + 1, n):
        if gcd(a[i], a[j]) != 1:
            pairwise = False
            break
if pairwise:
    print('pairwise coprime')
    exit()

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

n = int(input())
a = sorted(map(int,input().split()), reverse =True)

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

if ans != 1:
  print("not coprime")
  sys.exit()

#print(a)
for i in range(n):
  for j in range(i+1,n):
    if (math.gcd(a[i],a[j]) != 1): 
      	print("setwise coprime")
      	sys.exit()

print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 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 can_factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  # ここにバグがないか心配
        if temp % i == 0:
            arr.append(i)

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

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

    return arr


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
# cnt = defaultdict(lambda: 0)
cnt = [0] * (10**6)
flg = 1  # pairwiseであるフラグ
# if N > 3 * (10**5):
#     flg = 0
#     for a in A:
#         g_set = gcd(g_set, a)
# else:
for a in A:
    g_set = gcd(g_set, a)
    for p, n in factorization(a):
        if cnt[p] != 0:
            flg = 0
        cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
def gcd(ls):
    smallest = min(ls)
    for divider in range(smallest, 0, -1):
        count = 0
        for number in a:
            if number % divider == 0:
                count += 1
        if count == len(ls):
            return divider
            break
def couple(f, s):
    love = 1
    if f >= s:
        min = s
    else:
        min = f
    for divider in range(1, min):
        if s % divider == 0 and f % divider == 0:
            if divider > love:
                love = divider
    return love
if gcd(a) == 1:
    count = 0
    for number in range(n):
        for pair in range(0, number):
            if couple(a[number], a[pair]) == 1:
                count += 1
    if count == n*(n-1)/2:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import collections

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

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

d = {}
flag = False
for i in a:
    data = collections.Counter(prime_factorize(i))
    for k in data:
        try:
            if d[k] >= 1:
                d[k] += 1
                flag = True
        except:
            d[k] = 1
if not flag:
    print("pairwise coprime")
else:
    flag = False
    for i in d.values():
        if i == len(a):
            print("not coprime")
            flag = True
            break
    if not flag:
        print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
# https://cs.stackexchange.com/questions/93030/algorithm-for-checking-if-a-list-of-integers-is-pairwise-coprime

import math
n = int(input())
nums = list(map(int, input().split()))

gcd_ = nums[0]
for num in nums[1:]:
    gcd_ = math.gcd(gcd_, num)

if gcd_ >= 2:
    print('not coprime')
    exit()



def smallest_divisor(num, start):
    if num == 1:
        raise ValueError("error!")
    d = start
    while d * d <= num:
        if num % d == 0:
            return d
        d += 1
    return num


prime_set = set()

for num in nums:
    if num == 1:
        continue

    soinsuu = set()
    
    warareru = num
    start = 2
    while True:
        divi = smallest_divisor(warareru, start)
        soinsuu.add(divi)
        warareru = warareru // divi
        start = divi
        if warareru == 1:
            break
    # print(soinsuu)
    if soinsuu & prime_set:
        print('setwise coprime')
        exit()
    else:
        prime_set |= soinsuu

print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
from functools import reduce
N = int(input())
A = list(map(int,input().split()))

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

def primeFactorization(n):
    res = defaultdict(int)
    m = int(n**0.5)
    for i in range(2,m+1):
        while n % i == 0:
            n = n//i
            res[i] += 1
    if n > 1:
        res[n] = 1
    return res

pset = set()
for a in A:
    pf = primeFactorization(a).keys()
    if pset.intersection(pf):
        break
    pset = pset.union(pf)
else:
    print('pairwise coprime')
    exit()

allgcd = reduce(gcd, A)
if allgcd == 1:
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Time Limit Exceeded

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

def LCM(x, y):
    return x*y//GCD(x,y)

n = int(input())
a = [int(x) for x in input().split()]
g = a[0]
for i in range(1,n):
    if g > a[i]:
        g,a[i] = a[i], g
    g= GCD(a[i], g)

if g > 1:
    print("not coprime")
else:
    prod = 1
    for i in range(0, n):
        prod *= a[i]

    lcm = a[0]
    for i in range(1, n):
        if lcm > a[i]:
            lcm, a[i] = a[i], lcm
        lcm = LCM(a[i], lcm)

    if prod == lcm:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Time Limit Exceeded

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

from collections import defaultdict

############ ---- Input Functions ---- ############

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

############ ---- Solution ---- ############

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

def solve():
    N = inp()
    AA = inlt()
    
    mult = AA[0]
    gcd_cum = AA[0]
    pairwise = True

    for i in range(1, N):
        if i == 1 or (gcd_cum == 1 and pairwise):
            g = gcd(mult, AA[i])
            if g != 1:
                pairwise = False
            mult = mult * (AA[i] // g)
        gcd_cum = gcd(gcd_cum, AA[i])
    
    if gcd_cum == 1 and pairwise:
        return "pairwise coprime"

    if gcd_cum == 1:
        return "setwise coprime"
    
    return "not coprime"

    

if len(sys.argv) > 1 and sys.argv[1].startswith("input"):
    f = open("./" + sys.argv[1], 'r')
    input = f.readline

res = solve()
print(str(res))

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
t = [0]*1000
s = []
for i in range(n):
    for j in range(2,1000):
        if(a[i]%j == 0):
            t[j] += 1
            a[i] //= j
            if(a[i] == 1):
                break
    if(a[i] != 1):
        s.append(a[i])
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    z = 0
    for i in range(1,len(s)):
        for j in range(i):
            if(math.gcd(s[i],s[j]) > 1):
                z = 1
                break
    if(z == 1):
        print('setwise coprime')
    else:
        print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
from math import gcd
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
        
    class Eratos:
        def __init__(self, num: int):
            '''
            O(nlglgn) で num までの素数判定テーブルを作る
            >>> e = Eratos(10)
            >>> e.table
            [False, False, True, True, False, True, False, True, False, False, False]
            '''
            if num < 1:
                raise ValueError(f'Eratos.__init__(): argument should be >= 1. got {num}')
            self.table_max = num
            # self.table[i] は i が素数かどうかを示す (bool)
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            i = 2
            while i ** 2 <= num:
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    # i**2 からスタートすることで定数倍高速化できる
                        self.table[j] = False
                i += 1
            self.candidate = []
            i = 2 
            while i ** 2 <= num:
                if self.is_prime(i):
                    self.candidate.append(i)
                i += 1            


        def is_prime(self, num: int) -> bool:
            '''
            O(1) で素数判定を行う
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
            '''
            if num < 1:
                raise ValueError(f'Eratos.is_prime(): argument shoule be >= 1. got {num}')
            if num > self.table_max:
                raise ValueError(f'Eratos.is_prime(): exceed table_max({self.table_max}). got {num}')
            return self.table[num]

        def prime_factorize(self, num: int) -> Dict[int, int]:
            '''
            O(√n) で素因数分解を行う
            >>> e = Eratos(10000)
            >>> e.prime_factorize(6552)
            {2: 3, 3: 2, 7: 1, 13: 1}
            '''
            if num < 1:
                raise ValueError(f'Eratos.prime_factorize(): argument shoule be >= 1. got {num}')
            if (self.table_max + 1) ** 2 < num:
                raise ValueError('Eratos.prime_factorize(): exceed prime table size. got {}'.format(num))
            # 素因数分解の結果を記録する辞書        
            factorized_dict = dict()
            # n について、√n 以下の素数で割り続けると最後には 1 or 素数となる
            # 背理法を考えれば自明 (残された数が √n より上の素数の積であると仮定。これは自明に n を超えるため矛盾)
            for p in self.candidate:
                if num == 1:    # これ以上調査は無意味
                    break
                if num % p == 0:
                    # cnt = 0
                    while num % p == 0:
                        num //= p
                        # cnt += 1
                    # factorized_dict[p] = cnt
                    factorized_dict[p] = 1
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict


    def check_setwise(n, L):
        gcd_memo = L[0]        
        for i in range(n):
            gcd_memo = gcd(L[i], gcd_memo)
        return gcd_memo == 1


    def check_pairwise(n, L):
        eratos = Eratos(10**6)
        c = Counter()
        for i in range(n):
            c += Counter(eratos.prime_factorize(L[i]))
        for v in c.values():
            if v != 1:
                return False
        return True


    n = ii()
    L = lmi()
    if check_pairwise(n, L):
        print('pairwise coprime')
    elif check_setwise(n, L):
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, 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]


n = inp()
a = inpl()

data = get_sieve_of_eratosthenes(10**6)

ans = "pairwise coprime"
for i in data:
    coprime = 0
    for j in range(n):
        if a[j] % i == 0:
            coprime += 1
        elif a[j] % i != 0 and coprime >= 2:
            break
    if coprime == n:
        ans = "not coprime"
        break
    elif coprime >= 2:
        ans = "setwise coprime"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import math
import sys

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

gcd = []
for i in range(len(lis)):
    gcd.append(math.gcd(lis[i][0], lis[i][1]))
if max(gcd) ==1:
    print('pairwise coprime')
    sys.exit()

ans = A[0]
for i in range(1, N):
    ans = math.gcd(ans, A[i])
if ans == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd
n = int(input())
a = list(map(int, input().split()))
a.sort()
used = [False] * (10**6+1)

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

input_list = sieve_of_erastosthenes(10**6+1)
prime_list = [i for i, b in enumerate(input_list) if b == True]

def factorization(n):
    arr = []
    temp = n
    for i in prime_list:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

g = a[0]
arr = factorization(a[0])
for i in arr:
    used[i] = True

pair = True
for i in range(n-1):
    g = gcd(g, a[i+1])
    # 一度でも互いに素でない組合せが出たらpariwise coprimeではない
    arr = factorization(a[i+1])
    for i in arr:
        if i == 1: continue
        if used[i]: pair=False
        used[i] = True
if g > 1:
    print('not coprime')
    exit(0)
if not pair:
    print('setwise coprime')
    exit(0)
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
N = int( input() )
A = sorted( list(map(int, input().split())))
ans = A[0]
# http://www.ysr.net.it-chiba.ac.jp/~yashiro/sosu/
P = list( map( int, "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997".split(" ")))
L = []
def factorization(n):
    temp = n
    K = []
    for p in P:
      if p > int(-(-n**0.5//1))+1:
        break
      if temp%p==0:
        cnt=0
        while temp%p==0:
          cnt+=1
          temp //= p
        if p in L:
          return True
        K.append( p )
    if temp!=1:
      if temp in L:
        return True
      K.append( temp )
    if L==[]:
      L.append( n )
    L.extend( K )
    return False

for i in range(1, N):
    ans = math.gcd(ans, A[i])
    if ans == 1:
      break
if ans != 1:
  ret = "not coprime"
else:
  ret = "pairwise coprime"
  for a in A:
    if factorization( a ):
      ret = "setwise coprime"
      break
print( ret )

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):
    if n == 1:
        return {1: 1}

    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        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 main():
    N = NI()
    A = NLI()

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

    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)
        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:
#E
from math import gcd
N=int(input())
A=list(map(int,input().split()))
GCD=A[0]
for i in range(1,N):
    GCD=gcd(GCD,A[i])
    
def Primefact(n):
    Dic={}
    for i in range(2,int(pow(n,0.5))+1):
        if n%i==0:
            Dic[i]=0
            while True:
                n/=i
                Dic[i]+=1
                if n%i!=0:
                    break
        if n==1:
            break
    if n!=1:
        Dic[int(n)]=1
    return Dic

if GCD==1:
    L=[False for i in range(10**6+1)]
    flag=False
    for i in range(N):
        Li=Primefact(A[i])
        for k,v in Li.items():
            if L[k]:
                flag=True
                break
            else:
                L[k]=True
    if flag:
        ans="setwise coprime"
    else:
        ans="pairwise coprime"
else:
    ans="not coprime"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())
numbers = list(map(lambda x: int(x), input().split()))
if_set_has_gcd = False
if_pair_has_gcd = False

max_divider = int(max(numbers) ** 0.5) + 1

for divider in range(2, max_divider + 1):
    num_divided = sum([each % divider == 0 for each in numbers])
    if num_divided == n:
        if_set_has_gcd = True
    if num_divided >= 2:
        if_pair_has_gcd = True

# print(if_set_has_gcd, if_pair_has_gcd)    
if not if_pair_has_gcd:
    print('pairwise coprime')
    sys.exit()
    
if not if_set_has_gcd:
    print('setwise coprime')
    sys.exit()
    
print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
check_list = [0]*1000010
conf = False

def make_divisors(n):
    divisors = []
    global conf
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if check_list[i] == 1:
                conf = True
            elif check_list[i] == 0 and i != 1:
                check_list[i] = 1
            if i != n // i:
                divisors.append(n//i)
                if check_list[n//i] == 1:
                    conf = True
                elif check_list[n//i] == 0 and n//i != 1:
                    check_list[n//i] = 1
    # divisors.sort()
    return divisors[1:]

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

    insec = set(make_divisors(A[0]))
    val = A[0]
    for i in range(1, len(A)):
        insec = insec & set(make_divisors(A[i]))
    if len(insec) != 0:
        return "not coprime"
    else:
        if conf:
            return "setwise coprime"
        else:
            return "pairwise coprime"

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

Submission status: Time Limit Exceeded

Solution code:
import math, collections

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

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

gcd = 0
for i in range(n):
    gcd = math.gcd(gcd, a[i])
if gcd != 1:
    print("not coprime")
else:
    flag = True
    a2 = collections.deque(a)
    while len(a2) > 1:
        temp1 = a2.popleft()
        temp2 = a2.popleft()
        if math.gcd(temp1, temp2) != 1:
            print("setwise coprime")
            break
        else:
            a2.append(temp1 * temp2)
    else:
        print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
n = raw_input()
def gcd(a,b):
	if b == 0:
		return a
	return gcd(b,a%b)



def f(ais):
	seen = set()
	bis = ais[::]
	flag=  True
	for ai in bis[::]:
		factor =2
		while(ai != 1):
			if ai % factor == 0:
				if factor in seen:
					flag = False
					break
				while(ai % factor == 0):
					ai /= factor

				seen.add(factor)
			factor +=1
	if flag:
		return 'pairwise coprime'
	if reduce(gcd, ais) == 1:
		return 'setwise coprime'
	return 'not coprime'
print f(map(int, raw_input().split()))