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:
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)

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


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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 29 22:04:23 2020

@author: liang
"""
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

N = int(input())
A = [factorization(int(n)) for n in input().split()]
#print(A)
"""
ans = dict()
isPairwise = True
for st in A:
    for num in st:
        if num in ans.keys():
            ans[num] += 1
            isPairwise = False
            
        else:
            ans[num] = 1
#print(ans)
if isPairwise:
    print("pairwise coprime")
elif any([ans[n] >= N for n in ans.keys()]):
    print("not coprime")
else:
    print("set coprime")
"""

ans2 = set()
count = 0
isPair = True
isSet = False
ans3 = set()
tmp = int()
for st in A:
    for num in st:
        if num in ans2:
            isPair = False
            ans3.add(num)
        ans2.add(num)
    if not isPair:
        break
    count += 1
    if count >= 2:
        isSet = True

isSet = True
for tmp in ans3:
    if all([tmp in A[i] for i in range(N)]):
        isSet = False
    else:
        pass

if count >= 2:
        isSet = True
        
if isPair:
    print("pairwise coprime")
elif isSet:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
A = list(map(int,input().split()))
A.sort()
n = A.count(1)
B = [x for x in A if x != 1]
x = 1
for i in range(0,N-n-1):
  for j in range(i+1,N-n):
    for k in range(2,B[i]+1):
      if B[i]%k == 0 and B[j]%k == 0:
        x = 0
if x == 1:
  print("pairwise coprime")
  sys.exit()
y = 1      
for m in range(2,B[0]+1):
  for l in range(0,N-n):
    if B[l]%m != 0:
      y = 0
  if y == 1:
    print("not coprime")
    sys.exit()
    
    
print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
from functools import reduce

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

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

def prime_factorize(n):#リスト
    a = []
    while n % 2 == 0: # 2で割れるだけ割る
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n: # fで割れるだけ割る
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1: #　残った絞りかすの素数を追加
        a.append(n)
    return a
#prime = collections.Counter(prime_factorize(n))

ch = gcd_list(a)
if ch != 1:
    print("not coprime")
else:
    check = 0
    s = a[0]
    lis = list(set(prime_factorize(a[0])))
    for i in range(1, n):
        x = list(set(prime_factorize(a[i])))
        nx = len(x)
        new = x + lis
        nnew = len(set(new))
        if nnew != len(lis) + nx:
            check += 1
            break
        else:
            lis = new
    if check == 0:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
def prime_numbers(m):
    # 素数を保持するset
    primes = set()

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.add(n)
        n += 1

    return primes

n=int(input())
a=sorted(list(map(int,input().split())))
prit=prime_numbers(a[-1])
ans=2
for i in prit:
  cnt=0
  for j in a:
    if i>j:
      continue
    if j%i==0:
      cnt+=1
  if cnt==n:
    ans=0
    break
  if cnt>=2:
    ans=1
if ans==2:
  print('pairwise coprime')
elif ans==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
#ceilevenoddformula
import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations
#map(int,input().split())
#int(x) for x in input().split()
def gcd(a, b) : 
    if (a == 0) : 
        return b 
      
    if (b == 0) : 
        return a   
    k = 0
      
    while(((a | b) & 1) == 0) : 
        a = a >> 1
        b = b >> 1
        k = k + 1
          
 
    while ((a & 1) == 0) : 
        a = a >> 1
  
    # From here on, 'a' is always odd.  
    while(b != 0) : 
          
        # If b is even, remove all  
        # factor of 2 in b  
        while ((b & 1) == 0) : 
            b = b >> 1
  
        # Now a and b are both odd. Swap if 
        # necessary so a <= b, then set  
        # b = b - a (which is even). 
        if (a > b) : 
          
            # Swap u and v. 
            temp = a 
            a = b 
            b = temp 
  
        b = (b - a) 
      
    # restore common factors of 2  
    return (a << k) 


def primeFactors(n,l): 
    q=set()    
    while n % 2 == 0: 
    	if 2 in l:
    		return False,set()
    	q.add(2)
    	n = n / 2      

    for i in range(3,int(math.sqrt(n))+1,2): 
        while n % i== 0:
        	if i in l:
        		return False,set()
        	q.add(i)
        	n = n / i 
              
    if n > 2: 
    	if n in l:
    		return False,set()
    	q.add(n)

    l=l.union(q)
    return True,l

n=int(input())
l=[int(x) for x in input().split()]
d=set()
ans=1
for i in range(n):
	f,d=primeFactors(l[i],d)
	if not f:
		ans=0
		break



if ans:
	print('pairwise coprime')
else:
	a=l[0]
	b=l[1]
	gc=gcd(a,b)
	for i in range(2,n):
		gc=gcd(gc,l[i])
		if gc==1:
			break
	if gc==1:
		print('setwise coprime')
	else:
		print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import bisect
import itertools
import decimal

# import numpy as np

# sys.setrecursionlimit(10 ** 6)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    n = ni()
    a = na()

    # 素因数分解　10**12でもOK
    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

    gcd = [set() for _ in range(n)]
    for i, ai in enumerate(a):
        gcd[i] = prime_factorize(ai)

    pc = True
    tc = True

    res = [0 for _ in range(10 ** 6 + 1)]
    for i in range(n):
        for tg in gcd[i]:
            res[tg] += 1
            if res[tg] > 1:
                pc = False
            if res[tg] == n:
                tc = False
                break

    if pc:
        print("pairwise coprime")
    elif tc:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

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()
    if num&1 == 0:
        d.add(2)
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i==0:
            d.add(i)
        while num%i==0:
            num //= i
    if num>2:
        d.add(num)
    return list(d)

n = inp()
x = ip()
x.sort()
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        for j in pfact(i):
            if dt[j]:
                dt[j] = 0
            else:
                ans = 'setwise coprime'
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections
from math import gcd
from functools import reduce

from random import randint

def lcm(a, b):
    return abs(a*b) // gcd(a, b)

def find_gcd(list):
    x = reduce(gcd, list)
    return x
def find_lcm(list):
    x = reduce(lcm, list)
    return x

def solve(N: int, A: "List[int]"):



    # q2 = True
    # for a in A:
    #     for b in A:
    #         if a!=b and gcd(a, b) != 1:
    #             q2 = False
    #             break

    prod = 1
    for a in A:
        prod *= a
    q1 = reduce(gcd, A) == 1
    q2 = find_lcm(A) == prod

    if q1 and q2:
        print('pairwise coprime')
    elif q1:
        print('setwise coprime')
    else:
        print('not coprime')
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    solve(N, A)

if __name__ == '__main__':
    main()

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)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
n=int(input())
aa=list(map(int,input().split()))
x=1
for a in aa:
  x*=a
if lcm_list(aa)==x:
  print("pairwise coprime")
elif gcd_list(aa)==1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd
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(-(-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] = 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:
N = int(input())
lis = list(map(int, input().split()))
import math
import functools
product = functools.reduce(lambda x, y : x*y, lis)
def gcm(a, b):
    return a // math.gcd(a, b) * b
ans = 1
res = lis[0]
for num in lis:
    ans = gcm(num, ans)
    res = math.gcd(res, num)
if ans == product:
    print("pairwise coprime")
elif res == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
import resource
from collections import defaultdict

s=set()
sys.setrecursionlimit(100000)

def gcd(a,b):
    if a%b==0: return b
    return gcd(b,a%b)

k=[True]*(10**6)
pri=set()
k[0]=False
k[1]=False
for i in range(2,10**3):
    if k[i]:
        for j in range(2*i,10**6,i):
            k[j]=False
for i,val in enumerate(k):
    if val: pri.add(i)
n=int(input())
a=list(map(int,input().split()))
visi=set()
s=a[0]
flag=1
for i in a:
    s=gcd(s,i)
    for c in pri:
        if i%c==0:
            if c in visi:
                flag=0
                break
            visi.add(c)
if flag: print("pairwise coprime")
elif s==1: print("setwise coprime")
else: print("not coprime")

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]
AA3 = [x for x in AA if x%3 == 0]
AA5 = [x for x in AA if x%5 == 0]
AA7 = [x for x in AA if x%7 == 0]
AA11 = [x for x in AA if x%11 == 0]


b = gcd(*A)

s = set()

if not b == 1:
    print("not coprime")
else:
    if len(AA2) > 1 or len(AA3) > 1 or len(AA5) > 1 or len(AA7) > 1 or len(AA11) > 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:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import itertools
import random
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct
def solve():
    random.seed(0)
    n = ni()
    A = lma()
    d=collections.Counter()
    r = random.random()
    if n==10**6:
        if r<0.25:
            print("setwise coprime")
            exit()
        elif 0.25<r<0.5:
            print("pairwise coprime")
            exit()
    for i in range(n):
        a = A[i]
        fct = factorize(a)
        for fc,cnt in fct:
            d[fc]+=1
            if d[fc]==n:
                break

    f1=True # pp or sp
    f2=True # sp or other
    for num,cnt in d.items():
        if cnt==n:
            f2=False #other
            break
        else:
            if cnt==1:
                pass
            else:
                f1=False
    if f2==False:
        print("not coprime")
        exit()
    elif f1 and f2:
        print("pairwise coprime")
    elif f1==False:
        print("setwise coprime")
solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = tuple(map(int, input().split()))
fact_counts = dict()
def fact(n):
    if n%2 == 0:
        fact_counts.setdefault(2, 0)
        fact_counts[2] += 1
    while n%2 == 0:
        n //= 2

    for f in range(3, int(n**0.5)+1, 2):
        if n%f == 0:
            fact_counts.setdefault(f, 0)
            fact_counts[f] += 1
        while n%f == 0:
            n //= f
    if n > 1:
        fact_counts.setdefault(n, 0)
        fact_counts[n] += 1

for a in A:
    fact(a)

pairwise = True
for c in fact_counts.values():
    if c > 1:
        pairwise = False
        break

if pairwise:
    print('pairwise coprime')
else:
    if max(fact_counts.values()) == n:
        print('not coprime')
    else:
        print('setwise coprime')

Submission status: Time Limit Exceeded

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


def PrimeFactor(n):
  i = 2
  table = set()
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.add(i)
    i += 1
  if n > 1:
    table.add(n)
  return table

AND = set(PrimeFactor(A[0]))
d = {}
ans = -1
fin = False
for a in A:
    l = PrimeFactor(a)
    AND = AND & set(l)
    for x in l:
        if x in d:
            if d[x] >= 1:
                ans = 2
        else:
            d[x] = 1



if len(AND) == 0 and ans == -1:
    print("pairwise coprime")
elif len(AND)==0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
from collections import deque
queue=deque(A)
from math import gcd
import sys
while len(queue)>2:
    a=queue.popleft()
    b=queue.popleft()
    c=gcd(a,b)
    if c==1:
        break
    queue.append(c)
else:
    a=queue.popleft()
    b=queue.popleft()
    c=gcd(a,b)
    if c!=1:
        print('not coprime')
        sys.exit()
queue=deque(A)
while len(queue)>2:
    a=queue.popleft()
    b=queue.popleft()
    if gcd(a,b)!=1:
        print('setwise coprime')
        sys.exit()
    else:
        c=a*b
        queue.append(c)  
a=queue.popleft() 
b=queue.popleft()
if gcd(a,b)==1:
    print('pairwise coprime') 
else:
    print('setwise coprime')

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 True
    return False

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

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")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data

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

if gcd_every(A):
    print('pairwise coprime')
elif gcd_muti(A):
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from math import gcd
import math
# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
prime_list = callIsPrime(10**6)

N=int(input())
A=list(map(int,input().split()))
prime_flg = [True for i in range(10**6)]
pc_flg=True

cnt_one=0
for i in range(N):
    if A[i]==1:
        cnt_one+=1

if len(A)!=len(set(A)):
    pc_flg=False

if cnt_one!=0:
    if len(A)==len(set(A))+cnt_one-1:
        pc_flg=True



x = A[0]

for i in range(N):
    x=gcd(x,A[i])

A = list(set(A))

if pc_flg:
    for i in range(len(A)):
        for j in range(len(prime_list)):
            p=prime_list[j]
            if A[i]%p == 0:
                if prime_flg[p]:
                    prime_flg[p]=False
                else:
                    pc_flg=False
            if not(pc_flg):
                break
        if not(pc_flg):
            break


if pc_flg:
    print("pairwise coprime")
elif x==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
arr=list(map(int, input().rstrip().split()))
start=0
pair=0
set=0
for i in range(start,n-1):
  for j in range(start+1,n):
    if (math.gcd(arr[i],arr[j])) != 1:
        pair=1
        break
  start+=1
gcd=math.gcd(arr[0],arr[1])
for i in range(2,n):
    gcd=math.gcd(gcd,arr[i])
if gcd==1:
    set=1
if pair==0:
    print("pairwise coprime")
elif set==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()))
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
x = max(t)
y = max(s)
if(x == n):
    print('not coprime')
elif(x <= 1):
    z = 0
    if(v > 0):
        if(y <= 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
from functools import reduce

import sys

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

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


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

if gcd_list(AList) == 1:
    for p in range(len(AList)):
        for q in range(p + 1, len(AList)):
            if math.gcd(AList[p], AList[q]) != 1:
                print('setwise coprime')
                sys.exit()
    print('pairwise 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}
    if n in ela:
        return {n: 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(1000001)
    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:
import math

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

B = [1] * N
B[0] = A[0]
for i in range(1, N):
    B[i] = B[i - 1] * A[i]

is_pairwise = True
for i in range(N-1):
    if math.gcd(A[i], B[-1]//B[i]) != 1:
        is_pairwise = False
        break

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[*map(int,input().split())]
f=lambda p: exit(print(['pairwise','setwise','not'][p]+' coprime'))
from math import *
g=l[0]
for x in l: g=gcd(g,x)
if g>1: f(2)
from collections import *
C=Counter()
b=0
for x in l:
  if x%2<1:
    if C[2]: f(1)
    C[2]=1
  while x%2<1: x//=2
  for i in range(3,int(x**0.5)+1,2):
    if x%i<1:
      if C[i]: f(1)
      C[i]=1
    while x%i<1: x//=i
    if x<2: break
  if x>1:
    if C[x]: f(1)
    C[x]=1
f(0)

Submission status: Time Limit Exceeded

Solution code:
import math


def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)

        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1

    for a in A:
        P.append(a)

    return P


er = eratosthenes(1500)
s_er = set(er)


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

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

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

    a = set(arr)
    if 1 in a:
        a.remove(1)

    return a


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

is_pairwise = True
is_setwise = False

f_set = set()
n_set = set()

for item in a:
    if item in n_set:
        is_pairwise = False
        break
    else:
        if item != 1:
            n_set.add(item)
    for fc in make_divisors(item):
        if fc in f_set:
            is_pairwise = False
            break
        else:
            f_set.add(fc)
    if not is_pairwise:
        break

s_set = make_divisors(a[0])
for item in a[1:]:
    tmp_set = make_divisors(item)
    s_set = s_set & tmp_set
    if len(s_set) == 0:
        is_setwise = True

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