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 sympy
#import random

def get_ans():
    N = int(input())
    A_list = [int(e) for e in input().split()]

    #テスト用乱数生成
    
    #N = 10**6
    #A_list = [random.randrange(1,10**6) for _ in range(N)]

    #約数を列挙
    def make_divisors(n):
        lower_divisors , upper_divisors = [], []
        i = 1
        while i*i <= n:
            if n % i == 0:
                lower_divisors.append(i)
                if i != n // i:
                    upper_divisors.append(n//i)
            i += 1
        return lower_divisors + upper_divisors[::-1]
        
    divisors_dict = dict()

    for A in set(A_list):
        divisors_dict[A] = set(make_divisors(A))

    all_divisors = set()
    common_divisors = set()
    common_divisors |= divisors_dict[A_list[0]]
    all_divisors |= divisors_dict[A_list[0]]
    is_pairwise = True

    for i in range(1,len(A_list)):
        A_divisors = divisors_dict[A_list[i]]
        common_divisors &= A_divisors 
        
        if is_pairwise and len(all_divisors&A_divisors)!=1:
            is_pairwise = False
        else:
            all_divisors |= A_divisors
        
    #約数を全部積み重ねて、共通のものが1以外に全くなかったらpaiwise
    #全部に含まれる約数が、1以外になければ、setwise

    if is_pairwise:
        print("pairwise coprime")
    elif len(common_divisors) == 1:
        print("setwise coprime")
    else:
        print("not coprime")

get_ans()

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(n-1):
  for j in range(i+1, n):
    ans.append(math.gcd(a[i], a[j]))
if len(set(ans)) and 1 in set(ans):
  print('pairwise coprime')
  exit()
ans = a[0]
for i in range(1, n):
  ans = math.gcd(ans, a[i])
if ans == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
l=list(map(int,input().split()))
num=math.gcd(l[0],l[1])
for i in l:
    num=math.gcd(num,i)
if num!=1:
    print('not coprime')
else:
    ll=set(l)
    n=len(ll)
    if n>=8*10**4:
        print('setwise coprime')
    else:
        flag=True
        ll=list(ll)
        for i in range(n-1):
            for j in range(i+1,n):
                if math.gcd(ll[i],ll[j])!=1:
                    flag=False
                    break
        if flag==True:
            print('pairwise coprime')
        else:
            print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()
used = [0] * (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(-(-10**3//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

a.sort(reverse=True)
g = a[0]
arr = factorization(a[0])
for i in arr:
    used[i] += 1

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

Submission status: Time Limit Exceeded

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

import math
from functools import reduce

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

def sieve_of_eratosthenes(n): 
    candidate = [i for i in range(2, n+1)] 
    prime = []
    limit = math.sqrt(n) + 1 

    while True:
        p = min(candidate) 
        if limit <= p:
            prime.extend(candidate) 
            break
        prime.append(p) 

        candidate = [i for i in candidate if i % p != 0]

    return prime

prime = sieve_of_eratosthenes(2*(10**5)+1)

for p in prime:
  cnt = 0
  for a in A:
    if a%p == 0: cnt += 1
    if cnt == 2:
      if gcd_list(A) == 1: print('setwise coprime')
      else: print('not coprime')
      exit()
print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from math import gcd

import numpy as np


def solve(inp):
    n = inp[0]
    aaa = inp[1:]

    one_count = (aaa == 1).sum()
    aaa = np.unique(aaa)

    g = 0
    for i in range(len(aaa)):
        g = gcd(g, aaa[i])
    if g != 1:
        return -1

    if max(0, one_count - 1) + len(aaa) != n:
        return 0

    PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
              107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
              227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347,
              349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
              467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
              613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
              751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883,
              887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997)

    for p in PRIMES:
        multiple_count = 0
        inc_1 = 0
        for i in range(len(aaa)):
            if aaa[i] % p == 0:
                multiple_count += 1
                aaa[i] //= p
                while aaa[i] % p == 0:
                    aaa[i] //= p
                if aaa[i] == 1:
                    inc_1 += 1

        if multiple_count > 1:
            return 0

        if multiple_count == 1:
            one_count += inc_1
            aaa = np.unique(aaa)

            if max(0, one_count - 1) + len(aaa) != n:
                return 0

    return 1


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(['setwise coprime', 'pairwise coprime', 'not coprime'][ans])

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = sorted(LIST())

m = int(sqrt(a[-1]))
primes = set(range(2, m+1))
for i in range(2, int(m**0.5+1)):
    primes.difference_update(range(i*2, m+1, i))
primes=list(primes)

for i in range(n):
    for x in primes:
        y = x * x
        if y > a[i]:
            break
        else:
            while a[i] % y == 0:
                a[i] //= x

k = 1
flag = 1
for i in range(1, n):
    k *= a[i-1]
    if gcd(k, a[i]) > 1:
        flag = 0
        break

if flag == 1:
    print("pairwise coprime")
    exit()
else:
    g = a[0]
    for i in range(1, n):
        g = gcd(g, a[i])
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:



import math
#素数列挙
def get_primes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        A = [i for i in A if i%prime!=0]

    P.extend(A)
          
    return P


def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    sosus = set(get_primes(max(A)+1))
    dvd = set()



    val = A[0]
    for i in A:
        val = math.gcd(i,val)

    if val ==1:
        pass
    else:
        print('not coprime')
        return

    for i in A:
        tmp=[]
        for j in sosus:
            if j>i:
                break
            if i % j ==0:
                tmp.append(j)
                while i % j ==0:
                    i //=j
            if i ==1:
                break
        sosus.difference_update(tmp)
        
        if i != 1:
            break
    else:
        print('pairwise coprime')
        return

    print('setwise coprime')

resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    import math
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int,input().rstrip().split(" ")))
    M = int(math.sqrt(max(A))) + 1
    sosuu = set()
    sosuu.add(2)
    for i in range(3,M,2):
        for j in sosuu:
            if i % j == 0:
                break
        else:
            sosuu.add(i)
    
    pair = True
    setw = True
    counter = 0
    lis = [0] * (10 ** 6 + 1)
    for q in range(len(A)):
        i = A[q]
        for j in sosuu:
            if i % j == 0:
                while i % j == 0:
                    i = i // j
                lis[j] += 1
            
        if i != 1:
            lis[i] += 1
            if lis[i] == 2:
                pair = False
                
    for i in lis:
        if i == N:
            setw = False
        if i >= 2:
            pair = False
        if not setw and not pair:
            break

    if pair:
        print("pairwise coprime")
    elif setw:
        print("setwise coprime")
    else:
        print("not coprime")

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def soinsubunkai2(n,m):
    a = []
    i = 1
    for i in m:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def main():
    #l,r,d=map(int,input().split())
    n=int(input())
    a=list(map(int,input().split()))
    sosu=[]
    ccc=get_sieve_of_eratosthenes(int(math.sqrt(n)+10))
    memo = defaultdict(int)
    for i in range(n):
        if a[i]!=1:
            temp=set(soinsubunkai2(a[i],ccc))
        else:
            temp={}
        for j in temp:
            memo[j]+=1

    memo.pop(1,None)
 #   print(sosu)
 #   print(memo)
 #   print(memo.values())
    if len(memo)>=1:
        mmm=max(memo.values())
    else:
        mmm=1
    if mmm<=1:
        print("pairwise coprime")
    elif mmm<n:
        print("setwise coprime")
    else:
        print("not coprime")








if __name__ == "__main__":

    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import gcd
input=sys.stdin.buffer.readline
#sys.setrecursionlimit(10**6)

def Ed(num,ycnt):
    for i in range(1,int(num**0.5)+1):
        if num%i==0:
            ycnt[i]+=1
            if num//i!=i:
                ycnt[num//i]+=1

def main():
    input()
    a=[int(i) for i in input().split()]

    N=10**6+1
    ycnt=[0]*N
    gsum=a[0]

    for i in a:
        gsum=gcd(gsum,i)
        Ed(i,ycnt)
    
    for i in range(2,N):
        if ycnt[i]>=2:break
    else:
        print("pairwise coprime")
        exit()
    if gsum==1:
        print("setwise coprime")
    else:print("not coprime")

if __name__=="__main__":main()

Submission status: Time Limit Exceeded

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

# def
def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

def str_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

def int_map():
    return map(int,input().split())

def int_list():
    return list(map(int,input().split()))

def print_space(l):
    return print(" ".join([str(x) for x in l]))

# import
import numpy as np
import collections as col

import math
from functools import reduce

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

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

# main code
N = int(input())
A = int_list()

AA = [x for x in A if not x == 1]

AA2 = [x for x in AA if x%2 == 0]

b = gcd(*A)

s = set()

if not b == 1:
    print("not coprime")
else:
    if len(AA2) > 1:
        print("setwise coprime")
        exit()

    num = 0
    for aa in AA:
        v = factorization(aa)
        vnum = len(v)
        num += vnum
        for i in range(0,vnum):
            s.add(v[i][0])
        
        if not num == len(s):
            print("setwise coprime")
            exit()
    
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from sys import *
input=stdin.readline
from math import *
n=int(input())
l=list(map(int,input().split()))
l.sort()
g=l[0]
for i in range(1,n):
    g=gcd(g,l[i])
if(g!=1):
    print("not coprime")
else:
    f=0
    p=l[0]
    c=0
    for i in l:
        if(i%2==0):
            c+=1
    if(c>=2):
        f=1
    for i in range(1,n):
        if(gcd(p,l[i])!=1):
            f=1
            break
        p*=l[i]
    if(f==1):
        print('setwise coprime')
    else:
        print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections

N = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

from math import gcd

pairwise = True
setwise = True
acc = a[0]
for i in range(N):
    acc = gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

for i in range(N):
    for j in range(i+1,N):
        b = gcd(a[i],a[j])
        if b != 1:
            print("setwise coprime")
            exit()
if pairwise == True:
    print("pairwise coprime")
# elif setwise == True:
#     print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a 
def multiple_gcd(a):
    ans = a[0]
    for i in range(1, len(a)):
        ans = gcd(ans, a[i])
    return ans

def pairwise_coprime():
    for i in range(N-1):
        for j in range(i+1, N):
            if gcd(A[i], A[j]) != 1:
                return 0
    return 1

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

if pairwise_coprime() == 1:
    print('pairwise coprime')
elif multiple_gcd(A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
def PrimeFactorization(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            yield i
            n //= i
            while n % i == 0:
                n //= i
    if n > 1:
        yield n


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:
import sys
input = sys.stdin.readline

import math
from functools import reduce

count = int(input())

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

def gcd_p(n):
  an = list(map(int, input().split()))
  num = 1
  for i in range(n - 1):
    for j in range(i+1, n):
      if math.gcd(an[i], an[j]) != 1:
        num *= 0
  if num == 1:
    print("pairwise coprime")
  else:
    if gcd_s(an) == 1:
      print("setwise coprime")
    else:
      print("not coprime")
      
gcd_p(count)

Submission status: Time Limit Exceeded

Solution code:
import math


def get_sieve_of_eratosthenes(n):
    if n < 2:
        return []
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


def solve():
    N = int(input())
    A_L = [int(x) for x in input().split()]
    A_L.sort()
    A_L = tuple(A_L)

    f_l = get_sieve_of_eratosthenes(A_L[-2])

    flag = False
    for f in f_l:
        _len = len([e for e in A_L if e % f == 0])
        if _len == N:
            print("not coprime")
            exit(0)
        elif _len > 1:
            flag = True
    if flag:
        print("setwise coprime")
    else:
        print("pairwise coprime")


solve()

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
s = [0]*(10**6+1)
t = [0]*169
u = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
     101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
     211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
     307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
     401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
     503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
     601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
     701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
     809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
     907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]
v = 0
m = 169
for i in range(n):
    for j in range(m):
        if(a[i]%u[j] == 0):
            t[j] += 1
            while(a[i]%u[j] == 0):
                a[i] //= u[j]
            if(a[i] == 1):
                break
    if(a[i] != 1):
        s[a[i]] += 1
        v += 1
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    z = 0
    if(v > 0):
        if(max(s) <= 1):
            print('pairwise coprime')
        else:
            print('setwise coprime')    
    else:
        print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:

import math
import numpy
import functools
import operator

n=int(input())
a = list(map(int, input().split()))
pair_check=[]
ans1 = a[0]
for i in range(1, n):
    ans1 = ans1 * a[i] // math.gcd(ans1, a[i])
    #N個の最小公倍数

ans = a[0]
pair_check_check=0
for i in range(1, n):
    ans = math.gcd(ans, a[i])
    #N個の最大公約数

result = functools.reduce(operator.mul, a)

if result==ans1:
    print("pairwise coprime")

elif ans==1:
    print("setwise coprime")
    exit()
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
A=list(range(2,10**3+1))
p=list()
while A[0]**2<=10**3+1:
	tmp=A[0]
	p.append(tmp)
	A=[e for e in A if e%tmp!=0]
primes = p+A

N = int(input())
L = list(map(int, input().split()))
R = True
for p in primes:
  c = 0
  for i in range(N):
    if L[i]%p==0:
      c += 1
      while L[i]%p==0:
        L[i] //= p
  if c==N:
    print("not coprime")
    exit()
  if c>1:
    R = False
L = [l for l in L if l>1]
if len(L)>1:
  L.sort()
  if L[0]==L[-1]:
    print("not coprime")
    exit()
  for i in range(len(L)-1):
    if L[i]==L[i+1]:
      R = False
      break
print("pairwise coprime" if R else "setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
import copy

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


dp=[0 for _ in range(1000000+1)]

sosuu = [2]
A = 1000
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.append(L)
        
V=0  

VV=0
if V>1000:
  VV+=1
  

else:
  ch1=0
  ch3=0
  for w in sosuu:
    ch2=0
    for q in range(n):
      if B[q]%w==0:
        ch2+=1
        S=B[q]
        while S%w==0:
          S=S//w
        B[q]=S
    if ch2>1:
      ch3+=1
  d={}
  ch4=0
  for u in B:
      if u>1000:
        if u not in d:
          d[u]=0
        else:
          ch4+=1
  if ch3==0 and ch4==0:
    print('pairwise coprime')
    
      
  
  
    
  else:
    g=a[0]
    for h in range(1,n):
      g=math.gcd(g,a[h])
    
    if g==1:
      print('setwise coprime')
    
    else:
      print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n, ela):
    if n == 1:
        return {1: 1}

    prime_dict = {}
    for i in ela:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def 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 not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela = [i for i, b in enumerate(ela) if b]

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


    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    for a in A:
        if a == 1:
            continue

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    elif max_p == N:
        print("not coprime")
    else:
        print("setwise coprime")



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

counts = [0 for _ in range(max(A)+1)]
for a in A:
  counts[a] += 1

integers = [1 for _ in range(max(A)+1)]
integers[0] = 0
integers[1] = 0
max_count = 0
for i in range(max(A)+1):
  if integers[i] >= 1:
    count = 0
    for j in range(i,max(A)+1,i):
      count += counts[j]
      integers[j] = 0
    max_count = max(max_count,count)

if max_count == N:
  answer = 'not coprime'
elif max_count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)

Submission status: Time Limit Exceeded

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

def mult_gcd(arr):
    return reduce(gcd, arr)

def main(N, A):
    for c in combinations(A, r = 2):
        if gcd(*c) != 1:
            break
    else:
        print('pairwise coprime')
        exit()

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

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    main(N, A)

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 pf[i] == 1:
                if check_list[i] >= 1:
                    conf = True
                    check_list[i] += 1
                elif check_list[i] == 0:
                    check_list[i] = 1
    if m>1:
        pf[m]=1
        if check_list[m] >= 1:
            conf = True
            check_list[m] += 1
        elif check_list[m] == 0:
            check_list[m] = 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())