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:
#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import math,sys

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))
#n = int(input())
#a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])
pc = True

pairwise = True
p = set() #all prime

for e in a:
    if not pairwise:
        break
    asf = set(factrial(e))
    if judge & asf != set():
        pc = False
    #     #pairwise = False
    #     print("setwise coprime")
    #     exit(0)
    judge = judge | asf
# for i in a:
#     if not pc:
#         break
#     asf = set(factrial(i))

#     if judge & asf != set():
#         pc = False
#     judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))
#n = int(input())
#a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])
pc = True

pairwise = True
p = set() #all prime

for e in a:
    if not pairwise:
        break
    f = set(factrial(e))
    if judge & f != set():
        pc = False
    #     #pairwise = False
    #     print("setwise coprime")
    #     exit(0)
    judge = judge | f
# for i in a:
#     if not pc:
#         break
#     asf = set(factrial(i))

#     if judge & asf != set():
#         pc = False
#     judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))
#n = int(input())
#a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])
pc = True

pairwise = True
p = set() #all prime

for e in a:
    if not pairwise:
        break
    f = set(factrial(e))
    if p & f != set():
        pc = False
    #     #pairwise = False
    #     print("setwise coprime")
    #     exit(0)
    p = p | f
for i in a:
    if not pc:
        break
    asf = set(factrial(i))

    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
# def gen_is_prim(n):
#     is_prim = [i%2==1 for i in range(n+1)]
#     is_prim[1] = False; is_prim[2] = True
#     for i in range(3, n+1, 2):
#         if not is_prim[i]: continue
#         for j in range(i+i, n+1, i):
#             is_prim[j] = False
#     return is_prim

def gen_d_prim(n):
    D = [n+1 if i%2 else 2 for i in range(n+1)]
    D[0] = D[1] = 0
    for i in range(3, n+1, 2):
        if D[i] != n+1: continue
        for j in range(i, n+1, i): D[j] = i
    return D

def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def is_pairwise():
    # MAX_A = 10**6 + 1
    # C = [0] * MAX_A
    # for a in A: C[a] += 1
    # if sum(C[2::2]) > 1: return False
    # for i in range(3, MAX_A, 2):
    #     if sum(C[i::i]) > 1: return False
    # return True

    MAX_A = 10**6
    D = gen_d_prim(MAX_A)
    C = [0] * (MAX_A + 1)
    pre = set()
    for a in A:
        now = set()
        while a != 1:
            now.add(D[a])
            a //= D[a]
        # print('pre {}'.format(pre))
        # print('now {}'.format(now))
        # print('now & pre {}'.format(now & pre))
        if len(now & pre) > 0: return False
        pre = pre | now
    return True

def solve():
    if is_pairwise(): return 0
    if gcd_all(A) == 1: return 1
    return 2

    # if gcd_all(A) > 1: return 2
    # if is_pairwise(): return 0
    # return 1


n = int(input())
A = [*map(int, input().split())]
print(['pairwise','setwise','not'][solve()], 'coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

def prime_factorize(n):
    a = set()
    for i in range(2, int(n**0.5)+1):
        while n%i == 0:
            a.add(i)
            n //= i
    if n != 1:
        a.add(n)
    return a

n = int(input())
a = list(map(int, input().split()))
c0 = False
vals = []
for i, j in enumerate(a):
    vals += prime_factorize(j)
    if len(vals) != len(set(vals)) and c0 is False:
        c0 = True
        
if c0 is False:
    print('pairwise coprime')
else:
    b = gcd(a[0], a[1])
    for i in range(2, n):
        b = gcd(b, a[i])
    if b == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

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

n = int(input())
a = list(map(int, input().split()))
c0 = False
vals = []
for i, j in enumerate(a):
    vals += prime_factorize(j)
    if len(vals) != len(set(vals)) and c0 is False:
        c0 = True
        
if c0 is False:
    print('pairwise coprime')
else:
    b = gcd(a[0], a[1])
    for i in range(2, n):
        b = gcd(b, a[i])
    if b == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

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

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))
#n = int(input())
#a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])
pc = True

pairwise = True
p = set() #all prime

for e in a:
    if not pairwise:
        break
    f = set(factrial(e))
    #print(p,f)
    if p & f != set():
        pc = False
        #pairwise = False
        print("setwise coprime")
        exit(0)
    p = p | f
# for i in a:
#     if not pc:
#         break
#     asf = set(factrial(i))

#     if judge & asf != set():
#         pc = False
#     judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

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

import math
acc = a[0]
LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
# def factrial(N):
#     ret = []
#     while minPrime[N] != N:
#         ret.append(minPrime[N])
#         N = N//minPrime[N]
#     if N != 1:
#         ret.append(N)
#     return ret

def factrial(N):
    ret = set()
    while 1 != N:
        ret.add(minPrime[N])
        N = N//minPrime[N]
    if N != 1:
        ret.add(N)
    return ret

for i in range(N):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

pairwise = True
p = set() #all prime
for e in a:
    if not pairwise:
        break
    f = factrial(e)
    if p & f != set():
        pairwise = False
        print("setwise coprime")
        exit(0)
    p = p | f

if pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

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

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

import math
acc = a[0]
LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            for j in range(i+i,LIMIT+1,i):
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
# def factrial(N):
#     ret = []
#     while minPrime[N] != N:
#         ret.append(minPrime[N])
#         N = N//minPrime[N]
#     if N != 1:
#         ret.append(N)
#     return ret

def factrial(N):
    ret = set()
    while 1 != N:
        ret.add(minPrime[N])
        N = N//minPrime[N]
    if N != 1:
        ret.add(N)
    return ret

for i in range(N):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

pairwise = True
p = set() #all prime
for e in a:
    if not pairwise:
        break
    f = factrial(e)
    if p & f != set():
        pairwise = False
    p = p | f

if pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

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

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

import math
acc = a[0]
LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
for i in range(2,LIMIT+1):
    if minPrime[i] == 0:
        minPrime[i] = i
        for j in range(i+i,LIMIT+1,i):
            if minPrime[j] == 0:
                minPrime[j] = i

# def factrial(N):
#     ret = []
#     while minPrime[N] != N:
#         ret.append(minPrime[N])
#         N = N//minPrime[N]
#     if N != 1:
#         ret.append(N)
#     return ret

def factrial(N):
    ret = set()
    while 1 != N:
        ret.add(minPrime[N])
        N = N//minPrime[N]
    if N != 1:
        ret.add(N)
    return ret

for i in range(N):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

pairwise = True
p = set() #all prime
for e in a:
    if not pairwise:
        break
    f = factrial(e)
    if p & f != set():
        pairwise = False
    p = p | f

if pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

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

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

from math import gcd
import math
acc = a[0]
LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
for i in range(2,LIMIT+1):
    if minPrime[i] == 0:
        minPrime[i] = i
        for j in range(i+i,LIMIT+1,i):
            if minPrime[j] == 0:
                minPrime[j] = i

# def factrial(N):
#     ret = []
#     while minPrime[N] != N:
#         ret.append(minPrime[N])
#         N = N//minPrime[N]
#     if N != 1:
#         ret.append(N)
#     return ret

def factrial(N):
    ret = set()
    while 1 != N:
        ret.add(minPrime[N])
        N = N//minPrime[N]
    if N != 1:
        ret.add(N)
    return ret

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

pairwise = True
p = set() #all prime
for e in a:
    if not pairwise:
        break
    #f = set(factrial(e))
    f = factrial(e)
    if p & f != set():
        pairwise = False
    p = p | f

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

Submission status: Time Limit Exceeded

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

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

from math import gcd
import math
acc = a[0]
LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
for i in range(2,LIMIT+1):
    if minPrime[i] == 0:
        minPrime[i] = i
        for j in range(i+i,LIMIT+1,i):
            if minPrime[j] == 0:
                minPrime[j] = i

# def factrial(N):
#     ret = []
#     while minPrime[N] != N:
#         ret.append(minPrime[N])
#         N = N//minPrime[N]
#     if N != 1:
#         ret.append(N)
#     return ret

def factrial(N):
    ret = set()
    while minPrime[N] != N:
        ret.add(minPrime[N])
        N = N//minPrime[N]
    if N != 1:
        ret.add(N)
    return ret

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

pairwise = True
p = set() #all prime
for e in a:
    if not pairwise:
        break
    #f = set(factrial(e))
    f = factrial(e)
    if p & f != set():
        pairwise = False
    p = p | f

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

Submission status: Time Limit Exceeded

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

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

lis = {}
lis2= [0]*(10**6+1)
flg1 = True

for i in range(n):
  temp =  make_divisors(a[i])
  for j in temp:
    if j == 1:
      continue
    """
    if not  j in lis:
      lis[j]=1
    else:
      flg1 = False
      lis[j]+=1
      if lis[j]==n:
        print("not coprime")
        quit()
    """
    lis2[j]+=1
    if lis2[j]>1:
      flg1 = False
      if lis2[j]==n:
        print("not coprime")
        quit()
    

if flg1:
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Time Limit Exceeded

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

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

from math import gcd
import math
acc = a[0]
LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
for i in range(2,LIMIT+1):
    if minPrime[i] == 0:
        for j in range(i,LIMIT+1,i):
            if minPrime[j] == 0:
                minPrime[j] = i

# def factrial(N):
#     ret = []
#     while minPrime[N] != N:
#         ret.append(minPrime[N])
#         N = N//minPrime[N]
#     if N != 1:
#         ret.append(N)
#     return ret

def factrial(N):
    ret = set()
    while minPrime[N] != N:
        ret.add(minPrime[N])
        N = N//minPrime[N]
    if N != 1:
        ret.add(N)
    return ret

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

pairwise = True
p = set() #all prime
for e in a:
    if not pairwise:
        break
    #f = set(factrial(e))
    f = factrial(e)
    if p & f != set():
        pairwise = False
    p = p | f

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

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

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

lis = {}
lis2= [0]*(10**6+1)
flg1 = True

for i in range(n):
  temp =  make_divisors(a[i])
  for j in temp:
    if j == 1:
      continue
    """
    if not  j in lis:
      lis[j]=1
    else:
      flg1 = False
      lis[j]+=1
      if lis[j]==n:
        print("not coprime")
        quit()
    """
    lis2[j]+=1
    if lis2[j]>1:
      flg1 = False
      if lis2[j]==n:
        print("not coprime")
        quit()
    

if flg1:
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

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

lis = {}
flg1 = True

for i in range(n):
  temp =  make_divisors(a[i])
  for j in temp:
    if j == 1:
      continue
    if not  j in lis:
      lis[j]=1
    else:
      flg1 = False
      lis[j]+=1
      if lis[j]==n:
        print("not coprime")
        quit()
      
if flg1:
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Time Limit Exceeded

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

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

from math import gcd
import math
acc = a[0]
LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
count = 0
for i in range(2,LIMIT+1):
    if minPrime[i] == 0:
        count += 1
        j = i
        while j <= LIMIT:
            if minPrime[j] == 0:
                minPrime[j] = i
            j += i
#print(minPrime)
def factrial(N):
    ret = []
    while minPrime[N] != N:
        ret.append(minPrime[N])
        N = N//minPrime[N]
    if N != 1:
        ret.append(N)
    return ret

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

pairwise = True
# facts = [set(factrial(e)) for e in a]
p = set() #all prime
#s = set(factrial(a[0])) # pair prime
for e in a:
    if not pairwise:
        break
    f = set(factrial(e))
    # s = s & f
    if p & f != set():
        pairwise = False
    p = p | f
#print(p,s,pairwise)

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

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

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

lis = {}
flg1 = True
flg2 = True

for i in range(n):
  temp =  make_divisors(a[i])
  for j in temp:
    if j == 1:
      continue
    if not  j in lis:
      lis[j]=1
    else:
      flg1 = False
      lis[j]+=1
      if lis[j]==n:
        flg2 = False
      
if flg1:
  print("pairwise coprime")
elif flg2:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

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

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

from math import gcd
import math
acc = a[0]
LIMIT=10**6
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
count = 0
for i in range(2,LIMIT):
    if minPrime[i] == 0:
        count += 1
        j = i
        while j <= LIMIT:
            if minPrime[j] == 0:
                minPrime[j] = i
            j += i
#print(minPrime)
def factrial(N):
    ret = []
    while minPrime[N] != N:
        ret.append(minPrime[N])
        N = N//minPrime[N]
    if N != 1:
        ret.append(N)
    return ret

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

pairwise = True
# facts = [set(factrial(e)) for e in a]
p = set() #all prime
#s = set(factrial(a[0])) # pair prime
for e in a:
    if not pairwise:
        break
    f = set(factrial(e))
    # s = s & f
    if p & f != set():
        pairwise = False
    p = p | f
#print(p,s,pairwise)

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

Submission status: Time Limit Exceeded

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

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

from math import gcd
import math
acc = a[0]
LIMIT=10**6
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
count = 0
for i in range(2,LIMIT):
    if minPrime[i] == 0:
        count += 1
        j = i
        while j <= LIMIT:
            if minPrime[j] == 0:
                minPrime[j] = i
            j += i
#print(minPrime)
def factrial(N):
    ret = []
    while minPrime[N] != N:
        ret.append(minPrime[N])
        N = N//minPrime[N]
    if N != 1:
        ret.append(N)
    return ret

pairwise = True
# facts = [set(factrial(e)) for e in a]
p = set() #all prime
s = set(factrial(a[0])) # pair prime
for e in a:
    f = set(factrial(e))
    s = s & f
    if p & f:
        pairwise = False
    p = p | f
#print(p,s,pairwise)

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