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:
from math import gcd

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2
#prime_num が用意されているとき
primecounter = [0 for _ in range(len(primenum))]
biggerprime = []
def factorization(n):
  M = n
  for k in range(len(primenum)):
    p = primenum[k]
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if primecounter[k] == 0:
          primecounter[k] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if M not in biggerprime:
      biggerprime.append(M)
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)
  if flag == False:
    if g == 1:
      break


if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math 
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
ans = ["pairwise coprime", "setwise coprime ", "not coprime"]

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
if gcd_list(A) != 1:
  print(ans[2])
  quit()
  
def seachPrimeNum(N):
    max = int(N ** (1 / 2))
    D = [0] * N
    D[0] = 1
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        nn = seachList[0]
        D[nn - 1] = nn
        primeNum.append(nn)
        tmp = nn
        for i in seachList:
          if i != nn:
            if i % tmp == 0:
              D[i - 1] = nn
        seachList = [i for i in seachList if i % tmp != 0]
    for i in seachList:
      D[i - 1] = i
    primeNum.extend(seachList)
    
    return primeNum, D  
  
primeNum, D = seachPrimeNum(1000000)
used = [0] * len(primeNum)

for i in range(N):
  now = A[i]
  q = [now]
  #print(now, D[now - 1])
  while now != D[now - 1]:
    now = int(now / D[now - 1])
    if now in primeNum:
      q.append(now)
  for i in q:
    if i in primeNum:
      if used[primeNum.index(i)] == 0:
        used[primeNum.index(i)] = 1
      else:
        print(ans[1])
        quit()  

print(ans[0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


n = int(input())
arr = np.array(list(map(int, input().split())))


def solve(arr):
    cnt = np.bincount(arr)
    return np.all([cnt[i::i].sum() <= 1 for i in range(2, 10**6+1)])


ans1 = solve(arr)
ans2 = np.gcd.reduce(arr) == 1

if ans1 and ans2:
    print("pairwise coprime")
elif ans2:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

def sieve(n):
    A = list(range(n+1))
    for i in range(2, n+1 ,2):
        A[i] = 2
    for j in range(3, ceil(sqrt(n+1))+1, 2)[::-1]:
        for i in range(j, n+1, j):
            A[i] = j
    return A

def factorize(n, A):
    factors = set()
    while n != 1:
        f = A[n]
        factors.add(f)
        n //= f
    return factors

_, *aa = map(int, open(0).read().split())

def main(aa):
    pair_co = True
    max_factors = set()
    A = sieve(10**6)
    for a in aa:
        factors = factorize(a, A)
        new_max_factors = max_factors | factors
        if len(new_max_factors) < len(max_factors) + len(factors):
            pair_co = False
            break
        max_factors = new_max_factors
    if pair_co:
        return 'pairwise coprime'
    elif reduce(gcd, aa) == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'

print(main(aa))

Submission status: Time Limit Exceeded

Solution code:
primes = [0 for i in range(10**6 + 5)]
idx = 0
ps=[0 for i in range(10**6)]
 
for i in range(2,len(primes)):
    if primes[i] == 0:
        ps[idx] = i
        idx +=1
        j = i+i
        while j <len(primes):
            primes[j] = 1
            j+=i
 
# print(ps[:100])
 
n=int(input())
arr=[int(c) for c in input().split()]
pariwise = True
setWise = True
ct = 0
 
for i in range(idx):
    prime = ps[i]
    # print(prime)
    count = 0
    for j in arr:
        if j%prime == 0:
            count+=1
    
    if count == n:
        setWise = False
    if count > 1:
        pariwise = False
    if (not setWise) and (not pariwise):
        break
 
if pariwise :
    print("pairwise coprime")
elif not pariwise and setWise:
    print("setwise coprime") 
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
a=list(map(int, input().split()))

c=[0]*max(a)
for i in range(n): 
    m=a[i]
    pf={}
    for j in range(2,int(m**0.5)+1):
        while m%j==0:
            pf[j]=pf.get(j,0)+1
            m//=j
    if m>1:pf[m]=1

    for k in pf:
        c[k-1]+=1
        
maxcount=max(c)

if np.gcd.reduce(a) != 1:
    print('not coprime')
elif maxcount <= 1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math 
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
ans = ["pairwise coprime", "setwise coprime ", "not coprime"]

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
if gcd_list(A) != 1:
  print(ans[2])
  quit()
  
def seachPrimeNum(N):
    max = int(N ** (1 / 2))
    D = [0] * N
    D[0] = 1
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        nn = seachList[0]
        D[nn - 1] = nn
        primeNum.append(nn)
        tmp = nn
        for i in seachList:
          if i != nn:
            if i % tmp == 0:
              D[i - 1] = nn
        seachList = [i for i in seachList if i % tmp != 0]
    for i in seachList:
      D[i - 1] = i
    primeNum.extend(seachList)
    
    return primeNum, D  
  
primeNum, D = seachPrimeNum(1000000)
used = [0] * len(primeNum)

for i in range(N):
  now = A[i]
  q = []
  #print(now, D[now - 1])
  if now in primeNum:
    q.append(now)
  while now != D[now - 1]:
    now = int(now / D[now - 1])
    if now in primeNum:
      q.append(now)
  for i in q:
    if used[primeNum.index(i)] == 0:
      used[primeNum.index(i)] = 1
    else:
      print(ans[1])
      quit()  

print(ans[0])

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

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

flag = True
c2 = 0
c3 = 0
c5 = 0
for k in range(N):
  if A[k] %2 ==0:
    c2 += 1
    if c2 > 1:
      flag = False
      break
  elif A[k] %3 ==0:
    c3 += 1
    if c3 > 1:
      flag = False
      break
  elif A[k] %5 == 0:
    c5 += 1
    if c5 >1:
      flag = False
      break

if flag:
  mA = max(A)
  counter = [0 for _ in range(mA+1)]

  primenum = [2]
  sgn = [-1 for _ in range(int(mA**0.5)+1)]
  k = 3
  while k**2 <= mA:
    if sgn[k] == -1:
      primenum.append(k)
      add = k*k
      ok = k
      while ok**2 <= mA:
        sgn[ok] = 1
        ok += add
    k += 2
  #prime_num が用意されているとき
  def factorization(n):
    M = n
    for p in primenum:
      if p**2 > M:
        break
      else:
        if M%p == 0:
          if counter[p] == 0:
            counter[p] = 1
          else:
            return False
          while M%p == 0:
            M //= p

    if M > 1:
      if counter[M] == 0:
        counter[M] = 1
      else:
        return False
    return True

g = A[0]
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)
  if flag == False:
    if g == 1:
      break


if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce


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


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

    tmp = [0] * N

    s = 1
    for i in range(N):
        tmp[- i - 1] = s
        s = lcm(s, A[-i - 1])

    is_pairwise_coprime = True
    for i in range(N - 1):
        if math.gcd(A[i], tmp[i]) != 1:
            is_pairwise_coprime = False

    gcd_ = reduce(math.gcd, A)

    if is_pairwise_coprime:
        print('pairwise coprime')
    elif gcd_ == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
ans2 = a_list[0]
for i in range(1, n):
    ans2 = gcd(ans2, a_list[i])
    if ans2 == 1:
        break

if ans2 != 1:
    print("not coprime")
else:
    flag = 1
    max_a = a_list[n - 1] + 1
    num_flag_list = [True] * max_a
    d_list = list(range(0, max_a))
    d_list[0] = 1
    num_flag_list[0] = num_flag_list[1] = False
    for i in range(2, int(max_a**0.5) + 1):
        if num_flag_list[i]:
            for j in range(i**2, max_a, i):
                if num_flag_list[j] == True:
                    num_flag_list[j] = False
                    d_list[j] = i
    p_set = set()
    for a in a_list:
        if a == 1:
            continue
        temp_p_set = set()
        while True:
            p = d_list[a]
            temp_p_set.add(p)
            a = a // p
            if a == 1:
                break
        if len(p_set & temp_p_set) > 0:
            flag = 0
            break
        else:
            p_set = p_set | temp_p_set
        
    if flag == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import math
    from collections import defaultdict
    def factorization(n):
        # 参考: https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8
        dic = defaultdict(int)
        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
                dic[i] = cnt

        if temp != 1:
            dic[temp] = 1
        if not dic:
            dic[n] = 1

        return set(dic.keys())

    n = int(input())
    a = list(set(map(int, input().split())))
    pair = False
    divisors = factorization(a[0])
    ggcd = a[0]
    for i in range(1, len(a)):
        divs = factorization(a[i])
        nxt = divisors | divs
        if len(nxt) != len(divs) + len(divisors):
            pair = True
            break
        else:
            divisors = nxt
    for i in range(1, len(a)):
        ggcd = math.gcd(ggcd, a[i])
        if ggcd == 1:
            break
    if ggcd != 1:
        print("not coprime")
    else:
        if pair:
            print("setwise coprime")
        else:
            print("pairwise coprime")
resolve()

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
memo=set()
n=input()
g=0
l=list(map(int,input().split()))
for i in l:
    g=gcd(i,g)
if g!=1:print('not coprime');exit()

for i in l:
    for p in primeFactor(i):
        if p in memo:print("setwise coprime");exit()
        memo.add(p)
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from collections import deque
# = map(int, input().split())
N = int(input())
A = deque(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]
primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2
#prime_num が用意されているとき
def factorization(n):
  M = n
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if counter[p] == 0:
          counter[p] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A.popleft()
  g = gcd(g, a)
  if flag:
    flag = factorization(a)
  if flag == False:
    if g == 1:
      break


if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

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

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

                divisors.append(n//i)

    divisors.sort()
    return divisors

    


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

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
S=[]
tmp=gcd_list(T)
if tmp!=1:
    print("not coprime")
else:
    T.sort()

    n=10**6+1
    isprime=[True]*(n+1)
    isprime[0]=False
    isprime[1]=False
    for i in range(len(T)):
        S=make_divisors(T[i])
        #print(S)
        while len(S)!=0: 
            tmp=S.pop()
            if isprime[tmp]==True:
                j=tmp+tmp
                while j<=n:
                     
                    isprime[j] =False
                    j=j+tmp
                    
                        
            else:
                print("setwise coprime")
                exit()
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import math
    def divisor(n):
        ass = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                if i != 1:
                    ass.append(i)
                if i ** 2 == n:
                    continue
                ass.append(n // i)
        return ass

    n = int(input())
    a = list(map(int, input().split()))
    a = list(set(a))
    a = sorted(a)
    pair = False
    divisors = set(divisor(a[0]))
    ggcd = a[0]
    for i in range(1, len(a)):
        divs = set(divisor(a[i]))
        nxt = divisors | divs
        if len(nxt) != len(divs) + len(divisors):
            pair = True
            break
        else:
            divisors = nxt
    for i in range(1, len(a)):
        ggcd = math.gcd(ggcd, a[i])
        if ggcd == 1:
            break
    if ggcd != 1:
        print("not coprime")
    else:
        if pair:
            print("setwise coprime")
        else:
            print("pairwise coprime")

resolve()

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import defaultdict


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


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A_max = max(A)

    is_pairwise_coprime = True

    D = [-1] * (A_max + 1)
    for i in range(2, A_max + 1):
        if D[i] == -1:
            D[i] = i
            for j in range(i*i, A_max+1, i):
                D[j] = i

    def factorization(n):
        # assert 0 < n <= A_max
        primes_ = defaultdict(int)
        temp = n
        while temp > 1:
            primes_[D[temp]] += 1
            temp = temp // D[temp]

        return primes_

    P = [False]*(A_max+1)

    # primes = set({})
    for i in range(N):
        for p in factorization(A[i]).keys():
            # if p in primes:
            if P[p]:
                is_pairwise_coprime = False
                break
            else:
                # primes.add(p)
                P[p] = True

    gcd_ = reduce(math.gcd, A)

    if is_pairwise_coprime:
        print('pairwise coprime')
    elif gcd_ == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]

primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2
#prime_num が用意されているとき
def factorization(n):
  M = n
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if counter[p] == 0:
          counter[p] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)
  if flag == False:
    if g == 1:
      break


if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

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

#pairwiseかどうかを調べる
primes = []
def primeFinder(n):
    memo = [1]*(n+1)
    memo[0] = 0
    memo[1] = 0
    for i in range(2,n+1):
        if memo[i] == 1:
            primes.append(i)
            for j in range(i*2,n+1,i):
                memo[j] = 0

primeFinder(10**6)
primes = {p:0 for p in primes}
"""
各Aiに関して素因数を算出。素因数を集計してカウントが2つある素因数がなければpairwise
"""
flag = True
for i in range(N):
    a = A[i]
    memo = []
    for d in primes.keys():
        if a%d == 0:
            memo.append(d)
            while a % d == 0:
                a //= d
    for d in memo:
      primes.pop(d)
    if a != 1:
        break
else:
    print("pairwise coprime")
    exit()


#setwise coprimeを判断
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict


def first_prime_list(N):
    D = [1] * (N + 1)

    for i in range(2, N + 1):
        if D[i] != 1:
            continue
        for j in range(1, N // i + 1):
            if D[i * j] == 1:
                D[i * j] = i

    return D


def factorization_with_fpl(A, D):

    Ps = defaultdict(int)
    current_p = D[A]

    while D[A] > 1:
        cnt = 0
        while D[A] == current_p:
            A = A // D[A]
            cnt += 1

        Ps[current_p] = cnt
        current_p = D[A]

    if A != 1:
        Ps[A] = 1

    return Ps


N = int(sys.stdin.readline().rstrip())
A = [int(x) for x in sys.stdin.readline().rstrip().split()]

D = first_prime_list(max(A))

pc = True
sp = True

maxlist = factorization_with_fpl(A[0], D)

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

for i in range(1, N):
    d = factorization_with_fpl(A[i], D)
    for p in d.keys():
        if min(maxlist[p], d[p]) != 0:
            pc = False
        maxlist[p] = max(maxlist[p], d[p])

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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import math
    def divisor(n):
        ass = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                if i != 1:
                    ass.append(i)
                if i ** 2 == n:
                    continue
                ass.append(n // i)
        return ass

    n = int(input())
    a = list(map(int, input().split()))
    a = list(set(a))
    a = sorted(a)
    pair = False
    divisors = set(divisor(a[0]))
    ggcd = a[0]
    for i in range(1, len(a)):
        divs = set(divisor(a[i]))
        if len(divs & divisors) != 0:
            pair = True
            break
        else:
            divisors = divisors | divs
    for i in range(1, len(a)):
        ggcd = math.gcd(ggcd, a[i])
        if ggcd == 1:
            break
    if ggcd != 1:
        print("not coprime")
    else:
        if pair:
            print("setwise coprime")
        else:
            print("pairwise coprime")
resolve()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]

primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2
#prime_num が用意されているとき
def factorization(n):
  M = n
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if counter[p] == 0:
          counter[p] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)


if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

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]


def main():
    n = int(input())
    a = list(map(int, input().split()))
    num = [0]*(10**6 + 1)
    for i in range(n):
        d = make_divisors(a[i])
        for j in range(len(d)):
            num[d[j]] += 1
    flag1 = False
    flag2 = False
    for i in range(2, len(num)):
        if num[i] == num[1]:
            flag1 = True
        if num[i] > 1:
            flag2 = True

    if flag1 and flag2:
        ans = 'not coprime'
    elif flag2:
        ans = 'setwise coprime'
    else:
        ans = 'pairwise coprime'

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
ma=a[-1]
pn=[i for i in range(ma+1)]
for i in range(2,ma//2+1):
  j=2
  while j*i<=ma:
    pn[j*i]=i
    j+=1
chk=[0]*(ma+1)
for i in a:
  if i==1:
    continue
  x=pn[i]
  chk[x]+=1
  while x!=i:
    while i%x==0:
      i//=x
    x=pn[i]
    chk[x]+=1
ans=2
for i in chk:
  if i==n:
    ans=0
    break
  if i>=2:
    ans=1
if ans==2:
  print('pairwise coprime')
elif ans==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import math

    def primes(n):
        ass = []
        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
        for i in range(len(is_prime)):
            if is_prime[i]:
                ass.append(i)
        return ass

    def divisor(n):
        ass = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                if i != 1:
                    ass.append(i)
                if i ** 2 == n:
                    continue
                ass.append(n // i)
        return ass

    n = int(input())
    a = list(map(int, input().split()))
    a = list(set(a))
    pair = False
    divisors = set(divisor(a[0]))
    ggcd = a[0]
    for i in range(1, len(a)):
        divs = set(divisor(a[i]))
        if len(divs & divisors) != 0:
            pair = True
            break
        else:
            divisors = divisors | divs
    for i in range(1, len(a)):
        ggcd = math.gcd(ggcd, a[i])
        if ggcd == 1:
            break
    if ggcd != 1:
        print("not coprime")
    else:
        if pair:
            print("setwise coprime")
        else:
            print("pairwise coprime")
resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
from collections import defaultdict


def first_prime_list(N):
    D = [1] * (N + 1)

    for i in range(2, N + 1):
        if D[i] != 1:
            continue
        for j in range(1, N // i + 1):
            if D[i * j] == 1:
                D[i * j] = i

    return D


def factorization_with_fpl(A, D):

    Ps = defaultdict(int)
    current_p = D[A]

    while D[A] > 1:
        cnt = 0
        while D[A] == current_p:
            A = A // D[A]
            cnt += 1

        Ps[current_p] = cnt
        current_p = D[A]

    if A != 1:
        Ps[A] = 1

    return Ps


N = int(sys.stdin.readline().rstrip())
A = [int(x) for x in sys.stdin.readline().rstrip().split()]

D = first_prime_list(max(A))

pc = True
sp = True

maxlist = factorization_with_fpl(A[0], D)
minlist = factorization_with_fpl(A[0], D)

arrA = np.array(A)

for i in range(1, N):
    d = factorization_with_fpl(A[i], D)
    for p in d.keys():
        if min(maxlist[p], d[p]) != 0:
            pc = False
        maxlist[p] = max(maxlist[p], d[p])

    for p in minlist.keys():
        minlist[p] = min(minlist[p], d[p])
    

for p in minlist.keys():
    if minlist[p] != 0:
        sp = False


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

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
        if k: ret[i] = k
        i += 1 + i % 2
    if n > 1: return {n}
    return set(ret)
def main():
  N=int(input())
  L=list(map(int,input().split()))
  gc=L[0]
  for i in L:
    gc=gcd(i,gc)
    if gc==1:
      break
  if gc!=1:
    print("not coprime")
    exit()
  ans=set()
  c=0
  for i in L:
    c+=len(primeFactor(i))
    ans|=set(primeFactor(i))
  if c==len(ans):
    print("pairwise coprime")
  else:
    print("setwise coprime")
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


n = int(input())
arr = np.array(list(map(int, input().split())))


n = 10**3 + 1
primes = set(range(3, n+1, 2))

for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes.add(2)

used = [False] * 1002
ans1 = True
flg = False
for x in arr:
    for p in primes:
        while x > 1 and x % p == 0:
            if used[p]:
                ans1 = False
                flg = True
                break
            while x % p == 0:
                x //= p
            used[p] = True
        if flg:
            break
    if flg:
        break


ans2 = np.gcd.reduce(arr) == 1

if ans1 and ans2:
    print("pairwise coprime")
elif ans2:
    print("setwise coprime")
else:
    print("not coprime")