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 reduce

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

flag1,flag2=0,0
for i in range(N):
  f = set(primeFactor(A[i]).keys())
  if i == 0:
    set1,set2 = f,f
    continue
  l1,l2 = len(set1),len(set2)
  set1 = set1.intersection(f)
  set2 = set2.union(f)
  if len(set2) < l2+len(f):
    flag2 = 1
    
if len(set1)!=0:
  print('not coprime')
  exit()
    
if flag2:
  print('setwise coprime')
else:
  print('pairwise coprime')

Submission status: Time Limit Exceeded

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


import collections
import functools
from math import gcd


L = 10 ** 6 + 1


def sieve_of_eratosthenes(end):
    """Enumerates prime numbers below the given integer `end`.

    Returns (as a tuple):

    - `is_prime`: a list of bool values.
      If an integer `i` is a prime number, then `is_prime[i]` is True.
      Otherwise `is_prime[i]` is False.
    - `primes`: a list of prime numbers below `end`.
    """

    if end <= 1:
        raise ValueError("The integer `end` must be greater than one")
    is_prime = [True for _ in range(end)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for i in range(2, end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes


PRIMES = sieve_of_eratosthenes(L)


def factorize(n):
    factors = []
    if n < 2:
        return factors
    for p in PRIMES:
        if p * p > n:
            break
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        factors.append(n)
    return factors


def is_pairwise_coprime(bs):
    lcm_fs = dict()
    all_fs = collections.Counter()
    for b in bs:
        fs = collections.Counter(factorize(b))
        all_fs.update(fs)
        for k, v in fs.items():
            if k in lcm_fs:
                lcm_fs[k] = max(lcm_fs[k], v)
            else:
                lcm_fs[k] = v
    return lcm_fs == dict(all_fs)


def is_setwise_coprime(bs):
    return functools.reduce(gcd, bs) == 1


def main():
    n = int(input())
    bs = [int(b) for b in input().split()]
    if is_pairwise_coprime(bs):
        print("pairwise coprime")
    elif is_setwise_coprime(bs):
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

ok = True
for i in range(n):
    for j in range(i+1, n): 
        if 1 != math.gcd(a[i], a[j]):
            ok = False
            break
    if ok == False:
        break

if ok: 
    print('pairwise coprime')
    exit()

ans = math.gcd(a[0],a[1])
for i in range(2, n): 
   ans = math.gcd(ans, a[i])
if ans == 1:
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
A = [int(i) for i in input().split()]
flag =False
ans = math.gcd(A[0], A[1])
tmp = math.gcd(A[0], A[1])
maxa = (A[0] * A[1] // math.gcd(A[0], A[1]))
if tmp > 1:
    flag = True
for i in range(2, N):
    ans = math.gcd(ans, A[i])
    tmp = math.gcd(maxa, A[i])
    if tmp > 1:
        flag = True
    maxa = (maxa * A[i]) // tmp
if ans > 1:
    print('not coprime')
    exit()
if 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'
    st = set()
    for i in x:
        for j in pfact(i):
            if j not in st:
                st.add(j)
            else:
                ans = 'setwise coprime'
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
def primes(n):#nまでの素数を列挙0は入れちゃダメ
    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 is_prime
A = list(map(int,input().split()))
MAX = max(A)
prime = primes(MAX)
pri = [i for i in  range(2,MAX+1) if prime[i]]
n = len(pri)
cnt = defaultdict(int)
def factorization(n): #2以上の整数n => [[素因数, 指数], ...]の2次元リストを返す
    arr = []
    temp = n
    for i in pri:
        if i > int(n**0.5):
            break
        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
for i in range(N):
    a = A[i]
    li = factorization(a)
    for tu in li:
        b = tu[0]
        cnt[b] += 1
flag1 = 0
flag2 = 0
for i in pri:
    a = cnt[i]
    if a > 1:
        flag1 = 1
    if a == N:
        flag2 = 1
if flag1 == 0:
    print("pairwise coprime")
elif flag2 == 1:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

def lcm(x, y): return (x * y) // gcd(x, y)

N = INT()
A = LIST()

is_pc = 1
l = 1
for a in A:
    g = gcd(l, a)
    if g != 1:
        is_pc = 0
        break
    l = lcm(l, a)

is_sc = 1
g = 0
for a in A:
    g = gcd(g, a)
if g != 1:
    is_sc = 0

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

Submission status: Time Limit Exceeded

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

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

set_len_list = [0]*n
set_all = {1}
for i in range(n):
    set_i_tmp = set(prime_factor(a_list[i]))
    set_len_list[i] = len(set_i_tmp)
    set_all = set_all.union(set_i_tmp)
    if i == 0:
        set_int = set_i_tmp
    else:
        set_int = set_int.intersection(set_i_tmp)

if sum(set_len_list) == len(set_all)-1:
    print('pairwise coprime')
elif len(set_int) == 0:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math

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



n=int(input())

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

gcd=A[0]

for i in range(n-1):
  gcd=math.gcd(gcd,A[i+1])

nglis=[0 for i in range(10**6)]

if gcd!=1:
  print("not coprime")
else:
  check=0
  for i in range(n):
    if nglis[A[i]-1]==1:
      check=1
      break
    else:
      for pi in primelis(A[i]):
        j=1
        while pi*j<=10**6:
          nglis[pi*j-1]=1
          j+=1
  if check==1:
    print("setwise coprime")
  else:
    print("pairwise coprime")

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(range(2,n+1))
D=defaultdict(set)

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):
            if a in prime:
                prime_set.add(a)
                break
            while a % i == 0:
                prime_set.add(i)
                a //= i
                if a in prime:
                    flg=1
                    prime_set.add(a)
                    break
                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
    t_set|=prime_set
    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:
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:
        if mm[p[j]] and i!=p[j]:
          f=False
          break
        mm[p[j]]=1
        if mm[i//p[j]] and i//p[j]!=p[j] and i!=p[j]:
          f=False
          break
        mm[i//p[j]]=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:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

def make_divisors(n):
    res = []
    x = n
    y = 2
    while y*y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1:
        res.append(x)
    return res

n = ni()
a = na()

wa = set(make_divisors(a[0]))
s = len(wa)

for i in range(1,n):
    ii = set(make_divisors(a[i]))
    s += len(ii)
    wa = wa | ii
    if s != len(wa): # not pairwise
        break
else:
    print('pairwise coprime')
    exit()

import math
k = a[0]
for i in a:
    k = math.gcd(k,i)
    if k == 1:
        print('setwise coprime')
        exit()

print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

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

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

N = int(input())
A_list = list(map(int, input().split()))
A_list_min = sorted(A_list)

if gcd(*A_list) != 1:
    print("not coprime")
else:
    for i in range(len(A_list)):
        for j in range(i+1, len(A_list)):
            if gcd(A_list[i], A_list[j]) != 1:
                print("setwise coprime")
                exit()
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
pgcd = True
sgcd = a[n-1]

for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
    if sgcd==1:
        break
if sgcd!=1:
    print('not coprime')
else:
    for i in range(0,n-1):
        sgcd = math.gcd(sgcd, a[i])    
        for j in range(i+1,n):
            if math.gcd(a[i], a[j]) != 1:
                print('setwise coprime')
                break
        else:
            continue
        break
    else:
        print('pairwise coprime')

Submission status: Time Limit Exceeded

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


import collections
import functools

try:
    from math import gcd
except ImportError:
    from fractions import gcd


L = 10 ** 6 + 1


def sieve_of_eratosthenes(end):
    """Enumerates prime numbers below the given integer `end`.

    Returns (as a tuple):

    - `is_prime`: a list of bool values.
      If an integer `i` is a prime number, then `is_prime[i]` is True.
      Otherwise `is_prime[i]` is False.
    - `primes`: a list of prime numbers below `end`.
    """

    if end <= 1:
        raise ValueError("The integer `end` must be greater than one")
    is_prime = [True for _ in range(end)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for i in range(2, end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes


PRIMES = sieve_of_eratosthenes(L)


def factorize(n):
    factors = []
    if n < 2:
        return factors
    for p in PRIMES:
        if p * p > n:
            break
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        factors.append(n)
    return factors


def is_pairwise_coprime(bs):
    lcm_fs = dict()
    all_fs = collections.Counter()
    for b in bs:
        fs = collections.Counter(factorize(b))
        all_fs.update(fs)
        for k, v in fs.items():
            if k in lcm_fs:
                lcm_fs[k] = max(lcm_fs[k], v)
            else:
                lcm_fs[k] = v
    return lcm_fs == dict(all_fs)


def is_setwise_coprime(bs):
    return functools.reduce(gcd, bs) == 1


def main():
    n = int(input())
    bs = [int(b) for b in input().split()]
    if is_pairwise_coprime(bs):
        print("pairwise coprime")
    elif is_setwise_coprime(bs):
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
p=[1 for i in range(1001)]
p[0]=0
p[1]=0
for i in range(2,1001):
    if p[i]==1:
        for j in range(2,1001):
            if i*j<=1000:
                p[i*j]=0
#print(p[:25])
Prime=[]
for i in range(1001):
    if p[i]==1:
        Prime.append(i)
#print(Prime)
#print(len(Prime))
N=int(input())
L=list(map(int,input().split()))

def gcd(a,b):
    if b>a:
        a,b=b,a
    while a%b!=0:
        a,b=b,a%b
    return b
    
X=L[0]
for i in range(1,N):
    X=gcd(X,L[i])
    if X==1:
        break
if X>1:
    print("not coprime")
    exit()
        
D={}
for i in L:
    I=i
    for j in Prime:
        if I%j==0:
            if j not in D:
                D[j]=1
            else:
                print("setwise coprime")
                exit()
            while I%j==0:
                I//=j
    if I!=1:
        if I not in D:
            D[I]=1
        else:
            print("setwise coprime")
            exit()
#print(D)

print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
def main():
    from math import gcd
    MINFact = [-1] * (10**6 + 10)
    MINFact[0] = 0
    MINFact[1] = 1

    def Eratosthenes(sup: int) -> set:
        primes = [True for i in range(sup+1)]
        primes[0] = False
        primes[1] = False
        for i in range(2, sup+1):
            if sup < i*i:
                break
            if primes[i]:
                MINFact[i] = i
                mul = 2
                while i*mul <= sup:
                    primes[i*mul] = False
                    if MINFact[i*mul] == -1:
                        MINFact[i*mul] = i
                    mul += 1

    def prime_factor(n):
        while n != 1:
            prime = MINFact[n]
            while MINFact[n] == prime:
                n //= prime
            B[prime] += 1

    _ = int(input())
    A = [int(i) for i in input().split()]
    g = A[0]
    for a in A:
        g = gcd(g, a)
    Eratosthenes(10**6 + 5)
    B = [0]*(10**6 + 5)
    for a in A:
        prime_factor(a)
    # 素因数分解したのをBにいれる
    # 1より大きいのがあったら gcd != 1 のペアが存在する
    if g != 1:
        print("not coprime")
    elif max(B) <= 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd


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


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

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

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
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
if A==[1]*N:
  print('pairwise coprime')
  exit()
a=A[0]
d=a
if A[0]!=1:
  D={}
  x=0
  for i in range(N):
    if d!=1:
      d=math.gcd(d,A[i])
    c=A[i]
    if x==0:
      F=factorization(A[i])
      for a,b in F:
        if a not in D:
          D[a]=1
        else:
          x=1
        #互いに素じゃない二組がある  
    if x==1 and d==1:
      break

  if x==1 and d==1:
    print('setwise coprime')
  elif x==0 and d==1:
    print('pairwise coprime')
  else:
    print('not coprime')
else:
  D={}
  x=0
  for i in range(N):
    if A[i]!=1:
      F=factorization(A[i])
      for a,b in F:
        if a not in D:
          D[a]=1
        else:
          x=1
    
  if x==1:
    print('setwise coprime')
  else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
ans=['pairwise coprime','setwise coprime','not coprime']
k=0
s,g=A[-1],A[-1]
for i in range(2,N+1):
    g=math.gcd(g,A[-i])
    if math.gcd(s,A[-i])!=1:
        k=-1
    s*=A[-i]
if k==-1:
    if g==1:
        k=1
    else:
        k=2
print(ans[k])

Submission status: Time Limit Exceeded

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

def get_prime(m):
    global check_list
    global conf
    pf = {}
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1
    
    for i in pf.keys():
        if check_list[i] >= 1:
            conf = True
            check_list[i] += 1
        elif check_list[i] == 0:
            check_list[i] = 1

    return pf

def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(len(A)):
        get_prime(A[i])
    if max(check_list) == len(A):
        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:
N=int(input())
A=list(map(int,input().split()))

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.add(i)

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

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

    return arr

com={}
rem={}

for i in range(N):
  if i ==0:
    rem=factorization(A[i])
  else:
    rem=rem&factorization(A[i])

for i in range(N):
  if i ==0:
    com=factorization(A[i])
  else:
    if com&factorization(A[i])==set() or com&factorization(A[i])=={1}:
      com=com.union(factorization(A[i]))
    else:
      com={0}
      break
    
if com!={0}:
  print("pairwise coprime")
elif rem==set() or rem=={1}:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

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

import itertools
import math

ans_list = []
not_pair = False
for combi in itertools.combinations(A, 2):
    ans = math.gcd(combi[0], combi[1])
    if ans != 1:
        ans_list.append(ans)
        not_pair = True

if not not_pair:
    print("pairwise coprime")
else:
    ans = ans_list[0]
    not_set = False
    for i in range(1, N):
        ans = math.gcd(ans, ans_list[i])
        if ans != 1:
            print("not coprime")
            not_set = True
            break
    if not not_set:
        print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
MAX= 10**6

from math import gcd, sqrt
g = A[0]
# g_list = [A[0]]
for i in range(1, N):
    g = gcd(g, A[i])
    # g_list.append(g)
if g != 1:
    print("not coprime")
    exit()
else:
    def makePrimeChecker(n):
        """
        エラトステネスの篩.
        nまでの自然数が素数かどうかを表すリストを返す.
        """
        isPrime = [True] * (n + 1)
        isPrime[0] = False
        isPrime[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if isPrime[i]:
                for j in range(i * i, n + 1, i):
                    isPrime[j] = False
        return isPrime

    is_prime = makePrimeChecker(MAX)
    used_prime = [0]*(MAX+1)
    primes = [n for n in range(2, MAX+1) if is_prime[n]]

    # def factorization(n, used_prime):
    #     arr = []
    #     temp = n
    #     is_ok = 1
    #     for i in range(2, int(-(-n**0.5//1))+1):
    #         if temp%i==0:
    #             cnt=0
    #             if used_prime[i]:
    #                 is_ok = 0
    #                 break
    #             while temp%i==0:
    #                 cnt+=1
    #                 temp //= i
    #             arr.append([i, cnt])
    #             used_prime[i] = 1

    #     if is_prime[temp]:
    #         if used_prime[temp]:
    #             is_ok = 0
    #         # arr.append([temp, 1])
    #         used_prime[temp] = 1


    #     if is_prime[n]:
    #         # arr.append([n, 1])
    #         if used_prime[n]:
    #             is_ok = 0
    #         used_prime[n] = 1
    #     return is_ok, used_prime

    # def divisor(num):
    #     max_num = int(sqrt(num))
    #     divisor_list = []
    #     for i in range(1, max_num + 1):
    #         if num % i == 0:
    #             divisor_list.append(i)
    #             divisor_list.append(num//i)
        
    #     return divisor_list

    
    is_ok = 1
    for p in primes:
        for a in A:
            if a % p == 0:
                if used_prime[p]:
                    is_ok = 0
                    break
                used_prime[p] = 1
        if not is_ok:
            break
    if is_ok:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd 
n = int(input())
A = list(map(int,input().split()))
g = A[0]
mul = A[0]
pflag = True
for i in range(n-1):
  if pflag:
    if gcd(mul,A[i+1]) != 1:
      pflag = False 
    mul *= A[i+1]
  g = gcd(g,A[i+1])
if g != 1:
  print("not coprime")
else:
  if pflag:
    print("pairwise coprime")
  else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

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

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)

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

    return arr

N=int(input())
A=list(map(int, input().split()))
S=set(factorization(A[0]))
T=set(factorization(A[0]))
flg=0
for i in range(1,N):
    k=A[i]
    prime=set(factorization(k))
    if T&prime!=set():
        flg=1
    S=S&prime
    T=T|prime
    #print(S,T)
if S!=set():
    print('not coprime')
elif flg==1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
import itertools
from functools import reduce

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

n = int(input())
a = list(map(int, input().split()))
res = 1
for x in itertools.combinations(a, 2):
    res = max(res, gcd(x[0], x[1]))
    if res > 1:
        break
if res == 1:
    print('pairwise coprime')
elif gcd_list(a) == 1:
    print('setwise coprime')
else:
    print('not coprime')