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
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

from math import gcd
n = int(input())
a = list( map(int, input().split()))

g = 0
for aa in a:
    g = gcd(g,aa)
if g > 1:
    print('not coprime')
    exit()

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


g = 0
for aa in a:
    g = gcd(g,aa)
if g > 1:
    print('not coprime')
    exit()

seta = set(a)
if seta == {1}:
    print('pairwise coprime')
    exit()

prime_numbers_list = eratosthenes(10**6+10)

insu_set = set()
for aa in a:
    for prime in prime_numbers_list:
        tmp = set()
        if aa % prime ==0:
            tmp.add(prime)
            aa //= prime
        if tmp & insu_set:
            print('setwise coprime')
            exit()
        else:
            insu_set = insu_set | tmp

print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
MAX = 10**6
 
sieve = [i for i in range(MAX+1)]
 
p = 2
while p * p <= MAX:
    if sieve[p] == p:
        for i in range(p*2, MAX+1, p):
            if sieve[i] == i:
                sieve[i] = p
    p += 1
 
 
N = int(input())
A = list(map(int, input().split()))
pf = []
 
for a in A:
    tmp = set()
    b = a
    while b != 1:
        tmp.add(sieve[b])
        b //= sieve[b]
    pf.append(tmp)
 
 
soin = [0] * (10 ** 6 + 1)
for f in pf:
    for n in f:
        soin[n] += 1
 
if max(soin[2:]) <= 1:
    print('pairwise coprime')
    exit()
 
flag = np.gcd.reduce(A)
 
if flag == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
aa=int(input())
li = list(map(int,input().split()))
n=max(li)
def prime_2(n):
    l = list(range(2, n + 1))
    l_empty = []
    while len(l) >= 1:
        l_empty.append(l[0])
        s = set(l) - {j for j in l if j%l[0] == 0}
        list_s = list(s)
        l = sorted(list_s)
    return l_empty
primelist=prime_2(n)

for i in range(len(primelist)):
    cnt=0
    for k in li:
        if k%primelist[i]==0:
            cnt+=1
            if cnt==2:
                ans = li[0]
                for i in range(1,aa):
                    ans = math.gcd(ans, li[i])
                if ans==1:
                    print("setwise coprime")
                    exit()
                else:
                    print("not coprime")
                    exit()
print("pairwise coprime")

Submission status: Time Limit Exceeded

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

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

d = {}
flag = True
flag2 = True

b = list(set(a))
cnt = a.count(1)

if cnt != 0:
    if len(a) - len(b) - cnt + 1 != 0:
        flag = False
else:
    if len(a) != len(b):
        flag = False

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

for i in b:
    li2 = factorization(i)
    for x,y in li2:
        if x in d:
            d[x] += 1
        else:
            d[x] = 1

for i,j in d.items():
    if i != 1:
        if j == len(b):
            flag2 = False
        elif j >= 2:
            flag = False

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

Submission status: Time Limit Exceeded

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

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

d = {}
flag = True
flag2 = True

b = list(set(a))
cnt = a.count(1)

if 1 in a:
    if len(a) - len(b) - cnt + 1 != 0:
        flag = False
else:
    if len(a) != len(b):
        flag = False

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

for i in b:
    li2 = factorization(i)
    for x,y in li2:
        if x in d:
            d[x] += 1
        else:
            d[x] = 1

for i,j in d.items():
    if i != 1:
        if j == len(b):
            flag2 = False
        elif j >= 2:
            flag = False

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

Submission status: Time Limit Exceeded

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

li = [0] * 10**6

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

for i in a:
    li2 = factorization(i)
    for x,y in li2:
        li[x] += 1

flag = True
flag2 = True

for i in li[2:]:
    if i == n:
        flag2 = False
    elif i >= 2:
        flag = False

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

Submission status: Time Limit Exceeded

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

def prime_factor(n):
    """因数分解して因数のみを取得する"""
    if n <= 1: return set()

    ans = set()
    i = 2
    while i*i <= n:
        while n%i == 0:
            if not i in ans:
                ans.add(i)
            n //= i
        i += 1

    if n != 1:
        ans.add(n)
    return ans

def solve():
    import sys
    N = int(sys.stdin.readline())
    As = list(map(int, sys.stdin.readline().split()))

    pf_sets = []
    for a in As:
        pf_set = prime_factor(a)
        pf_sets.append(pf_set)


    # pairwiseにできる
    is_pairwise = True
    a_set = set()
    for pf_set in pf_sets:
        if len(a_set & pf_set) != 0:
            # すでに因数が存在するならpairwiseになれない
            is_pairwise = False
            break
        a_set |= pf_set

    if is_pairwise:
        print("pairwise coprime")
        return

    # setwiseにできるかを調べる
    is_setwise = False
    base_pf_set = pf_sets[0]
    for pf_set in pf_sets[1:]:
        base_pf_set &= pf_set

        if len(base_pf_set) == 0:
            is_setwise = True
            break

    if is_setwise:
        print("setwise coprime")
        return

    print("not coprime")

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

def prime_factor(n):
    """因数分解して因数のみを取得する"""
    if n <= 1: return set()

    ans = set()
    i = 2
    while i*i <= n:
        while n%i == 0:
            if not i in ans:
                ans.add(i)
            n //= i
        i += 1

    if n != 1:
        ans.add(n)
    return ans

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    pf_sets = []
    for a in As:
        pf_set = prime_factor(a)
        pf_sets.append(pf_set)


    # pairwiseにできる
    is_pairwise = True
    a_set = set()
    for pf_set in pf_sets:
        if len(a_set & pf_set) != 0:
            # すでに因数が存在するならpairwiseになれない
            is_pairwise = False
            break
        a_set |= pf_set

    if is_pairwise:
        print("pairwise coprime")
        return

    # setwiseにできるかを調べる
    is_setwise = False
    base_pf_set = pf_sets[0]
    for pf_set in pf_sets[1:]:
        base_pf_set &= pf_set

        if len(base_pf_set) == 0:
            is_setwise = True
            break

    if is_setwise:
        print("setwise coprime")
        return

    print("not coprime")

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Alist = list(map(int,input().split()))
Aprimes = []
isPC = True
isSC = False
# import time
# import random
# Alist = [random.randint(1,1000000) for i in range(1000000)]
# tt = time.time()

# make primelist
primelist = list(range(1,max(Alist)+1))
for item in primelist[1:]:
    for i in range(2,primelist[-1]//item+1):
        i*=item
        if i in primelist:
            primelist.remove(i)

def get_prime(a):
    primes = []
    for p in primelist[1:]:
        if p>a:
            break
        elif a%p == 0:
            primes.append(p)
    return primes

for a in Alist:
    p = get_prime(a)
    # if len(p)>1:
    Aprimes.append(p)

factors = []
cofactors = Aprimes[0]
# cofactors.remove(1)
for a in Aprimes:
    for p in a:
        if p in factors:
            isPC = False
        else:
            factors.append(p)
    for f in cofactors.copy():
        if f not in a:
            cofactors.remove(f)


if isPC:
    print('pairwise coprime')
elif len(cofactors)>0:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
soin = [0]*(10**6+1)
if a.count(1)==n:
    print("pairwise coprime")
    exit()

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


if len(a)>80000:
    ans=a[0]
    for i in a:
        ans=math.gcd(ans,i)
    if ans==1:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    for i in a:
        if i ==1:continue
        for num in factorization(i):
            soin[num]+=1
    if max(soin)==1:
        print("pairwise coprime")
    elif max(soin)==n and 1 not in a:
        print("not coprime")
    else:print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Alist = list(map(int,input().split()))
# import time
# import random
# Alist = [random.randint(1,1000000) for i in range(1000000)]
# tt = time.time()
def GCD(a,b):
    if a>b:
        a = a%b
        if a == 0:
            return(b)
        else:
            return GCD(a,b)
    else:
        b = b%a
        if b == 0:
            return(a)
        else:
            return GCD(a,b)

isPC = True
isSC = False
kouyaku = 1
skipindex = 0
prod = 1

for i,x in enumerate(Alist[1:]):
    prod*=Alist[i]
    # print(x,prod)
    if GCD(x,prod)>1:
        isPC = False
        kouyaku = GCD(x,prod)
        break

if kouyaku > 1:
    for x in Alist:
        kouyaku = GCD(x,kouyaku)
        if kouyaku == 1:
            isSC = True
            break

if isPC:
    print('pairwise coprime')
elif isSC:
    print('setwise coprime')
else:
    print('not coprime')
# print(time.time() - tt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Alist = list(map(int,input().split()))
    
def GCD(a,b):
    if a>b:
        a = a%b
        if a == 0:
            return(b)
        else:
            return GCD(a,b)
    else:
        b = b%a
        if b == 0:
            return(a)
        else:
            return GCD(a,b)
    
isPC = True
isSC = False
kouyaku = 1
skipindex = 0
    
for i,x in enumerate(Alist):
    for y in Alist[:i]:
        if GCD(x,y) != 1:
            isPC = False
            kouyaku = GCD(x,y)
            break
    else:
        continue
    break
    
if kouyaku > 1:
    for x in Alist:
        kouyaku = GCD(x,kouyaku)
        if kouyaku == 1:
            isSC = True
            break
    
if isPC:
    print('pairwise coprime')
elif isSC:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

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

def GCD(a,b):
    if a>b:
        a = a%b
        if a == 0:
            return(b)
        else:
            return GCD(a,b)
    else:
        b = b%a
        if b == 0:
            return(a)
        else:
            return GCD(a,b)

isPC = True
isSC = False
kouyaku = 1
skipindex = 0

for i,x in enumerate(Alist):
    for y in Alist[:i]:
        if GCD(x,y) != 1:
            isPC = False
            kouyaku = GCD(x,y)
            break
    else:
        continue
    skipindex = i
    break

if kouyaku > 1:
    for x in set(Alist[i:]):
        kouyaku = GCD(x,kouyaku)
        if kouyaku == 1:
            isSC = True
            break

if isPC:
    print('pairwise coprime')
elif isSC:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

N = input()
A = list(map(int, input().split()))
M = 10**3+1
ps = []
is_p = [True] * M
for i in range(2, M):
    if is_p[i]:
        ps.append(i)
        j = i + i
        while j < M:
            is_p[j] = False
            j += i
cnt = defaultdict(int)
for a in A:
    for p in ps:
        if a % p == 0:
            cnt[p] += 1
            while a % p == 0:
                a //= p
    if a > 1:
        cnt[a] += 1
if all([x < 2 for x in cnt.values()]):
    print("pairwise coprime")
    exit()
gcd = lambda x, y : x if y == 0 else gcd(y, x % y)
x = A[0]
for a in A[1:]:
    x = gcd(x, a)
if x == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

N = input()
A = list(map(int, input().split()))
M = 10**6+1
ps = []
is_p = [True] * M
for i in range(2, M):
    if is_p[i]:
        ps.append(i)
        j = i + i
        while j < M:
            is_p[j] = False
            j += i
for p in ps:
    cnt = 0
    for a in A:
        if a % p == 0:
            cnt += 1
    if cnt > 1:
        break
else:
    print("pairwise coprime")
    exit()
gcd = lambda x, y : x if y == 0 else gcd(y, x % y)
x = A[0]
for a in A[1:]:
    x = gcd(x, a)
if x == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
import sys

N = int(input())

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

A = max(a)+1

# 全ての数に対して、入っているかいないかを判別する配列を作る
c = [0]*A
for i in range(N):
    c[a[i]] += 1

# print(c)

pairwise = True

for i in range(2,A):
    cnt = 0

    # 素因数ずつ数を増やしていき、同じ素因数を持つことがあればpairwiseではない
    # たとえば、3ならば、3,6,9,,と増やしていき、それがc[]に１つ以上含まれているか調べていく
    for j in range(i,A,i):
        cnt += c[j]
    if (cnt > 1):
        pairwise = False

if pairwise:
    print("pairwise coprime")
    sys.exit()

g = 0
for i in range(N):
    g = gcd(g,a[i])
if (g == 1):
    print("setwise coprime")
    sys.exit()

else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

N = input()
A = list(map(int, input().split()))
ps = primes(10**6+1)
for p in ps:
    cnt = 0
    for a in A:
        if a % p == 0:
            cnt += 1
    if cnt > 1:
        break
else:
    print("pairwise coprime")
    exit()
gcd = lambda x, y : x if y == 0 else gcd(y, x % y)
x = A[0]
for a in A[1:]:
    x = gcd(x, a)
if x == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

N = input()
A = list(map(int, input().split()))
cnt = [0] * (10**6+1)
ps = primes(10**6+1)
for p in ps:
    for a in A:
        if a % p == 0:
            cnt[p] += 1
if all([x < 2 for x in cnt]):
    print("pairwise coprime")
    exit()
gcd = lambda x, y : x if y == 0 else gcd(y, x % y)
x = A[0]
for a in A[1:]:
    x = gcd(x, a)
if x == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

N = input()
A = list(map(int, input().split()))
dic = defaultdict(lambda : False)
ps = primes(10**6+1)
flg = True
for p in ps:
    for a in A:
        if a % p == 0:
            if dic[p]:
                flg = False
                break
            dic[p] = True
    if not flg:
        break
if flg:
    print("pairwise coprime")
    exit()
gcd = lambda x, y : x if y == 0 else gcd(y, x % y)
x = A[0]
for a in A[1:]:
    x = gcd(x, a)
if x == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

def GCD(a,b):
    if a>b:
        a = a%b
        if a == 0:
            return(b)
        else:
            return GCD(a,b)
    else:
        b = b%a
        if b == 0:
            return(a)
        else:
            return GCD(a,b)

isPC = True
isSC = False
kouyaku = 1


for i,x in enumerate(Alist):
    for y in Alist[:i]:
        if GCD(x,y) != 1:
            isPC = False
            kouyaku = GCD(x,y)
            break
    else:
        continue
    break

if kouyaku > 1:
    for x in set(Alist):
        kouyaku = GCD(x,kouyaku)
        if kouyaku == 1:
            isSC = True
            break

if isPC:
    print('pairwise coprime')
elif isSC:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

N = input()
A = list(map(int, input().split()))
dic = defaultdict(lambda : False)
ps = primes(10**6+1)
flg = True
for a in A:
    for p in ps:
        if p > a:
            break
        if a % p == 0:
            if dic[p]:
                flg = False
                break
            dic[p] = True
            while a % p == 0:
                a //= p
    if not flg:
        break
if flg:
    print("pairwise coprime")
    exit()
gcd = lambda x, y : x if y == 0 else gcd(y, x % y)
x = A[0]
for a in A[1:]:
    x = gcd(x, a)
if x == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

N = input()
A = list(map(int, input().split()))
dic = defaultdict(lambda : False)
ps = primes(10**6+1)
flg = True
for a in A:
    for p in ps:
        if a % p == 0:
            if dic[p]:
                flg = False
                break
            dic[p] = True
    if not flg:
        break
if flg:
    print("pairwise coprime")
    exit()
gcd = lambda x, y : x if y == 0 else gcd(y, x % y)
x = A[0]
for a in A[1:]:
    x = gcd(x, a)
if x == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import gcd
n = int(input())
a = list(map(int, input().split()))

c = [0]*1000006
for i in range(n):
    c[a[i]] += 1

pairwise = True
for i in range(2, 1000006):
    cnt = 0
    for j in range(i, 1000006, i):
        cnt += c[j]
    if cnt > 1:
        pairwise = False

if pairwise:
    print("pairwise coprime")
    sys.exit()

g = 0
for i in range(n):
    g = gcd(g, a[i])
if g == 1:
    print("setwise coprime")
    sys.exit()

print("not coprime")
sys.exit()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from math import gcd

    def soinsuu(a):
        yy, j = set(), 2
        y = yy.add
        while(a > 1):
            for i in range(j, int(a**0.5)+1):
                if a % i == 0:
                    y(i)
                    a, j = a//i, i
                    break
            else:
                y(a)
                break
        return yy
    n = int(input())
    a = list(map(int, input().split()))

    s = set()
    flag = False
    for i in a:
        so = soinsuu(i)
        for j in so:
            if j in s:
                flag = True
                break
            else:
                s.add(j)
        if flag:
            break
    if flag == False:
        print("pairwise coprime")
        return

    temp1 = a[0]
    for i in a[1:]:
        temp1 = gcd(temp1, i)
    if temp1 > 1:
        print("not coprime")
    else:
        print("setwise coprime")


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = map(int, input().split())

is_prime = [1] * 1001
is_prime[0] = 0
is_prime[1] = 0
for current in range(2, 1001):
  if is_prime[current]:
    for i in range(2, 1 + 1000//current):
      is_prime[i*current] = 0
primes = []
for i in range(2, 1001):
  if is_prime[i]:
    primes.append(i)

def factorize(n):
  factors = set()
  for p in primes:
    if n % p == 0:
      factors.add(p)
      while n % p == 0:
        n //= p
    if p * p > n:
      if n > 1:
        factors.add(n)
      break
  return factors

p_coprime = True
common_factors = None
appeared_factors = None
for a in A:
  f = factorize(a)
  #print(a, f, p_coprime, common_factors, appeared_factors) 
  if common_factors == None:
    common_factors = f
    appeared_factors = f
  else:
    if p_coprime and appeared_factors & f:
      p_coprime = False
    common_factors = common_factors & f
    appeared_factors = appeared_factors | f
  #print(a, f, p_coprime, common_factors, appeared_factors) 
if p_coprime:
  print('pairwise coprime')
elif not common_factors:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = map(int, input().split())

is_prime = [1] * 1001
is_prime[0] = 0
is_prime[1] = 0
for current in range(2, 1001):
  if is_prime[current]:
    for i in range(2, 1 + 1000//current):
      is_prime[i*current] = 0
primes = []
for i in range(2, 1001):
  if is_prime[i]:
    primes.append(i)

def factorize(n):
  factors = set()
  for p in primes:
    if n % p == 0:
      factors.add(p)
      while n % p == 0:
        n //= p
    if p * p > n:
      if n > 1:
        factors.add(n)
      break
  return factors

p_coprime = True
common_factors = None
appeared_factors = None
for a in A:
  f = factorize(a)
  #print(a, f, p_coprime, common_factors, appeared_factors) 
  if common_factors == None:
    common_factors = f
    appeared_factors = f
  else:
    if appeared_factors & f:
      p_coprime = False
    common_factors = common_factors & f
    appeared_factors = appeared_factors | f
  #print(a, f, p_coprime, common_factors, appeared_factors) 
if p_coprime:
  print('pairwise coprime')
elif not common_factors:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = NI()
    A = LI()

    # 1000までの素数列
    t = [True] * 1000
    for i in range(2,33):
        j = 2
        while i * j < 1000:
            t[i*j] = False
            j += 1
    p = []
    for i in range(2,1000):
        if t[i]: p.append(i)

    cnt = [0] * 1000000
    for x in A:
        for d in p:
            if x % d == 0:
                while x % d == 0:
                    x //= d
                if cnt[d]: break
                cnt[d] += 1
        else:
            if x > 1:
                if cnt[x]: break
                cnt[x] += 1
            continue
        break
    else:
        print('pairwise coprime')
        return

    g = A[0]
    for x in A[1:]:
        g = math.gcd(g,x)
        if g == 1:
            print('setwise coprime')
            return
    print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

A_max = max(A)
P = []
arr = list(range(2, A_max + 1))
while len(arr) > 0:
    i = arr.pop(0)
    P.append(i)
    arr = [j for j in arr if j % i != 0]
    if i > A_max ** 0.5:
        P.extend(arr)
        break
 
"""
素因数分解
"""
 
 
def factorize(x):
    f = []
    for p in P:
        rest = x
        cnt = 0
        while True:
            if rest % p != 0:
                break
            rest = rest // p
            cnt += 1
        f.append(cnt)
    return f
 
 
facts = [factorize(A_i) for A_i in A]
 
if all(sum([facts[j][i] > 0 for j in range(N)]) < 2 for i in range(len(P))):
    print('pairwise coprime')
    exit()
 
if all(not all([facts[j][i] > 0 for j in range(N)]) for i in range(len(P))):
    print('setwise coprime')
    exit()
 
print('not coprime')

Submission status: Time Limit Exceeded

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

"""
エラトステネスの篩

1. 探索リストに2からxまでの整数を昇順で入れる。
2. 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。
3. 上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
4. 探索リストに残った数を素数リストに移動して処理終了。
"""
A_max = max(A)
P = []
arr = list(range(2, A_max + 1))
while len(arr) > 0:
    i = arr.pop(0)
    P.append(i)
    arr = [j for j in arr if j % i != 0]
    if i > A_max ** 0.5:
        P.extend(arr)
        break

"""
素因数分解
"""


def factorize(x):
    f = []
    for p in P:
        rest = x
        cnt = 0
        while True:
            if rest % p != 0:
                break
            rest = rest // p
            cnt += 1
        f.append(cnt)
    return f


facts = [factorize(A_i) for A_i in A]

if all(sum([facts[j][i] > 0 for j in range(N)]) < 2 for i in range(len(P))):
    print('pairwise coprime')
    exit()

if all(not all([facts[j][i] > 0 for j in range(N)]) for i in range(len(P))):
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def sieve(n):
    is_prime = [True] * (n+1)
    divisors = [set() for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False

    p = 0
    for i in range(2,n+1):
        divisors[i].add(i)
        if is_prime[i]:
            p = i
            for j in range(p+p, n+1, p):
                divisors[j].add(i)
                is_prime[j] = False
        
        if p * 2 > n:
            break
    
    primes = []
    for i in range(2,n+1):
        if is_prime[i]:
            primes.append(i)

    return primes, divisors

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

    primes, divisors = sieve(10**6)
    divisors_counter = defaultdict(int)

    is_pairwise = True
    for a in A:
        for d in divisors[a]:
            if divisors_counter[d] != 0:
                is_pairwise = False
            divisors_counter[d] += 1
    
    if is_pairwise:
        print('pairwise coprime')
        return
    
    if list(divisors_counter.values()).count(N) == 0:
        print('setwise coprime')
    else:
        print('not coprime')
        
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd, sqrt
from functools import reduce

n, *A = map(int, open(0).read().split())
def f(A):
    sup = max(A)+1
    table = [set() for i in range(sup)]
    for i in range(2, sup):
        if not table[i]:
            for j in range(i, sup, i):
                table[j].add(i)
    D = set()
    for a in A:
        for b in table[a]:
            if b not in D:
                D.add(b)
            else:
                return False
    return True

if reduce(gcd, A) == 1:
    if f(A):
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')