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:
from functools import lru_cache


@lru_cache(maxsize=None)
def PrimeFactorization(n):
    l=[]
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            l.append(i)
            n //= i
            while n % i == 0:
                n //= i
    if n > 1:
        l.append(n)
    return l


def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    pairwise = True
    d = {}
    for i in a[:-1]:
        for j in PrimeFactorization(i):
            if j in d:
                d[j] += 1
                if pairwise:
                    pairwise = False
            else:
                d[j] = 1
    for j in PrimeFactorization(a[-1]):
        if j in d:
            if d[j] == n - 1:
                print("not coprime")
                return
            if pairwise:
                pairwise = False
    if pairwise:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p


# error_print(len(P))

@mt
def slv(N, A):
    d = Counter()
    P = eratosthenes(10**6+1)
    P = set(P)

    for a in A:
        f = True
        u = set()
        for p in P:
            if a % p == 0:
                if p in d:
                    break
                d[p] = 1
                u.add(p)
            while a % p == 0:
                a //= p
            if a == 1:
                break
        else:
            f = False

        if a != 1:
            break
        P -= u
        # print(a, u)
    else:
        return 'pairwise coprime'

    g = 0
    for a in A:
        g = math.gcd(a, g)
    return 'setwise coprime' if g == 1 else 'not coprime'


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # P = eratosthenes(10**6+1)
    # N = len(P)
    # A = P[:]
    # error_print(N)
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p

P = eratosthenes(10**6+1)
# error_print(len(P))

@mt
def slv(N, A):
    d = Counter()

    for a in A:
        f = True
        for p in P:
            if a % p == 0:
                if p in d:
                    break
                d[p] = 1
            while a % p == 0:
                a //= p
            if a == 1:
                break
        else:
            f = False
        if f and a != 1:
            break
    else:
        return 'pairwise coprime'

    g = 0
    for a in A:
        g = math.gcd(a, g)
    return 'setwise coprime' if g == 1 else 'not coprime'


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


    # N = 10**6
    # A = [random.randint(1, 10**6) for _ in range(N)]
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p

P = eratosthenes(10**6+1)
# error_print(len(P))

@mt
def slv(N, A):
    def f(a):

        return d

    d = Counter()

    for a in A:
        f = True
        for p in P:
            if a % p == 0:
                if p in d:
                    break
                d[p] = 1
        else:
            f = False
        if f:
            break
    else:
        return 'pairwise coprime'

    g = 0
    for a in A:
        g = math.gcd(a, g)
    return 'setwise coprime' if g == 1 else 'not coprime'


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p

P = eratosthenes(10**6+1)
error_print(len(P))

@mt
def slv(N, A):
    def f(a):
        d = Counter()
        for p in P:
            if a % p == 0:
                d[p] = 1
            # while a % p == 0:
            #     a //= p
            # if a == 1:
            #     break
        return d

    dc = Counter()
    g = 0
    for a in A:
        dc += f(a)
        g = math.gcd(a, g)

    for v in dc.values():
        if v != 1:
            break
    else:
        return 'pairwise coprime'

    return 'setwise coprime' if g == 1 else 'not coprime'


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p

P = eratosthenes(10**6+1)

@mt
def slv(N, A):
    def f(a):
        d = Counter()
        for p in P:
            if a % p == 0:
                d[p] = 1
            while a % p == 0:
                a //= p
            if a == 1:
                break
        return d

    dc = Counter()
    g = 0
    for a in A:
        dc += f(a)
        g = math.gcd(a, g)

    for v in dc.values():
        if v != 1:
            break
    else:
        return 'pairwise coprime'

    return 'setwise coprime' if g == 1 else 'not coprime'


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
X = [0] * 1000000

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

for a in A:
    m = int(math.sqrt(a))
    for i in range(2, m + 1):
        if a % i == 0:
            X[i] += 1
        while a % i == 0:
            a /= i
    a = int(a)
    if a != 1:
        X[a] += 1

ans = 'pairwise coprime'
for x in X:
    if x == N:
        print('not coprime')
        exit()
    if x > 1:
        ans = 'setwise coprime'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True
c2 = True

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

hoge = 0
for i in num_lis:
  hoge = gcd(hoge, i)
if hoge > 1:
  print("not coprime")
  exit()

d_lis = osa_k(10**6+10)
tmp = set()
for i in num_lis:
  num = i
  new_tmp = set()
  while num > 1:
    d = d_lis[num]
    new_tmp.add(d)
    num //= d
  if len(tmp | new_tmp) != len(tmp)+len(new_tmp):
    print("setwise coprime")
    exit()
  else:
    tmp |= new_tmp
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True
c2 = True

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

hoge = 0
for i in num_lis:
  hoge = gcd(hoge, i)
if hoge > 1:
  print("not coprime")
  exit()

d_lis = osa_k(max(num_lis))
tmp = set()
for i in num_lis:
  num = i
  new_tmp = set()
  while num > 1:
    d = d_lis[num]
    new_tmp.add(d)
    num //= d
  if len(tmp | new_tmp) != len(tmp)+len(new_tmp):
    print("setwise coprime")
    exit()
  else:
    tmp |= new_tmp
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
 
def gcd_lis(lis):
    return reduce(math.gcd, lis)

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True
c2 = True

d_lis = osa_k(max(num_lis))
tmp = set()
for i in num_lis:
  num = i
  new_tmp = set()
  while num > 1:
    d = d_lis[num]
    new_tmp.add(d)
    num //= d
  #print(new_tmp)
  if len(tmp)+len(new_tmp) == len(tmp | new_tmp):
    tmp |= new_tmp
    continue
  else:
    c1 = False
    break
  
if gcd_lis(num_lis) != 1:
  c2 = False

if c1:
  print("pairwise coprime")
elif not c1 and c2:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

from math import gcd

def solve():
    N = II()
    A = LI()
    
    mx = 1000003
    D = [1] * mx
    for i in range(2, len(D)):
        # if D[i] != 1:
        #     continue
        for j in range(i, len(D), i):
            if D[j] == 1:
                D[j] = i
    # print(D[mx-3])
    # print(D[4], D[6], D[35])

    g = A[0]
    dct = defaultdict(int)
    flag = True
    for a in A:
        g = gcd(g, a)
        # print(a, D[a])
        # if D[a] != 1:
        #     if dct[D[a]] > 0:
        #         flag = False
        #     dct[D[a]] += 1
        d = D[a]
        p = a
        # 最小の素数を求める
        while p != d:
            p = p // d
            d = D[p]

        if p != 1:
            dct[p] += 1
            if dct[p] > 1:
                flag = False

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


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
if True:
    import math
    import fractions


    def make_prime_and_deleted_by_list(n):
        prime_list = [i for i in range(2, n+1)]
        deleted_by_list = [i for i in range(n+1)]
        pi = 0
        target_prime = prime_list[pi]
        while(target_prime < math.sqrt(n)):
            old_prime_list = prime_list.copy()
            prime_list = prime_list[:pi+1]
            for i in old_prime_list:
                if i % target_prime == 0:
                    deleted_by_list[i] = target_prime
                else:
                    if i > prime_list[pi]:
                        prime_list.append(i)
            pi += 1
            target_prime = prime_list[pi]
        return prime_list, deleted_by_list

    def make_factor_list(n, deleted_by_list, factor_list):
        if n == 1:
            return factor_list
        else:
            factor = deleted_by_list[n]
            factor_list.append(factor)
            return make_factor_list(int(n/factor), deleted_by_list, factor_list)

    def calc_gcd(As):
        ans = As[0]
        for i in range(1, len(As)):
            ans = fractions.gcd(ans, As[i])
        return ans
            
    N = int(input())
    As = list(map(int, input().split()))
    if As == [1 for i in range(N)]:
        print("pairwise coprime")
    else:
        _, d = make_prime_and_deleted_by_list(max(As))

        As_factor_list = []
        for A in As:
            As_factor_list.extend(set(make_factor_list(A, d, [])))

        if len(set(As_factor_list)) == len(As_factor_list):
            print("pairwise coprime")

        else:
            if calc_gcd(As) == 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 primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

primes=primes(int(1000))
points=[0]*1000001

from math import gcd
pairprime_flag=True
allgcd=A[0]
allprime=set()

for a in A:
    allgcd=gcd(allgcd,a)
    for i in primes:
        if a%i==0:
            if points[i]==1:
                pairprime_flag=False
            points[i]=1
            while a%i==0:
                a//=i
        if a==1:
            break
    if a!=1:
        if points[a]!=0:
            pairprime_flag=False
        else:
            points[a]=1

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

Submission status: Time Limit Exceeded

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

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

pairprime_flag=True
allgcd=A[0]
product=1

for a in A:
    allgcd=gcd(allgcd,a)
    if gcd(product,a)!=1:
        pairprime_flag=False
    product=lcm(product,a)
if pairprime_flag:
    print('pairwise coprime')
elif allgcd==1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
'''
なんで通らないのかわからん
Xの値もしかして間違ってた？
多分TLE
'''


import sys
import math

X = 1000000

prime = []

for i in range(2,X+1):
    det = 0
    for j in range(2,int(i**(1/2))+1):
        if i%j==0:
            det = -1
            break
    if det == 0:
        prime.append(i)

#print(prime)
#print(len(prime))

N = int(input())
A = list(map(int,input().split()))
B = []###Aのうち1ではないもの
det = False###Aが1を含んでいたか否か

for i in range(N):
    if A[i] == 1:
        det = True
    else:
        B.append(A[i])

#print(det)
#print(B)

if len(B) <= len(prime):

    m = 1

    for p in prime:
        count = 0
        for b in B:
            if b%p==0:
                count += 1
        m = max(m,count)
        #print(p,count,m)
        if m >= 2:
            break
    
    if m == 1:
        print('pairwise coprime')
        sys.exit(0)

if det:
    print('setwise coprime')

else:
    g = A[0]
    for i in range(1,N):
        g = math.gcd(g,A[i])
    if g == 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

N = INT()
A = LIST()

if reduce(gcd, A) != 1:
    print("not coprime")
    exit()
ma = max(A)
p = list(range(ma+1))

for x in range(2, int(ma ** 0.5) + 1):
    if p[x]:
        # xは素数，それがpの要素にあるうちは続ける
        for i in range(2 * x, ma + 1, x):
            p[i] = x

s = [set() for _ in range(N)]
t = set()

for i, x in enumerate(A):
    while x != 1:
        s[i].add(x)
        t.add(x)
        # 割り続けるとs[i]にその素数がたまっていく
        x //= p[x]
l = sum(len(x) for x in s)
print("pairwise coprime" if l == len(t) else "setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce
# from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))

if reduce(gcd,a)!=1:
  print("not coprime")
  exit()

def primes(x):
  ret=[]
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      ret.append(i)
      if x//i!=i:
        ret.append(x//i)
  ret.sort()
  return ret[1:]
      
s=set()
for q in a:
  p=primes(q)
  for j in p:
    if j in s:
      print("setwise coprime")
      exit()
    s.add(j)
print("pairwise coprime")

Submission status: Time Limit Exceeded

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

g=reduce(gcd,a)
if g!=1:
  print("not coprime")
  exit()

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

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
d=defaultdict(int)
for q in a:
  p=primeFactor(q)
  for j in p:
    d[j]+=1

for _,di in d.items():
  if di>=2:
    print("setwise coprime")
    exit()
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
def Ii():return int(sys.stdin.readline().rstrip())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))
n = Ii()
a = Li()
sc = 0
g = math.gcd(a[0],a[1])
for i in range(n-2):
  g = math.gcd(g,a[i+2])
  if(g == 1):
    sc = 1
    break
if(sc == 0):
  print('not coprime')
  exit(0)

b = 1
for i in range(n-1):
  b *= a[i]
  g = math.gcd(b%a[i+1],a[i+1])
  if(g > 1):
    print('setwise coprime')
    exit(0)    
  
print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
def Ii():return int(sys.stdin.readline().rstrip())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))
n = Ii()
a = Li()
sc = 0
pc = 1
for i in range(n-1):
  b = 1
  for j in range(i):
    b *= a[j]
    b %= a[i+1]
    
  g = math.gcd(b,a[i+1])
  if(g > 1):
    pc = 0
    break
    
g = math.gcd(a[0],a[1])
for i in range(n-2):
  g = math.gcd(g,a[i+2])
  if(g == 1):
    sc = 1
    break

if(pc):
  ans = 'pairwise coprime'
elif(sc):
  ans = 'setwise coprime'
else:
  ans = 'not coprime'
  
print(ans)

Submission status: Time Limit Exceeded

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

number_list = [0]*1000010
for a in A:
    number_list[a] += 1
    
flag1 = True
flag2 = True

for i in range(2,1000001):
    count = 0
    for j in range(1,1000001):
        if i*j > 1000000:
            break
        tmp = i*j
        count += number_list[tmp]
    if count > 1:
        flag1 = False
    if count == N:
        flag2 = False
        
if flag2 == False and flag1 == False:
    print("not coprime")
elif flag2 == True and flag1 == False:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math,sys

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


ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n=int(math.sqrt(10**6))+1
count=[0 for _ in range(max_n)]

def fac(x,T):
    i=2
    while x>1:
        ind=0
        while x%i == 0:
            ind+=1
            x=int(x/i)
        if ind>0:
            if i in T:
                return False
            else:
                T.append(i)
        i+=1
    return True

flag=True
for each in Ns:
    flag_2=fac(each,count)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
    sys.exit()

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

if gcd_ans==1:
    print(ans_s)
else:
    print(ans_n)

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
l=list(map(int,input().split()))
su=1
for values in l:
    su=su*values
lcm=1
gcc=l[0]
for values in l:
    gc=math.gcd(lcm,values)
    gcc=math.gcd(gcc,values)
    lcm=(lcm*values)//gc;
# print(gcc)
# print(lcm)
# print(su)
if lcm==su and gcc==1:
    print("pairwise coprime")
elif lcm!=su and gcc==1:
    print("setwise coprime")
else:
    print("not coprime")