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 sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
input=sys.stdin.readline
from random import randint
##import numpy as np
##sys.setrecursionlimit(10**7)
mo=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input()) 
def lcm(a,b): 
    return (a*b) // math.gcd(a,b) 
for _ in range(1):
    n=inin()
    l=ain()
    f1,f2=0,0
    gc=lc=l[0]
    for i in range(1,n):
        gc=math.gcd(gc,l[i])
        if(math.gcd(l[i],lc)!=1):
            f1=1
        lc=lcm(lc,l[i])
    if(gc!=1):print("not coprime")
    else:
        if(f1):
            print("setwise coprime")
        else:
            print("pairwise coprime")
        
        
    
    
    

 
    
    
    
    
        
        
    
    
    
    


    




##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

pc = True
gg = False
cnt = Counter()

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

for a in factorization(A[0]):
    if a > 1:
        cnt[a] = 1

for i in range(1, N):
    for a in factorization(A[i]):
        if cnt[a] >= 1:
            pc = False
        if a > 1:
            cnt[a] += 1

if pc:
    print("pairwise coprime")
elif cnt.most_common(1)[0][1] < N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from functools import reduce

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from operator import mul
from functools import reduce
N = int(input())
*A, = map(int, input().split())

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

if reduce(lcm, A) == reduce(mul, A):
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print("setwise coprime")
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
arr = raw_input()  
v = list(map(int,arr.split(' ')))
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)
def lcm(x,y):
    p=x*y
    return p/gcd(x,y)
    
l=v[0]
g=v[0]
p=v[0]
for i in range(1,len(v)):
    l=lcm(l,v[i])
    g=gcd(g,v[i])
    p*=v[i]
if p==l:
    print "pairwise coprime"
elif g==1:
    print "setwise coprime"
else:
    print "not coprime"

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a = inpl()
ans = "pairwise coprime"
FLAG = [False] * 10**6
for i in range(2, 10**6):
    if FLAG[i]:
        continue
    coprime = 0
    for j in range(n):
        if a[j] % i == 0:
            coprime += 1
        elif a[j] % i != 0 and coprime >= 2:
            break
    if coprime == n:
        ans = "not coprime"
        break
    elif coprime >= 2:
        ans = "setwise coprime"
    for k in range(2, 10**6):
        if i * k >= 10**6:
            break
        FLAG[i * k] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
n = int(input())
A = [int(i) for i in input().split()]

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

first_prod = A[0]
first_lcm = A[0]
for i in range(1, n):
    first_prod *= A[i]
    first_lcm = lcm(first_lcm, A[i])
    if first_prod != first_lcm:
        break #not pairwise
else:
    print("pairwise coprime")
    exit()

first_gcd = A[0]
for i in range(1, n):
    first_gcd = gcd(first_gcd, A[i])
if first_gcd == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = [int(_) for _ in input().split()]
p = [1] * (n + 1)
for i in range(n - 1, -1, -1):
    p[i] = p[i + 1] * a[i]
pc = True
for i in range(n - 1):
    pc = pc & (math.gcd(p[i + 1], a[i]) == 1);
if pc:
    print("pairwise coprime")
    exit(0)
x = 0
for y in a:
    x = math.gcd(x, y)
if x == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

def function(n):
    memo = set()
    r = int((n+1)**0.5)
    for i in p:
        if n % i == 0:
            c = 0
            while n % i == 0:
                c += 1
                n //= i
            memo.add(i)
    if n > 1:
        memo.add(n)
    return memo

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


total = set()
cnt = 0
seki = set(p)
for a in A:
    s = function(a)
    total = total | s
    seki = seki & s
    cnt += len(s)
# print(total)

if seki == set():  # 全部に共通する素因数はない
    if len(total) != cnt:  # どこかに共通あり
        print("setwise coprime")
    else:
        print("pairwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math 
from functools import reduce

def read():
    N = int(input()) 
    As = list(map(int, input().split(' ')))
    return N, As


def func(N, As):
    for i in range(N):
        ai = As[i]
        for j in range(i+1, N):
            aj = As[j]
            if math.gcd(ai, aj) != 1:
                if reduce(math.gcd, As) == 1:
                    print('setwise coprime')
                else:
                    print('not coprime')
                return
    print('pairwise coprime')
    return


if __name__ == '__main__':
    N, As = read()
    func(N, As)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
import math

input = sys.stdin.readline


# 素因数分解O(√n)

def primeFactor(n):
    res = defaultdict(lambda: 0)
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res[i] += 1
            n = n // i
    if n != 1:
        res[n] = 1
    return res


def main():
    N = int(input())
    A = list(map(int, input().split()))
    primes = defaultdict(lambda: 0)
    for i in range(N):
        pf = primeFactor(A[i])
        for k in pf.keys():
            primes[k] += 1
    pairs = True
    setp = True
    for k in primes.keys():
        if primes[k] != 1:
            pairs = False
        if primes[k] == N:
            setp = False
            break
    if pairs:
        print('pairwise coprime')
    elif setp:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

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

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]
used = [False] * len(primes)
big = set()

g = A[0]
for v in A:
    g = gcd(v,g)
if g == 1:  
    works = True
    for v in A:
        for i in range(len(primes)):
            if v % primes[i] == 0:
                if used[i]:
                    works = False
                    break
                used[i] = True
                while v % primes[i] == 0:
                    v //= primes[i]
                if v == 1:
                    break
        if v > 1:
            if v in big:
                works = False
            big.add(v)
        if not works:
            break
    if works:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = tuple(map(int, input().split()))
def fact(n):
    factors = set()
    while n%2 == 0:
        factors.add(2)
        n //=2

    for f in range(3, int(n**0.5)+ 1, 2):
        while n%f == 0:
            factors.add(f)
            n //= f
    if n != 1:
        factors.add(n)
    return factors

fact_and = fact(A[0])
fact_or = fact(A[0])

pairwise = True
for a in A[1:]:
    aset = fact(a)
    if len(fact_or & aset):
        # 今まで出てきた素因数と共通するものが見つかったらpairwiseではない
        pairwise = False
    fact_and = fact_and & aset
    fact_or = fact_or | aset

if pairwise:
    print('pairwise coprime')
else:
    if len(fact_and) == 0:
        # すべてに共通する素因数が見つからなかったら
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
A.sort()

def gcd(n,m):
	if m > n:
		n,m = m,n
	a,b = n,m
	while b > 0:
		a,b = b, a%b
	return a

isPC = True

p,s = A[0], A[0]

for n in A[1:]:
	if isPC and gcd(p, n) == 1:
		p *= n
	else:
		isPC = False

	if s > 1:
		s = gcd(s, n)

if isPC:
	print("pairwise coprime")
elif s == 1:
	print("setwise coprime")
else:
	print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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


def divisor(n: int) -> list:
    if n == 1:
        return [1]
    for i in range(1, n):
        if n % i == 0:
            if i > 1:
                dic[i]+=1
            if i != n / i:
                dic[int(n / i)] += 1
        if (i + 1) * (i + 1) > n:
            return

for a in A:
    divisor(a)

flg_pair = True
flg_step = True

for a in dic.values():
    if a > 1:
        flg_pair = False
    if a == N:
        flg_step = False

if flg_pair:
    print('pairwise coprime')
elif flg_step:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
def main():

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

    def isprime(a):
        if a == 1: return False
        for i in range(2, int(math.sqrt(a))+1):
            if a % i == 0: return False
        return True

    primes = []
    for v in range(1, max(A)+1):
        if isprime(v):  primes.append(v)

    d = dict()
    ispair = True
    isset = True
    for v in A:
        for p in primes:
            if v % p == 0:
                d[p] = d.get(p, 0) + 1
    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:
import math
import unittest


def f(n):
    e = set()
    if n < 2:
        return e
    if n % 2 == 0:
        e.add(2)
        while n % 2 == 0:
            n //= 2
    i = 3
    while i <= n:
        if n % i == 0:
            e.add(i)
            while n % i == 0:
                n //= i
        i += 2
    return e


def is_pairwise_coprime(n, a):
    e = set()
    for i in range(n):
        e2 = f(a[i])
        if e & e2:
            return False
        e |= e2
    return True


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


def solve(n, a):
    a = [e for e in a if e > 1]
    a.sort(reverse=True)
    len_a = len(a)
    if is_pairwise_coprime(len_a, a):
        return 'pairwise coprime'
    elif len_a < n or is_setwise_coprime(n, a):
        return 'setwise coprime'
    else:
        return 'not coprime'


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(n, a))


if __name__ == "__main__":
    main()


class Test(unittest.TestCase):
    def test_1(self):
        n = 3
        a = [3, 4, 5]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_2(self):
        n = 3
        a = [6, 10, 15]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_3(self):
        n = 3
        a = [6, 10, 16]
        self.assertEqual(solve(n, a), 'not coprime')

    def test_4(self):
        n = 3
        a = [1, 1, 1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_5(self):
        n = 3
        a = [1, 2, 2]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_6(self):
        n = 10
        a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_7(self):
        n = 11
        a = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def main():  
    def factorization(num):
        result = []
        temp = num
        for i in range(2, int(num ** 0.5) + 1):
            if temp % i == 0:
                while temp % i == 0:
                    temp /= i
                d[i] += 1
                result.append(i)
        if temp != 1:
            d[int(temp)] += 1
            result.append(int(temp))
        if result == []:
            d[num] += 1

        return 0
    n = int(input())
    A = map(int, input().split())
    d = defaultdict(int)
    for a in A:
        factorization(a)
    d[1] = 0
    m = max(d.values())
    if m == n:
        print('not coprime')
    elif m >= 2:
        print('setwise coprime')
    else:
        print('pairwise coprime')
    



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def resolve():
    import copy
    n = int(input())
    a = list(map(int, input().split()))
    pairwise = True
    union = PrimeFactorization(a[0])
    intersection = copy.deepcopy(union)
    for i in a[1:]:
        p = PrimeFactorization(i)
        if pairwise and p & union:
            pairwise = False
        union = union | p
        intersection = intersection & p
    if intersection:
        print("not coprime")
        return
    if pairwise:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

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

npcf = False
for i in range(N - 1):
    for j in range(i + 1, N):
        if gcd(A[i], A[j]) != 1:
            npcf = True
            break
    if npcf:
        break

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

buf = A[0]
for a in A[1:]:
    buf = gcd(buf, a)
if buf == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))

def gcd(n,m):
	if m > n:
		n,m = m,n
	a,b = n,m
	while b > 0:
		a,b = b, a%b
	return a

isPC = True

p,s = A[0], A[0]

for n in A[1:]:
	if isPC and gcd(p, n) == 1:
		p *= n
	else:
		isPC = False

	if s > 1:
		s = gcd(s, n)

if isPC:
	print("pairwise coprime")
elif s == 1:
	print("setwise coprime")
else:
	print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))

d = defaultdict(int)

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

f = 1

for ai in a:
    # g = gcd(g, ai)
    for n, cnt in factorization(ai):
        if n in d:
            f = 0
        if n != 1:
            d[n] += 1



if f:
    print('pairwise coprime')
else:
    f2 = 1
    for key in d:
        if d[key] == N:
            f2 = 0
            break
    if f2:
        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)
            
        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


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

    for i in A:
        tmp = set()
        for j in sosus:
            if i % j ==0:
                tmp.add(j)

                while i % j ==0:
                    i //=j
        sosus.difference_update(tmp)
        
        if i != 1:
            break
    else:
        print('pairwise coprime')
        return

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

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

resolve()

Submission status: Time Limit Exceeded

Solution code:
def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

pl = eratosthenes(10**6)
pd = {}
for p in pl:
    pd[p] = 0

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

A.sort()



d = {}
ans = 0
for i in range(N):
    if A[i] not in pd:
        primes = prime_decomposition(A[i])
        for p in primes:
            if p not in d:
                d[p] = 0
            else:
                ans = 1
                break
    else:
        if A[i] in d:
            ans = 1
            break
        d[A[i]] = 0

if ans == 0:
    print('pairwise coprime')
else:
    def gcd(a, b):
    	while b:
    		a, b = b, a % b
    	return a
    a = A[0]
    for i in range(N):
        a = gcd(a,A[i])
    if a==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

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

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]
used = [False] * len(primes)
big = set()

g = A[0]
for v in A:
    g = gcd(v,g)
if g == 1:  
    works = True
    for v in A:
        for i in range(len(primes)):
            if v % primes[i] == 0:
                if used[i]:
                    works = False
                used[i] = True
                while v % primes[i] == 0:
                    v //= primes[i]
        if v > 1:
            if v in big:
                works = False
            big.add(v)
    if works:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

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

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

n = int(input())
x = list(map(int,input().split()))
mod = int(1e9 + 7)

prod = x[0]
lc = x[0]
gc = x[0]

for i in range(1, len(x)):
    prod *= x[i]
    lc = lcm(lc, x[i])
    gc = gcd(gc, x[i])

if gc > 1: print ("not coprime")
elif lc == prod: print ("pairwise coprime")
else: print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
from functools import reduce
from math import gcd
g=reduce(lambda x,y:gcd(x,y),A,0)
if g>1:
    print('not coprime')
    exit()
def prime(N):
    p=set(range(2,N+1))
    for i in range(int(N**.5)+1):
        if i in p:
            p-=set(range(i*2,N+1,i))
    return p
p=prime(max(A))
r=1
for a in A:
    p2=p.copy()
    for x in p:
        if a%x==0:
            p2.remove(x)
        while a%x==0:
            a//=x
        if a==1:
            break
    if a>1:
        r=0
        break
    p=p2
print(['setwise coprime','pairwise coprime'][r])

Submission status: Time Limit Exceeded

Solution code:
import functools
import math

n=int(input())
values=list(map(int,input().split()))
setgcd = functools.reduce(math.gcd, values)

flag=True
for i in range(n-1):
  if flag==False:
    break
  for j in range(i+1,n):
    if math.gcd(values[i],values[j])!=1:
      flag=False
      #print(values[i],values[j])
      break

if flag:
  print("pairwise coprime")
elif setgcd==1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
ls=[int(s) for s in input().split()]
M=max(ls)
SQRT_M=int(math.sqrt(M))+1
#素数のリスト作成
prime=[1 for i in range(SQRT_M+1)]
prime[0]=0
prime[1]=0
primels=[]
primedic={}
for i in range(2,SQRT_M+1):
  if prime[i]==1:
    primels.append(i)
    primedic[i]=0
    a=1
    while a*i<=SQRT_M:
      prime[a*i]=0
      a+=1

for e in ls:
  for p in primels:
    if e%p==0:
      primedic[p]+=1
      while e%p==0:
        e//=p
    if e==1:
      break
  else:
    if e in primedic:
      primedic[e]+=1
    else:
      primedic[e]=1
    

A=max(primedic.values())

if A==len(ls):
  print('not coprime')
elif A>1:
  print('setwise coprime')
else:
  print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 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


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
for a in A:
    g_set = gcd(g_set, a)
    for p, n in factorization(a):
        if cnt[p] != 0:
            flg = 0
        cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
import math

input = sys.stdin.readline


# 素因数分解O(√n)

def primeFactor(n):
    res = defaultdict(lambda: 0)
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res[i] += 1
            n = n // i
    if n != 1:
        res[n] = 1
    return res


def main():
    N = int(input())
    A = list(map(int, input().split()))
    primes = defaultdict(lambda: 0)
    for i in range(N):
        pf = primeFactor(A[i])
        for k in pf.keys():
            primes[k] += 1
    if all(primes[k] == 1 for k in primes.keys()):
        print('pairwise coprime')
    elif all(primes[k] < N for k in primes.keys()):
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def get_prime(p):
  result = []
  if p==1:
    return result
  else:
    integers = [1 for _ in range(p+1)]
    integers[0] = 0
    integers[1] = 0
    for i in range(p+1):
      if integers[i] == 1:
        result.append(i)
        for j in range(i,p+1,i):
          integers[j] = 0
    return result

def one_coprime(p):
  count = 0
  for a in A:
    if a%p == 0:
      count += 1
  return count <= 1

def none_coprime(p):
  count = 0
  for a in A:
    if a%p != 0:
      return False
  return True

maxA = max(A)
minA = min(A)

answer = 'pairwise coprime'
if maxA > 1:
  for p in get_prime(maxA):
    if one_coprime(p) == False:
      answer = 'setwise coprime'
      break
if answer == 'setwise coprime' and minA > 1:
  for p in get_prime(minA):
    if none_coprime(p) == True:
      answer = 'not coprime'
      break

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

pc = True
gg = A[0]
so = set()

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

for a in factorization(A[0]):
    if a > 1:
        so.add(a)

for i in range(1, N):
    for a in factorization(A[i]):
        if a in so:
            pc = False
            break
        if a > 1:
            so.add(a)
    gg = gcd(A[i], gg)

if pc:
    print("pairwise coprime")
elif gg == 1:
    print("setwise coprime")
else:
    print("not coprime")