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
import sys
import random

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

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

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(int(-(-1000//1))+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
random.shuffle(a)
g = a[0]
arr = factorization(a[0])
used = set()
for i in arr:
    if i == 1: continue
    used.add(i)

pair = True
for i in range(n-1):
    g = gcd(g, a[i+1])
    # 一度でも互いに素でない組合せが出たらpariwise coprimeではない
    if pair:
        arr = set(factorization(a[i+1]))
        arr -= {1}
        if used&arr:
            pair = False
        else:
            used |= arr
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
import collections
def main():

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

    d = dict()
    def prime_factor(n):
        if n % 2 == 0: d[2] = d.get(2, 0) + 1
        while n % 2 == 0:
            n //= 2

        for i in range(3, int(math.sqrt(n))+1, 2):
            if n % i == 0:
                d[i] = d.get(i, 0) + 1
            while n % i == 0:
                n //= i
        if n > 1:
            d[n] = d.get(n, 0) + 1
        return

    ispair = True
    isset = True

    d = dict()
    for v in A: prime_factor(v)
    # print(d)

    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"

    return "not coprime"

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

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getList()

pair = True
semi = True
# not divisible
# 全部互いに素かどうか
judge = [0] * (10 ** 6 + 1)
num_list = [0] * (10 ** 6 + 1)

for i in A:
    judge[i] += 1

for i in range(2, 10 ** 6 + 1):
    if num_list[i] == 1:
        continue
    cnt = 0
    for j in range(i, 10 ** 6 + 1, i):
        num_list[j] = 1
        cnt += judge[j]
    if cnt > 1:
        pair = False
        break
if pair:
    print('pairwise coprime')
    exit()

now = A[0]
for i in A[1:]:
    now = gcd(now, i)
if now > 1:
    semi = False

if semi:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())

l = list(map(int,input().split()))
ans = 1

for i in l:
    ans*=i
f=0
for i in range(n):
    x = ans//l[i]
    if math.gcd(x,l[i])!=1:
        f = 1
        break
    
if f==0:
    print('pairwise coprime')
    exit()

x = l[-1]

for i in range(n):
    x = math.gcd(x,l[i])

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

Submission status: Time Limit Exceeded

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

from collections import Counter

class Osa_k:
    def __init__(self, n):
        self.n = n
        self.min_factor = [int(x) for x in range(n+1)]
        
        self.is_prime = [True] * (self.n + 1)
        self.is_prime[0] = False
        self.is_prime[1] = False
        for j in range(4, self.n+1, 2):
            self.is_prime[j] = False
            self.min_factor[j] = 2
        for i in range(3, int(self.n**0.5) + 1, 2):
            if not self.is_prime[i]:
                continue
            for j in range(i * 2, self.n + 1, i):
                self.is_prime[j] = False
                if self.min_factor[j] >= i:
                    self.min_factor[j] = i
    
    def calulate(self, x):
        ans = []
        while x > 1:
            key = self.min_factor[x]
            while x%key == 0:
                ans.append(key)
                x //= key
        counter = set(ans)
        return counter
        

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    key = a[0]
    sc = False
    for i in range(1, n):
        key = math.gcd(key, a[i])
    
    if key == 1:
        sc = True
    
    
    pc = True
    osak = Osa_k(10**6+1)
    
    sub = set()
    
    judge = dict()
    for i in range(n):
        key = osak.calulate(a[i])
        for v in key:
            if v in judge:
                pc = False
            judge[v] = 1
            
    
    if pc:
        print("pairwise coprime")
    elif sc:
        print("setwise coprime")
    else:
        print("not coprime")

    
    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
def main():

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


    def prime_factor(n):
        ans = []
        if n % 2 == 0: ans.append(2)
        while n % 2 == 0:
            n //= 2

        for i in range(3, int(math.sqrt(n))+1, 2):
            if n % i == 0:
                ans.append(i)
            while n % i == 0:
                n //= i
        if n > 1:
            ans.append(n)
        return ans

    ispair = True
    isset = True

    d = dict()
    for v in A:
        for u in prime_factor(v):
            d[u] = d.get(u, 0) + 1
    # print(d)

    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"

    return "not coprime"

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

Submission status: Time Limit Exceeded

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

from math import gcd

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

    sv = [i for i in range(10**6+1)]
    for i in range(2 ,int(N**0.5)+1) :
        if sv[i] < i : continue
        for j in range(i * i , N , i) :
            sv[j] = min(sv[j] , i)

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

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


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

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

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

    A.sort()
    d = A[0]

    for i in A:
        d = gcd(i,d)
        if d == 1 or d > 10**2:
            break

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

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
def factors(x):
    f = []
    i = 2
    while i <= int(x**.5+1):
        while x%i==0:
            f.append(i)  
            x //= i
        i += 1
    if x > 1:
        f.append(x)
    return set(f)

import math
gcd_list = []
g = a[0]
for j in a[1:]:
    g = math.gcd(g,j)


flg=0
z = factors(a[0])
for i in a[1:]:
    zz = factors(i)
    if not(z & zz):
        z |= zz
    else:
        flg=1
        break

if not flg:
    print('pairwise coprime')
    exit()

if g == 1:
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Time Limit Exceeded

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

def gcd(p,q):
# Create the gcd of two positive integers.
    while q != 0:
        p, q = q, p%q
    return p

def is_coprime(x, y):
    return gcd(x, y) == 1


N = int(input())
A = list(map(int,input().split()))
flag = False
cnt = 0
GCDArr = A[0]
for i in range(N):
    for j in range(i+1,N):
        if is_coprime(A[i],A[j]) == True:
            flag = True
        else:
            flag = False
if flag == True:
    print("pairwise coprime")
else:
    for i in range(N):
        GCDArr = gcd(GCDArr,A[i])
    if GCDArr == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import copy
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
  
def main():
  n = int(input())
  arr = list(map(int, input().split()))
  prime = primes(10**6)
  pf = isPair(prime, arr)
  sf = isSet(prime, arr)
  

  if pf and sf:
    print('pairwise coprime')
    exit()
  if not sf:
    print('not coprime')
    exit()
  else:
    print('setwise coprime')
    exit()

def isPair(prime, arr):
  searched = []
  for p in prime:
    for a in arr:
      if a % p == 0:
        if p in searched:
          return False
        searched += [p]
  return True

def isSet(prime, arr):
  searched = []
  for p in prime:
    if arr[0] % p == 0:
      searched.append(p)
      
  for a in arr[1:]:
    if len(searched) == 0:
      return True
    tmp = []
    for s in searched:
      if a % s == 0:
        tmp.append(s)
        
    searched = tmp
  if len(searched) == 0:
      return True
  return False
  
  
main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
#N = 1000000
A = list(map(int, input().split()))
#A = [i+1 for i in range(1000000)]
p = {2*i+1: 1 for i in range(1, 500)}
for i in range(3, 1000, 2):
  for j in p:
    if j != i:
      if j % i == 0:
        p[j] = 0
L = [2]
for i in p:
  if p[i] == 1:
    L.append(i)
def gcd(x, y):
  k, l = x, y
  while l:
    k, l = l, k % l
  return k
g = A[0]
for i in range(1, N):
  g = gcd(g, A[i])
  if g == 1:
    break
if g > 1:
  print("not coprime")
else:
  D = {}
  for i in range(N):
    pnt = 0
    while A[i] != 1:
      cnt = 0
      while A[i] % L[pnt] == 0:
        cnt = 1
        A[i] //= L[pnt]
      if cnt:
        if L[pnt] in D:
          D[L[pnt]] += 1
        else:
          D[L[pnt]] = 1
      pnt += 1
      if pnt == len(L) and A[i] != 1:
        if A[i] in D:
          D[A[i]] += 1
        else:
          D[A[i]] = 1
        break
  if D == {}:
    print("pairwise coprime")
  else:
    if max(D[i] for i in D) > 1:
      print("setwise coprime")
    else:
      print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
E  = 1000000
B = [0]*(E+1)

seek = [False]*(E + 1)
sosu = [[] for _ in range(E+1)]

for n in range(2, E + 1):
    num = 1
    while (n * num) < E+1:
        if seek[n * num] == False:
            seek[n * num] = True
        sosu[n * num].append(n)
        num += 1
#print(sosu)

for a in A:
    for num in sosu[a]:
        B[num] += 1

#print(B)

f1 = False
f2 = False

for b in B:
    if b >= 2:
        f1 = True
    if b == N:
        f2 = True

if f1 == True and f2 == False:
    print('setwise coprime')
elif f1 == False:
    print('pairwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    S = 1
    for x in A:
        S *= x
    start = time.time()

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

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

        if len(ret) == 0 and n != 1:
            ret.add(n)

        return ret

    flag = True
    s = factorization(A[0])
    for x in A[1:]:
        tmp = 0
        now = time.time()
        if now - start > 1.8:
            exit(1)
            break
        for y in s:
            if x % y == 0:
                flag = False
                break
        if flag:
            s |= factorization(x)
            continue
        else:
            break

    if flag:
        print("pairwise coprime")
    else:
        g = A[0]
        for i, x in enumerate(A[::-1]):
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()

Submission status: Time Limit Exceeded

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

#互いに素　互除法 a=bq+r
def gcd(a,b):
    r=1
    while r>0:
        q,r= a // b, a % b
        a, b = b, r
    return(a)
#n個のgcd
def gcdn(A):
    min=gcd(A[0],A[1])
    for i in range(2,len(A)):
        min=gcd(min,A[i])
    return(min)

max = 0
for i in range(N-1):
    for j in range(i,N-1):
        if max < gcd(A[i], A[i + 1]):
            max = gcd(A[i], A[i + 1])

if max == 1:  # 全てのペアが互いに素
    print("pairwise coprime")
elif gcdn(A)==1: #全ての最大公約数が1
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math

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

pairwise_flag = True
total_set = set()
common_set = set()
i_max = max(a)
num_list = [i for i in range(2, i_max + 1)]
prime_list = set(num_list)
for i in num_list:
    if i in prime_list:
        tmp = i + i
        while tmp < i_max:
            tmp += i
            prime_list.discard(tmp)

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

for i in range(n):
    tmp = a[i]
    tmp_list = []
    for j in prime_list:
        if tmp < j:
            break
        if tmp % j == 0:
            while tmp % j == 0:
                tmp //= j
            tmp_list.append(j)
    for j in tmp_list:
        prime_list.discard(j)
    if tmp != 1:
        pairwise_flag = False
        break

if pairwise_flag:
    print("pairwise coprime")
elif total_gcd > 1:
    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()))

def get_prime(n):
  res = [1]*(n+1)
  x = 2
  for i in range(2,x):
    if res[i]:
      for j in range(i*2,n+1,i):
        res[j] = 0
  return [i for i in range(2,n+1) if res[i]]

prime_list = {x:0 for x in get_prime(10**6+1)}
def check(n):
  for p in prime_list.keys():
    if n < p:
      break
    if n % p==0:
      if prime_list[p]:
        return 0
      else:
        prime_list[p] = 1
  return 1

allwise = 1
if len([x for x in a if x > 1]) > len(prime_list.keys()):
  allwise = 0
else:
  allwise = check(a[0])
setwise = a[0]

for ai in a[1:]:
  if allwise:
    allwise = check(ai)
  setwise = math.gcd(setwise,ai)
  #print(ai,allwise,setwise)
if allwise:
  print('pairwise coprime')
elif setwise == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import *
def gcds(a):
    tmp = a[0]
    for i in range(1,len(a)):
        tmp = gcd(tmp,a[i])
    return tmp

multiplied_a = [1]
n = int(input())
a = list(map(int,input().split()))
for i in a:
    multiplied_a.append(multiplied_a[-1]*i)
Flag = True
for i in range(n-1):
    other = multiplied_a[-1] // multiplied_a[i+1] 
    #print(a[i],other,gcd(a[i],other))
    if gcd(a[i],other) != 1:
        Flag = False
        break
if Flag:
    print('pairwise coprime')
    exit()
if gcds(a) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

import math

def erastosthenes(N):
    number_list = [i for i in range(N+1)]
    is_p_list = [True]*(N+1)

    is_p_list[0] = False
    is_p_list[1] = False

    for i in range(2, math.ceil(math.sqrt(N+1))):
        if is_p_list[i]:
            for j in range(2, (N//i)+1):
                is_p_list[i*j] = False
    return [number for number in number_list if is_p_list[number]]

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

    p_list = erastosthenes(1000000)

    min_counter = N# 1回目の提出では0と書き間違えていた。
    for p in p_list:
        counter = 0
        for A in A_lsit:
            if A%p != 0:
                counter += 1
        min_counter = min(min_counter, counter)
    
    if min_counter >= N-1:
        print("pairwise coprime")
    elif min_counter >= 1:
        print("setwise coprime")
    else:
        print("not coprime")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math


def gcd_muti(A):
    ans = A[0]
    for i in range(1, len(A)):
        ans = math.gcd(ans, A[i])
        if ans == 1:
            return ans
    return ans


def gcd_every(A):
    s = set()
    fucs = list(map(factorization, A))
    for fuc in fucs:
        for radix, _ in fuc:
            if radix in s:
                return False
            s.add(radix)
    return True


def factorization(n):
    arr = []
    if n == 1:
        return 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

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

all_gcd = gcd_muti(A) == 1
every_gcd = gcd_every(A)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def primeNumberCreate():
    primeList = [2]  # 2以下の素数リストを作成
    maxNumber = 10 ** 6  # 1000以下の数字をチェック
    for x in range(3, maxNumber):
        for y in primeList:
            if x % y == 0:
                break
        else:
            primeList.append(x)  # 割り切れるものがなければリストに追加
    return primeList


prime_tuple = primeNumberCreate()
prime_num = 78498
n = int(input())
exp_array = np.zeros((n, prime_num), dtype="int")
for i, a in enumerate(map(int, input().split())):
    for p_i in range(prime_num):
        if a == 1:
            break
        p = prime_tuple[p_i]
        while a % p == 0:
            a //= p
            exp_array[i][p_i] += 1

max_exp = exp_array.max(axis=0)
min_exp = exp_array.min(axis=0)
sum_exp = exp_array.sum(axis=0)
# print(exp_array)
# print(sum_exp)
# print(min_exp)
# print(max_exp)
if np.all(np.equal(sum_exp, max_exp)):
    print("pairwise coprime")
elif np.all(np.equal(min_exp, 0)):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
N = int( input() )
A = sorted( list(map(int, input().split())))
ans = A[0]
L = []
mod = 10 ** 7 + 9

cnt = 0
for i in range(1, N):
    ans = math.gcd(ans, A[i])
    if ans == 1:
      break
    else:
      cnt += 1
if ans != 1:
  ret = "not coprime"
else:
  if cnt > 0:
    ret = "setwise coprime"
  else:
    product = 1
    for a in A:
      product = ( product * a )
    ret = "pairwise coprime"
    for a in A:
      ans = math.gcd(a, product // a)
      if ans != 1:
        ret = "setwise coprime"
        break
print( ret )

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil, gcd
from bisect import bisect_left
import random
from itertools import combinations, accumulate
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def generate_primes(n):
    primes = []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, n + 1):
        if is_prime[p]:
            primes.append(p)
            for i in range(p, n + 1, p):
                is_prime[i] = False
    return primes

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

    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

def solve1(N, A):
    primes = generate_primes(max(A) + 1)
    elems = defaultdict(list)
    ct = Counter()

    for p in primes:
        for i, Ai in enumerate(A):
            if Ai % p == 0:
                ct[p] += 1

    flag = True
    for key in ct:
        if ct[key] > 1:
            flag = False
            break

    # 共通gcd
    prod = A[0]
    for k in range(1, N):
        prod = gcd(prod, A[k])
    flag2 = prod == 1

    if flag:
        print("pairwise coprime")
    elif flag2:
        print("setwise coprime")
    else:
        print("not coprime")

def main():
    from builtins import int, map
    N = int(input())
    A = list(map(int, input().split()))
    solve1(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    S = 1
    for x in A:
        S *= x
    start = time.time()

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

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

        if len(ret) == 0 and n != 1:
            ret.add(n)

        return ret

    flag = True
    s = factorization(A[0])
    for x in A[1:]:
        tmp = 0
        now = time.time()
        if now - start > 1:
            break
        for y in s:
            if x % y == 0:
                flag = False
                break
        if flag:
            s |= factorization(x)
            continue
        else:
            break

    if flag:
        print("pairwise coprime")
    else:
        g = A[0]
        for i, x in enumerate(A[::-1]):
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
import sys
 
n = int(input())
a = list(map(int, input().split(' ')))
 
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
if gcd_list(a) != 1:
  print('not coprime')
  sys.exit()
 
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 math
import sys
import random

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

input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
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(int(-(-1000//1))+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
random.shuffle(a)
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ではない
    if pair:
        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:
def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    S = 1
    for x in A:
        S *= x
    start = time.time()

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

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

        if len(ret) == 0 and n != 1:
            ret.add(n)

        return ret

    flag = True
    s = factorization(A[0])
    for x in A[1:]:
        tmp = 0
        now = time.time()
        if now - start > 1.5:
            break
        for y in s:
            if x % y == 0:
                flag = False
                break
        if flag:
            s |= factorization(x)
            continue
        else:
            break

    if flag:
        print("pairwise coprime")
    else:
        g = A[0]
        for i, x in enumerate(A[::-1]):
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

from math import gcd
g = a[0]
for i in range(n):
    g = gcd(g,a[i])

if g!=1:
    print('not coprime')
    exit()


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

f = True
l = set()
for i in range(n):
    x = prime_factorize(a[i])
    y = l|x
    if len(l)+len(x)!=len(y):
        f = False
        break
    l = y
    
if f:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
from math import gcd
prime = [0] * 2 + [1] * (10 ** 6 - 1)
A = list(map(int, input().split()))
A.sort()
g = 0
for a in A:
  g = gcd(g, a)
for i in range(2, 10 ** 2 + 1):
  if prime[i]:
    for j in range(2 * i, 10 ** 3 + 1, i):
      prime[j] = 0
P = [i for i in range(2, 10 ** 3 + 1) if prime[i]]
from bisect import bisect
A = A[bisect(A, 1):]
N = len(A)
x = [0] * (10 ** 6 + 1)
for a in A:
  for p in P:
    if a % p == 0:
      x[p] += 1
      while a % p == 0:
        a //= p
    if a == 1:
      break
  if a > 1:
    x[a] += 1
if max(x) < 2:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
  
else:
  print('not coprime')