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 math
import sys
from functools import reduce


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

def prime_factorize(n):
    prime_list = eratosthenes(n)
    arr = []

    for p in prime_list:
        if n % p == 0:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            arr.append([p, cnt])
    
    return arr

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


def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

prime_list = eratosthenes(n)
check = [0]*(10**6)
pairwise = True

for x in a:
    for p in prime_list:
        if x % p == 0:
            if check[p]:
                pairwise = False
            check[p] += 1
            if check[p] == n:
                print('not coprime')
                sys.exit()

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

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
from functools import reduce


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

def prime_factorize(n):
    prime_list = eratosthenes(n)
    arr = []

    for p in prime_list:
        if n % p == 0:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            arr.append([p, cnt])
    
    return arr

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


def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

prime_list = eratosthenes(n)
check = [0]*(10**6)
pairwise = True

for x in a:
    for p in prime_list:
        if x % p == 0:
            if check[p]:
                pairwise = False
                break
            check[p] = 1
    if not pairwise:
        break

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

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

Submission status: Time Limit Exceeded

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

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

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

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

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

# facts = [set(factrial(e)) for e in a]
s = set()
for e in a:
    f = set(factrial(e))
    if f & s:
        print("setwise coprime")
        exit()
    s = s | f
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:
import math

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

inf = int(1e6+5)
C = [0]*inf

for a in A:
    C[a] += 1

pa = True
se = True
for i in range(2, inf):
    cnt = 0
    for j in range(i, inf, i):
        cnt += C[j]
    if cnt > 1:
        pa = False
    if cnt == N:
        se = False
        
if pa:
    print("pairwise coprime")
elif se:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

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

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

def factrial(N):
    ret = []
    n = N
    for i in range(2,math.floor(pow(N,0.5))+1):
      while n%i==0:
        ret.append(i)
        n = n//i
    if n != 1:
        ret.append(n)
    return ret

# facts = [set(factrial(e)) for e in a]
s = set()
for e in a:
    f = set(factrial(e))
    if f & s:
        print("setwise coprime")
        exit()
    s = s | f
print("pairwise coprime")

Submission status: Time Limit Exceeded

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

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

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

def factrial(N):
    ret = []
    n = N
    for i in range(2,math.floor(pow(N,0.5))+1):
      while n%i==0:
        ret.append(i)
        n = n//i
    if n != 1:
        ret.append(n)
    return ret

# facts = [set(factrial(e)) for e in a]
s = set()
for e in a:
    f = set(factrial(e))
    if f & s:
        print("setwise coprime")
        exit()
    s = s | f
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:
#https://note.nkmk.me/python-gcd-lcm/
import math
from functools import reduce

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

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

isPairwiseCoprime = True
for i in range(n-1):
    for j in range(i+1,n):
        if math.gcd(a[i],a[j])!=1:
            isPairwiseCoprime = False
            break
    else:
        continue
    break

if isPairwiseCoprime:
    print('pairwise coprime')
else:
    if gcd_list(a)==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
import functools
import sys

N = int(input())
A = list(map(int, input().split()))
Amax = max(A) + 1
if Amax == 2:
    print('pairwise coprime')
    sys.exit(0)

hurui = [1] * 1001
primes = []

for n in range(2, 1001):
    if hurui[n] != 1:
        continue

    primes.append(n)

    k = 2
    while n * k <= 1000:
        hurui[n * k] = n
        k += 1


#print(len(list(filter(lambda i: i == 0, hurui))))
#print(primes)

#print(primes)

wise = functools.reduce(math.gcd, A)
if wise != 1:
    print('not coprime')
    sys.exit(0)

count = [0] * (Amax+1)

pairwise = True
for i in range(N):
    a = A[i]
    if a == 1:
        continue

    for p in primes:
        if a % p == 0:
            count[p] += 1
            while a % p == 0:
                a = a // p
    if a != 1:
        count[a] += 1

if max(count)==1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math

def sieve():
  n = 10**6+1
  primes = [True]*(n+1)
  primes[0],primes[1] = False,False

  for i in range(2,int(math.sqrt(n)+1)):
    if primes[i] == True:
      j = 2
      while i*j <= n:
        primes[i*j] = False
        j += 1

  return primes

def prime_factors(n):
  i = 2
  factors = set()
  while i * i <= n:
    if n % i:
      i += 1
    else:
      n //= i
      factors.add(i)

  if n > 1:
    factors.add(n)
  return factors

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

dic = {}
flg = True
for a in A:
  if primes[a]:
    facs = [a]
  else:
    facs = prime_factors(a)

  for p in facs:
    if p in dic:
      flg = False
      break
    else:
      dic[p] = 1

if flg:
  print("pairwise coprime")
else:
  g = A[0]
  for i in range(1, N):
    g = math.gcd(g, A[i])
  if g == 1:
    print("setwise coprime")
  else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
ma=max(a)
memo=[0]*ma

def gcd(a,b):#最大公約数
  while b!=0:
    a,b=b,a%b
  return a

for i in a:
  memo[i-1]+=1

pair=True
for i in range(2,ma+1):
  cnt=0
  for j in range(i,ma+1,i):
    if 0<memo[j-1]:
      cnt+=1
  if 1<cnt:
    pair=False


g=a[0]
for i in range(1,n):
  g=gcd(g,a[i])

if pair == False and g==1:
  print("setwise coprime")
elif pair == True and g==1:
  print("pairwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
d=[0]*(10**6)
for i in a:
  d[i-1]+=1
num=2
while num<=10**6:
  if sum([d[i*num-1] for i in range(1,10**6//num+1)])>1:
      break
  num+=1
else:
  print('pairwise coprime')
  exit()
g=reduce(gcd,a)
if g==1:
  print('setwise coprime')
  exit()

print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import math
def main():
    n=int(input())
    a=list(map(int,input().split()))
    ap=[set(prime_factorize(i)) for i in a]
    x=set()
    for i in ap:
        if len(x & i) > 0:
            break
        x |= i
    else:
        print("pairwise coprime")
        return
    x=a[0]
    for i in a:
        x = math.gcd(x, i)
    if x == 1:
        print("setwise coprime")
        return
    print("not coprime")

def prime_factorize(n: int) -> list:
    '''引数nの素因数分解結果のlistを返す。'''
    arr = []
    # 2で割り続け奇数まで還元する
    while n % 2 == 0:
        arr.append(2)
        n //= 2
    # sqrt(n)までの素数で試し割
    for f in primes(int(n**0.5)):
        while n % f == 0:
            arr.append(f)
            n //= f
    if n != 1:
        arr.append(n)
    return arr

@lru_cache(maxsize=None)
def primes(n:int) -> list:
    '''n以下の全素数をlistで返す'''
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

# 素数判定（単純な素数判定なら十分早い。大量にやる場合はX in primesがよさそう）
@lru_cache(maxsize=None)
def is_prime(n: int) -> bool:
    '''引数nが素数であればTrue、そうでなければFalseを返す'''
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from math import gcd
    from itertools import chain
    import sys
    input = sys.stdin.readline

    # def gcd(x, y):
    #     if y == 0:
    #         return x
    #     return gcd(y, x % y)
    # 6n+1, 6n-1でも求めて、素数**2+素数*kはふるいおとす
    def prime_set(N):
        if N < 4:
            return ({}, {}, {2}, {2, 3})[N]
        Nsq = int(N ** 0.5 + 0.5) + 1
        primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
        for i in range(5, Nsq, 2):
            if i in primes:
                primes -= set(range(i * i, N + 1, i * 2))
        # return list(primes)
        return primes
    n = int(input())
    A = [int(x) for x in input().split()]
    len_A = len(A)
    # setwise coprimeの条件(1ならOK)
    g = 0
    for a in A:
        g = gcd(g, a)
    # 素数列挙
    num = 10**6+1
    primes = prime_set(num)
    # 全部素因数分解
    prime_list = [0] * (num+1)
    pairwise_f = True
    for a in A:
        # l = []
        cnt = 0
        tmp = a
        # nsq = int(a ** 0.5 + 0.5) + 1
        for i in primes:
            if i*i > a:
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                prime_list[i] += 1
                # l.append(i)
                cnt += 1
                if prime_list[i] == 2:
                    break
        if tmp != 1:
            prime_list[tmp] += 1
            # l.append(tmp)
            cnt += 1
            if prime_list[tmp] == 2:
                break
        # if l == []:
        if cnt == 0:
            if a != 1:
                prime_list[a] += 1
                # l.append(a)
                if prime_list[a] == 2:
                    break
    set_prime_list = set(prime_list)
    # print(prime_list[:100])
    if set_prime_list != set([0]) and set_prime_list != set([0, 1]):
        pairwise_f = False
    if pairwise_f:
        print('pairwise coprime')
    elif g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    from itertools import chain
    import sys
    input = sys.stdin.readline

    def gcd(x, y):
        if y == 0:
            return x
        return gcd(y, x % y)
    # 6n+1, 6n-1でも求めて、素数**2+素数*kはふるいおとす
    def prime_set(N):
        if N < 4:
            return ({}, {}, {2}, {2, 3})[N]
        Nsq = int(N ** 0.5 + 0.5) + 1
        primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
        for i in range(5, Nsq, 2):
            if i in primes:
                primes -= set(range(i * i, N + 1, i * 2))
        # return list(primes)
        return primes
    n = int(input())
    A = [int(x) for x in input().split()]
    len_A = len(A)
    # setwise coprimeの条件(1ならOK)
    g = 0
    for a in A:
        g = gcd(g, a)
    # 素数列挙
    num = 10**6+1
    primes = prime_set(num)
    # 全部素因数分解
    prime_list = [0] * (num+1)
    pairwise_f = True
    for a in A:
        # l = []
        cnt = 0
        tmp = a
        # nsq = int(a ** 0.5 + 0.5) + 1
        for i in primes:
            if i*i > a:
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                prime_list[i] += 1
                # l.append(i)
                cnt += 1
                if prime_list[i] == 2:
                    break
        if tmp != 1:
            prime_list[tmp] += 1
            # l.append(tmp)
            cnt += 1
            if prime_list[tmp] == 2:
                break
        # if l == []:
        if cnt == 0:
            if a != 1:
                prime_list[a] += 1
                # l.append(a)
                if prime_list[a] == 2:
                    break
    set_prime_list = set(prime_list)
    # print(prime_list[:100])
    if set_prime_list != set([0]) and set_prime_list != set([0, 1]):
        pairwise_f = False
    if pairwise_f:
        print('pairwise coprime')
    elif g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
sys.setrecursionlimit(10**9)

n = int(input())
a = list(map(int, input().split()))
ma = max(a)
p = [0]*(ma + 1)

for i in a:
  p[i] += 1

pairwise = True
for i in range(2, ma+1):
  cnt = 0
  for j in range(i, ma+1, i):
    cnt += p[j]
  if cnt > 1:
    pairwise = False
    
if pairwise:
  print("pairwise coprime")
else:
  temp = a[0]
  for i in a:
    temp = math.gcd(temp, i)
  if temp == 1:
    print("setwise coprime")
  else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
# N = 10**6
# A = [10**6-i for i in range(N)]

def is_pairwise_coprime():
    l = [0]*(10**6+1)
    for a in A:
        for j in range(2, int(a**(1/2))+2):
            if a % j == 0:
                if l[j]:
                    return False
                l[j] = 1
            while a % j == 0:
                a //= j
        if a != 1:
            if l[a]:
                return False
            l[a] = 1
    return True

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

def is_setwise_coprime():
    A_gcd = A[0]
    for a in A[1:]:
        A_gcd = gcd(A_gcd, a)
        if A_gcd == 1:
            break
    return (A_gcd == 1)

if is_pairwise_coprime():
    print("pairwise coprime")
elif is_setwise_coprime():
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:

def main():
    from itertools import chain
    import sys
    input = sys.stdin.readline

    def gcd(x, y):
        if y == 0:
            return x
        return gcd(y, x % y)
    # 6n+1, 6n-1でも求めて、素数**2+素数*kはふるいおとす
    def prime_set(N):
        """
        Nまでの素数のsetを返す
        """
        if N < 4:
            return ({}, {}, {2}, {2, 3})[N]
        Nsq = int(N ** 0.5 + 0.5) + 1
        primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
        for i in range(5, Nsq, 2):
            if i in primes:
                primes -= set(range(i * i, N + 1, i * 2))
        return list(primes)
    n = int(input())
    A = [int(x) for x in input().split()]
    len_A = len(A)
    # setwise coprimeの条件(1ならOK)
    g = 0
    for a in A:
        g = gcd(g, a)
    # 素数列挙
    num = 10**6+1
    primes = prime_set(num)
    # 全部素因数分解
    prime_list = [0] * (num+1)
    pairwise_f = True
    ll = list()
    for a in A:
        l = []
        tmp = a
        # nsq = int(a ** 0.5 + 0.5) + 1
        for i in primes:
            if  i*i > a:
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                prime_list[i] += 1
                l.append(i)
                if prime_list[i] == 2:
                    break
        if tmp != 1:
            prime_list[tmp] += 1
            l.append(tmp)
            if prime_list[tmp] == 2:
                break
        if l == []:
            if a != 1:
                prime_list[a] += 1
                l.append(a)
                if prime_list[a] == 2:
                    break  
    set_prime_list = set(prime_list)
    if set_prime_list != set([0]) and set_prime_list != set([0, 1]):
        pairwise_f = False
    if pairwise_f:
        print('pairwise coprime')
    elif g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    from itertools import chain
    import sys
    input = sys.stdin.readline

    def gcd(x, y):
        if y == 0:
            return x
        return gcd(y, x % y)
    # 6n+1, 6n-1でも求めて、素数**2+素数*kはふるいおとす
    def prime_set(N):
        """
        Nまでの素数のsetを返す
        """
        if N < 4:
            return ({}, {}, {2}, {2, 3})[N]
        Nsq = int(N ** 0.5 + 0.5) + 1
        primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
        for i in range(5, Nsq, 2):
            if i in primes:
                primes -= set(range(i * i, N + 1, i * 2))
        return list(primes)

    def factorization(n, prime_set):
        l = []
        tmp = n
        nsq = int(n ** 0.5 + 0.5) + 1
        for i in prime_set:
            if  i > nsq: 
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                l.append(i)
        if tmp != 1:
            l.append(tmp)
        if l == []:
            if n != 1:
                l.append(n)
        return l
    n = int(input())
    A = [int(x) for x in input().split()]
    len_A = len(A)
    # setwise coprimeの条件(1ならOK)
    g = 0
    for a in A:
        g = gcd(g, a)
    # 素数列挙
    num = 10**6+1
    primes = prime_set(num)
    # 全部素因数分解
    prime_list = [0] * (num+1)
    pairwise_f = True
    ll = list()
    for a in A:
        l = []
        tmp = a
        # nsq = int(a ** 0.5 + 0.5) + 1
        for i in primes:
            if  i*i > a:
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                prime_list[i] += 1
                l.append(i)
        if tmp != 1:
            prime_list[tmp] += 1
            l.append(tmp)
        if l == []:
            if a != 1:
                prime_list[n] += 1
                l.append(a)
        set_prime_list = set(prime_list)
        if len_A > 10**5:
            if set_prime_list != set([0]) and set_prime_list != set([0, 1]):
                pairwise_f = False
                break
    # print(prime_list[:100])
    if set_prime_list != set([0]) and set_prime_list != set([0, 1]):
        pairwise_f = False
    if pairwise_f:
        print('pairwise coprime')
    elif g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    from itertools import chain
    import sys
    input = sys.stdin.readline

    def gcd(x, y):
        if y == 0:
            return x
        return gcd(y, x % y)
    # 6n+1, 6n-1でも求めて、素数**2+素数*kはふるいおとす
    def prime_set(N):
        """
        Nまでの素数のsetを返す
        """
        if N < 4:
            return ({}, {}, {2}, {2, 3})[N]
        Nsq = int(N ** 0.5 + 0.5) + 1
        primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
        for i in range(5, Nsq, 2):
            if i in primes:
                primes -= set(range(i * i, N + 1, i * 2))
        return list(primes)

    def factorization(n, prime_set):
        l = []
        tmp = n
        nsq = int(n ** 0.5 + 0.5) + 1
        for i in prime_set:
            if  i > nsq: 
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                l.append(i)
        if tmp != 1:
            l.append(tmp)
        if l == []:
            if n != 1:
                l.append(n)
        return l
    n = int(input())
    A = [int(x) for x in input().split()]

    # setwise coprimeの条件(1ならOK)
    g = 0
    for a in A:
        g = gcd(g, a)
    # 素数列挙
    num = 10**6+1
    primes = prime_set(num)
    # 全部素因数分解
    prime_list = [0] * (num+1)
    pairwise_f = True
    ll = list()
    for a in A:
        l = []
        tmp = a
        # nsq = int(a ** 0.5 + 0.5) + 1
        for i in primes:
            if  i*i > a:
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                prime_list[i] += 1
                l.append(i)
        if tmp != 1:
            prime_list[tmp] += 1
            l.append(tmp)
        if l == []:
            if a != 1:
                prime_list[n] += 1
                l.append(a)
        set_prime_list = set(prime_list)
        if set_prime_list != set([0]) and set_prime_list != set([0, 1]):
            pairwise_f = False
            break
    # print(prime_list[:100])
    if pairwise_f:
        if set_prime_list != set([0]) and set_prime_list != set([0, 1]):
            pairwise_f = False
    if pairwise_f:
        print('pairwise coprime')
    elif g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    from itertools import chain
    import sys
    input = sys.stdin.readline

    def gcd(x, y):
        if y == 0:
            return x
        return gcd(y, x % y)
    # 6n+1, 6n-1でも求めて、素数**2+素数*kはふるいおとす
    def prime_set(N):
        """
        Nまでの素数のsetを返す
        """
        if N < 4:
            return ({}, {}, {2}, {2, 3})[N]
        Nsq = int(N ** 0.5 + 0.5) + 1
        primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
        for i in range(5, Nsq, 2):
            if i in primes:
                primes -= set(range(i * i, N + 1, i * 2))
        return list(primes)

    def factorization(n, prime_set):
        l = []
        tmp = n
        nsq = int(n ** 0.5 + 0.5) + 1
        for i in prime_set:
            if  i > nsq: 
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                l.append(i)
        if tmp != 1:
            l.append(tmp)
        if l == []:
            if n != 1:
                l.append(n)
        return l
    n = int(input())
    A = [int(x) for x in input().split()]

    # setwise coprimeの条件(1ならOK)
    g = 0
    for a in A:
        g = gcd(g, a)
    # 素数列挙
    num = 10**6+1
    primes = prime_set(num)
    # 全部素因数分解
    prime_list = [0] * (num+1)
    pairwise_f = True
    ll = list()
    for a in A:
        l = []
        tmp = a
        # nsq = int(a ** 0.5 + 0.5) + 1
        for i in primes:
            if  i*i > a:
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                prime_list[i] += 1
                l.append(i)
        if tmp != 1:
            prime_list[tmp] += 1
            l.append(tmp)
        if l == []:
            if a != 1:
                prime_list[n] += 1
                l.append(a)
    # print(prime_list[:100])
    set_prime_list = set(prime_list)
    if set_prime_list != set([0]) and set_prime_list != set([0, 1]):
        pairwise_f = False
    if pairwise_f:
        print('pairwise coprime')
    elif g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    from itertools import chain
    import sys
    input = sys.stdin.readline

    def gcd(x, y):
        if y == 0:
            return x
        return gcd(y, x % y)
    # 6n+1, 6n-1でも求めて、素数**2+素数*kはふるいおとす
    def prime_set(N):
        """
        Nまでの素数のsetを返す
        """
        if N < 4:
            return ({}, {}, {2}, {2, 3})[N]
        Nsq = int(N ** 0.5 + 0.5) + 1
        primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
        for i in range(5, Nsq, 2):
            if i in primes:
                primes -= set(range(i * i, N + 1, i * 2))
        return list(primes)

    def factorization(n, prime_set):
        l = []
        tmp = n
        nsq = int(n ** 0.5 + 0.5) + 1
        for i in prime_set:
            if  i > nsq: 
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                l.append(i)
            i += 1
        if tmp != 1:
            l.append(tmp)
        if l == []:
            if n != 1:
                l.append(n)
        return l
    n = int(input())
    A = [int(x) for x in input().split()]

    # setwise coprimeの条件(1ならOK)
    g = 0
    for a in A:
        g = gcd(g, a)
    # 素数列挙
    primes = prime_set(10**6+1)
    # 全部素因数分解
    af = list()
    pairwise_f = True
    for a in A:
        f = factorization(a, primes)
        af = af + f
    if len(af) != len(set(af)):
        pairwise_f = False
    if pairwise_f:
        print('pairwise coprime')
    elif g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()