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

for a in list_A:
    list_S.append(list(set(prime_factorize(a))))

g = set()
cnt = 0
k = set(list_S[0])

for l in list_S:
    g = g | set(l)
    cnt += len(l)
    k = k & set(l)

if len(list(g)) == cnt:
    print("pairwise coprime")
elif len(list(k)) == 0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

k = set()
s = set(prime_factorize(list_A[0]))
cnt = 0

for a in list_A:
    l = prime_factorize(a)
    s = s & set(l)
    k = k | set(l)
    cnt += len(list(set(l)))

if cnt == len(list(k)):
    print("pairwise coprime")
elif len(list(s)) == 0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

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

div=[[] for _ in range(n)]
for i in range(n):
  ll=l[i]
  while ll>1:
    div[i].append(d[ll])
    ll//=d[ll]

cnt=[]
for i in range(n):
  div[i]=set(div[i])
  div[i]=list(div[i])
  cnt+=div[i]

if len(cnt)==len(set(cnt)):
  print('pairwise coprime')
  exit()

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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce

n = int(input())
A = list(map(int, input().split()))
res = ['pairwise coprime', 'setwise coprime', 'not coprime']

# 素因数分解 O(n ** 0.5)
def prime_factor(n):
    factor = []
    for i in range(2, int(n ** 0.5) + 1):
        while (n % i == 0):
            factor.append(i)
            n //= i
    if n != 1:
        factor.append(n)
    return factor

prime_factors = []
for a in A:
    factor = prime_factor(a)
    factor_set = list(set(factor))
    prime_factors.extend(factor_set)

if len(prime_factors) == len(set(prime_factors)):
    print(res[0])
elif reduce(gcd, A) == 1:
    print(res[1])
else:
    print(res[2])

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce


def solve(N, As):
    for i in range(N - 1):
        for j in range(N - i - 1):
            gcd = math.gcd(As[i], As[i + j + 1])
            if gcd > 1:
                if reduce(math.gcd, As) == 1:
                    print('setwise coprime')
                else:
                    print('not coprime')
                exit(0)
    print('pairwise coprime')


if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split()))
    solve(N, As)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(d) for d in input().split()]

A_max = max(A)

p = [True] * (A_max + 1)
c = [0] * (A_max + 1)

pair = True

for i in range(2, A_max + 1):
    if p[i]:
        for j in range(i*2, A_max+1, i):
            p[j] = False
        for a in A:
            if a%i == 0:
                c[i] += 1
        if c[i] >= 2:
            pair = False
            break


if pair:
    print("pairwise coprime")
else:
    import math
    from functools import reduce
    g = reduce(lambda x, y: math.gcd(x, y), A)
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

A_max = max(A)
prime = [[] for _ in range(A_max + 1)]
for i in range(2,A_max + 1):
    if prime[i] == []:
        n = i
        while n <= A_max:
            prime[n].append(i)
            n += i

li = [0] * (A_max + 1)
for a in A:
    for p in prime[a]:
        li[p] += 1


if max(li) <= 1:
    print('pairwise coprime')
elif max(li) == N:
    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 main():
    n = int(input())
    A = list(map(int,input().split()))
    LCM = 1
    GCD = A[0]
    flag = True
    for a in A[::-1]:
        if gcd(LCM,a) > 1:
            flag = False
            break
        LCM = lcm(LCM,a)
    for a in A:
        GCD = gcd(GCD,a)
    if flag:
        print("pairwise coprime")
    elif GCD == 1:
        print("setwise coprime")
    else:
        print("not coprime")
    return

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from math import gcd

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

num = 10 ** 6
primes = [0] * (num + 1)
primes[0] = 1
primes[1] = 1

for i in range(2, num + 1):
    if primes[i] != 0:
        continue

    cnt = 1
    while i * cnt <= num:
        primes[i * cnt] = i
        cnt += 1


def func(n):
    res_dic = defaultdict(int)
    while n > 1:
        x = primes[n]
        res_dic[x] += 1
        n //= x

    return res_dic


pairwise = True
cnt_dic = defaultdict(int)
for a in A:
    dic = func(a)

    for k in dic.keys():
        cnt_dic[k] += 1
        if cnt_dic[k] > 1:
            pairwise = False
            break

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

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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

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

num = 10 ** 6
is_prime = [True] * (num + 1)
is_prime[0] = False
is_prime[1] = False

for i in range(2, num + 1):
    if not is_prime[i]:
        continue

    cnt = 2
    while i * cnt <= num:
        is_prime[i * cnt] = False
        cnt += 1

primes = [i for i, p in enumerate(is_prime) if p]

pairwise = True
for p in primes:
    cnt = 0
    for a in A:
        if a % p == 0:
            cnt += 1

    if cnt > 1:
        pairwise = False
        break

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

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

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
import sys, math, heapq
from functools import reduce
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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


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


fctA = [fctr1(a) for a in A]
pfactors = defaultdict(int)
is_pc = True
for fcta in fctA:
    if not (is_pc):
        break
    for p in fcta:
        pn = p[0]
        if pfactors[pn] > 0:
            is_pc = False
            break
        else:
            pfactors[pn] += 1
if is_pc:
    print("pairwise coprime")
else:
    is_sc = reduce(gcd, A) == 1
    if is_sc:
        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()))

A.sort()
A_max = A[-1]


def prime_factorization(n):
    counter = Counter()

    if n < 2:
        return counter

    for i in range(2, int(n ** 0.5) + 1):
        if i * i > n:
            break

        while n % i == 0:
            counter[i] += 1
            n //= i

    if n > 1:
        counter[n] += 1

    return counter


used = set()
A_set = set(A)

pairwise = True
setwise = True

u = set()
flag = True
for a in A:
    counter = prime_factorization(a)

    if flag:
        u = set(counter.keys())
        flag = False
    else:
        u = u.intersection(counter.keys())

    if pairwise:
        for k in counter.keys():
            if k in used:
                continue

            v = k
            cnt = 1

            while v <= A_max:
                if v != a and v in A_set:
                    pairwise = False
                    break

                cnt += 1
                v = k * cnt

            if not pairwise:
                break

            used.add(k)


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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
import random

# test1 = gcd(40, 20, 1)
# test2 = gcd(60, 40, 1)
# test3 = gcd(50, 3, 1)

# print(test1, test2, test3)

def f(n, ais):
    common_divisor = ais[0]
    for (i, ai) in enumerate(ais):
        common_divisor = gcd(ai, common_divisor)
        for (j, aj) in enumerate(ais[i+1:]):
            if gcd(ai, aj) != 1:
                for aiu in ais[i+1:]:
                    common_divisor = gcd(aiu, common_divisor)
                if common_divisor == 1:
                    return 'setwise coprime'
                else:
                    return 'not coprime'
        # print(common_divisor)
    return 'pairwise coprime'

def make_prime_list():
    l = [2]
    for i in range(3, 1000000, 2):
        for j in l:
            if i % j == 0:
                break;
        else:
            l.append(i)
    return l;

def find_prime(n, l):
    result = set()
    for p in l:
        if n % p == 0:
            result.add(p)
            while n % p == 0:
                n = n // p
        if p >= n:
            return result
    return result

# l = make_prime_list()
# print(find_prime(60, l))
# print(find_prime(1, l))
# print(find_prime(7, l))

def f(n, ais):
    koremadenolcm = 1
    koremadenogcd = ais[0]
    pairwise_coprime = True
    for ai in ais:
        if pairwise_coprime:
            g = gcd(koremadenolcm, ai)
            if g != 1:
                pairwise_coprime = False
            else:
                koremadenolcm = koremadenolcm * ai
        koremadenogcd = gcd(koremadenogcd, ai)
    if pairwise_coprime:
        return 'pairwise coprime'
    elif koremadenogcd == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'

# def test(n, ais, r):
#     result = f(n, ais)
#     print('{} n={}, ais={}, result={}'.format(result == r, n, ais, result))

# r1 = 'pairwise coprime'
# r2 = 'setwise coprime'
# r3 = 'not coprime'

# test(2, [6, 6], r3)
# test(3, [4, 7, 3], r1)
# test(3, [2, 3, 4], r2)
# test(3, [2, 4, 6], r3)

# test(3, [3, 4, 5], r1)
# test(3, [6, 10, 15], r2)
# test(3, [6, 10, 16], r3)

# test(2, [100, 1], r1)
# test(3, [8, 1, 800], r2)
# test(3, [1, 1, 1], r1)
# test(4, [2, 3, 5, 7], r1)
# test(4, [2, 3, 5, 10], r2)

# test(3, [100, 10, 1], r2)

# test(3, [1000000, 777777, 11], r2)

# print(f(1000000, random.sample(range(2, 1000000), k=1000000)))
# test(10000, random.sample(range(2, 1000000), k=10000), r2)

n = int(input())
ais = list(map(int, input().split(' ')))
print(f(n, ais))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from math import sqrt

def gen_primes(X):
    is_prime = [True for _ in range(0, X+1)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for n in range(2, int(sqrt(X))):
        if is_prime[n]:
            primes.append(n)
            j = n*2
            while j <= X:
                is_prime[j] = False
                j += n
    primes.extend([x for x in range(int(sqrt(X)), X+1) if is_prime[x]])
    return primes


def solve(N, A):
    primes = gen_primes(10**6)
    C = [0] * len(primes)

    for a in A:
        for i, p in enumerate(primes):
            if a < p:
                break
            if a % p == 0:
                C[i] += 1
    M = max(C)
    #print(A)
    #print(M)
    if M <= 1:
        print("pairwise coprime")
    elif M != N:
        print("setwise coprime")
    else:
        print("not coprime")
    
N = int(input())
A = [int(x) for x in input().split()]
solve(N, A)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from math import sqrt

def gen_primes(X):
    is_prime = [True for _ in range(0, X+1)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for n in range(2, int(sqrt(X))):
        if is_prime[n]:
            primes.append(n)
            j = n*2
            while j <= X:
                is_prime[j] = False
                j += n
    primes.extend([x for x in range(int(sqrt(X)), X+1) if is_prime[x]])
    return primes


def solve(N, A):
    primes = gen_primes(10**6)
    C = [0] * len(primes)

    for a in A:
        for i, p in enumerate(primes):
            if a % p == 0:
                C[i] += 1
    M = max(C)
    #print(A)
    #print(M)
    if M <= 1:
        print("pairwise coprime")
    elif M != N:
        print("setwise coprime")
    else:
        print("not coprime")
    
N = int(input())
A = [int(x) for x in input().split()]
solve(N, A)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

# test1 = gcd(40, 20, 1)
# test2 = gcd(60, 40, 1)
# test3 = gcd(50, 3, 1)

# print(test1, test2, test3)

def f(n, ais):
    common_divisor = ais[0]
    for (i, ai) in enumerate(ais):
        common_divisor = gcd(ai, common_divisor)
        for (j, aj) in enumerate(ais[i+1:]):
            if gcd(ai, aj) != 1:
                for aiu in ais[i+1:]:
                    common_divisor = gcd(aiu, common_divisor)
                if common_divisor == 1:
                    return 'setwise coprime'
                else:
                    return 'not coprime'
        # print(common_divisor)
    return 'pairwise coprime'

# def test(n, ais, r):
#     result = f(n, ais)
#     print('{} n={}, ais={}, result={}'.format(result == r, n, ais, result))

# r1 = 'pairwise coprime'
# r2 = 'setwise coprime'
# r3 = 'not coprime'

# test(2, [6, 6], r3)
# test(3, [4, 7, 3], r1)
# test(3, [2, 3, 4], r2)
# test(3, [2, 4, 6], r3)

# test(3, [3, 4, 5], r1)
# test(3, [6, 10, 15], r2)
# test(3, [6, 10, 16], r3)

# test(2, [100, 1], r1)
# test(3, [8, 1, 800], r2)
# test(3, [1, 1, 1], r1)
# test(4, [2, 3, 5, 7], r1)
# test(4, [2, 3, 5, 10], r2)

# test(3, [100, 10, 1], r2)

# test(3, [1000000, 777777, 11], r2)

n = int(input())
ais = list(map(int, input().split(' ')))
print(f(n, ais))

Submission status: Time Limit Exceeded

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

def div(n):
    for k in range(2,n+1):
        if n % k == 0:
            return k
    return 1

def pf(n):
    pf=[]
    while n != 1:
        pf.append(div(n))
        n = n // div(n)
    p = list(set(pf))
    return p

"""pc = True
for i in range(N-1):
    ai = pf(A[i])
    li = len(ai)
    for j in range(i+1,N):
        aj = pf(A[j])
        lj = len(aj)
        a = list(set(ai + aj))
        if (li + lj) != len(a):
            pc = False
            break
        """


cp = False
apf =[]
for e in range(N):
    apf.extend(pf(A[e]))
l1 = len(apf)
l2 = len(list(set(apf)))
if l1 == l2:
    cp = True

if cp == False:
    sc = False
    g = functools.reduce(math.gcd, A)
    if g == 1:
        sc = True


if cp == True:
    print('pairwise coprime')
elif sc == True:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

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

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)
    a.sort()
    return a
#############################################################

primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i])
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

# 全て1の時、primesが空になってmaxが取れない
if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
# min_cnt = min(primes.values())

if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

# エラトステネスの篩
#############################################################
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 = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
#############################################################

# 素因数分解、リストで返す
#############################################################
def prime_factorize(n, prime_list):
    a = []
    for p in prime_list:
        while p * p <= n:
            if n % p == 0:
                a.append(p)
                n //= p
            else:
                break
    if n != 1:
        a.append(n)
    a.sort()
    return a
#############################################################


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

data = set(get_sieve_of_eratosthenes(10**6))

primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i], data)
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

# print(primes)

if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

# エラトステネスの篩
#############################################################
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 = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
#############################################################

# 素因数分解、リストで返す
#############################################################
def prime_factorize(n, prime_list):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if f in prime_list and n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a.sort()
    return a
#############################################################

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

data = set(get_sieve_of_eratosthenes(10**6))

primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i], data)
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

# print(primes)

if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from math import ceil
def mpfli(N): #minimum prime factor listのこと
    li = [i for i in range(N+1)]
    li2 = [i for i in range(N+1)]
    for i in range(2,ceil(sqrt(N+1))):
        for j in range(2*i, N + 1):
            if li[j]== li2[j]:
                if li[j] % li[i] == 0:
                    li[j] = li[i]
    return li


def pfac(n): #高速素因数集合。 先に mpfli(N)がmpfとして与えられているという前提のコード
    S = set()
    while n != 1:
        m = mpf[n]
        S = S.union({m})
        n = n // m
    return S


def paerwise_coprime(A):
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            if pfac(A[i]) & pfac(A[j]) != {}:
                return False
            else:
                return True


def setwise_coprime(A):
    S = pfac(A[0])
    for i in range(1, len(A)):
        S = S & pfac(A[i])
    if S != {}:
        return False
    else:
        return True


def main():
    mpf = mpfli(10**6+1)
    N = input()
    A = list(map(int, input().split()))
    if pairwise_coprime(A):
        print('pairwise coprime')
    elif setwise_coprime(A):
        print('setwise coprime')
    else:
        print('not coprime')


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
import queue
import collections
import math
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

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

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

	tmp = set()
	while a > 1:
		tmp.add(sieve[a])
		a //= sieve[a]

	return tmp


def main():
	N = i_input()
	A = i_list()

	d = dict()

	max_A = max(A)
	count_list = []
	for i in range(0,max_A):
		count_list.append(0)

	for a in A:
		for p in ((set(factorization(a)))):
			if(d.get(p,-1)==-1):
				d[p] = 1
			else:
				d[p] +=1


	if (max(d.values())==1):
		print("pairwise coprime")
	elif(gcd_list(A)==1):
		print("setwise coprime")
	else:
		print("not coprime")

	return

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
import queue
import collections
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

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

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


def main():
	N = i_input()
	A = i_list()

	max_A = max(A)
	count_list = []
	for i in range(0,max_A):
		count_list.append(0)

	for a in A:
		for p in (list(set(prime_decomposition(a)))):
			count_list[p-1] +=1

	if (max(count_list) <=1 ):
		print("pairwise coprime")
	elif(gcd_list(A)==1):
		print("setwise coprime")
	else:
		print("not coprime")

	return

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
import queue
import collections
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

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

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


def main():
	N = i_input()
	A = i_list()

	tmpP = []
	P = []
	for a in A:
		for p in prime_decomposition(a):
			tmpP.append(p)
		P.extend(list(set(tmpP)))
		tmpP.clear()
	
	if(P.count == list(set(P)).count):
		print("pairwise coprime")
	elif(gcd_list(A) ==1):
		print("setwise coprime")
	else:
		print("not coprime")


	return

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
A = list(map(int, input().split()))
m = max(A)
c = [0] * (m+1)
for i in A:
  c[i] += 1

pairwise = True
for i in range(2,m+1,1):
  cnt = 0
  for j in range(i,m+1,i):
    cnt += c[j]
  if cnt > 1:
    pairwise = False
if pairwise:
  print("pairwise coprime")
  exit()

g = 0
for i in range(N):
  g = math.gcd(g,A[i])
if g == 1:
  print("setwise coprime")
  exit()
print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
def get_sieve_of_eratosthenes(n):
    table = [i if i % 2 else 2 for i in range(n + 1)]
    prime = [2]
    limit = int(n ** 0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return table, prime + data
        prime.append(p)
        next_data = []
        for e in data:
            if e % p != 0:
                next_data.append(e)
            else:
                table[e] = p
        data = next_data


N = int(input())
A = [int(i) for i in input().split()]
M = max(A)
if M > 2:
    table, primes = get_sieve_of_eratosthenes(M)
    Divisor = [0 for i in range(M + 1)]

    for a in A:
        aa = a
        while True:
            Divisor[table[aa]] += 1
            div = table[aa]
            while not aa % div:
                aa = aa // div
            if aa == 1:
                break

    Max_div = max(Divisor)
    #print(Max_div)
    if Max_div == 1:
        print("pairwise coprime")
    elif Max_div == N:
        print("not coprime")
    else:
        print("setwise coprime")

else:
    n = A.count(2)
    if n <= 1:
        print("pairwise coprime")
    elif n == N:
        print("not coprime")
    else:
        print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
ans1 = "pairwise coprime"
ans2 = "setwise coprime"
ans3 = "not coprime"

def func(number):
    factor = []
    div = 2
    s = math.sqrt(number)
    while div < s:
        div_cnt = 0
        while number % div == 0:
            div_cnt += 1
            number //= div
        if div_cnt != 0:
            factor.append(div)
        div += 1
    if number > 1:
        factor.append(number)
        
    return set(factor)

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

if a==1:
    b = True
    l = func(A[0])
    for i in range(1, N):
        
        if l&func(A[i])==set():
            l=l|func(A[i])
        else:
            b=False
            break
    if b:
        print(ans1)
    else:
        print(ans2)
        
        
    
else:
    print(ans3)