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 bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5)
        data = []
        for i in range(2, n + 1):
            data.append(i)
            D[i] = i

        while data[0]:
            p = data[0]
            if limit <= p:
                return D
            k = n // p
            for j in range(1, k + 1):
                s = p * j
                D[s] = p
                del s
        return D



    N = I()
    A = LI()
    D = defaultdict()
    num_list = [0] * (10 ** 6 + 1)

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()

    A_ = set(A)
    A_.discard(1)
    if len(A_) >= 90000:
        print("setwise coprime")
        exit()

    max_a = max(A)
    if max_a == 1:
        print('pairwise coprime')
        exit()
    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        while a != 1:
            x = D[a]
            if num_list[x] == 1:
                print('setwise coprime')
                exit()
            num_list[x] = 1
            a //= x

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from math import gcd
from functools import reduce
from collections import Counter


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def sieve(n):
    """
    n以下の素数を昇順に列挙する
    """
    is_prime = [True for i in range(n+1)]
    primes = []
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, n+1, i):
                is_prime[j] = False
    return primes


def solve(N, A):
    primes = Counter(sieve(10**6))
    for a in A:
        for p in primes:
            if a < p:
                break
            q = a // p
            if q * p == a:
                primes[p] += 1
    if primes.most_common()[0][1] <= 2:
        return "pairwise coprime"
    if reduce(gcd, A) == 1:
        return "setwise coprime"
    return "not coprime"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

N=int(input())
A=list(map(int,input().split()))
ans=["pairwise coprime","setwise coprime","not coprime"]
factor={}
cond=True
g=A[0]
a=0
D=[_ for _ in range(max(A)+1)]

for i in range(2,int(max(A)**0.5)+1):
    n=i
    while i*n<=max(A):
        D[i*n]=i
        n+=1

for i in range(N):
    g=gcd(g,A[i])

    temp=A[i]
    while cond and temp!=D[temp]:
        if D[temp] in factor:
            cond=False
        else:
            factor[D[temp]]=1
            temp//=D[temp]

if g>1:
    a=2
elif not cond:
    a=1
print(ans[a])

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

N=int(input())
A=list(map(int,input().split()))
ans=["pairwise coprime","setwise coprime","not coprime"]
factor={}
cond=True
g=A[0]
a=0
D=[_ for _ in range(max(A)+1)]

for i in range(2,int(max(A)**0.5)+1):
    n=i
    while i*n<=max(A):
        D[i*n]=i
        n+=1

for i in range(N):
    g=gcd(g,A[i])

    temp=A[i]
    while cond and temp!=D[temp]:
        if D[temp] in factor:
            cond=False
        else:
            factor[D[temp]]=1
            temp=D[temp]

if g>1:
    a=2
elif not cond:
    a=1
print(ans[a])

Submission status: Time Limit Exceeded

Solution code:
import math

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

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
    while search_list[0] <= math.sqrt(number):
        #search_listの先頭の値が√nの値を超えたら終了
        #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        for i in range(number // head_num):
            if D[head_num * (i + 1)] == -1:
                D[head_num * (i + 1)] = head_num
        search_list = [num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list


def factrization_prime(number):
    div = D[number]
    s = math.sqrt(number)
    while div <= s:
        div_cnt = 0
        while number % div == 0:
            div_cnt += 1
            number //= div
        ans_array[div] += 1
        if number == 1:
            break
        div = D[number]
    if number > 1:
        ans_array[number] += 1

thre = pow(10, 6) + 1
ans_array = [0] * thre
D = [-1] * (thre + 1)

prime_list = get_primenumber(thre)
for a in a_array:
    factrization_prime(a)

max_ans_array = max(ans_array)
if max_ans_array == 1:
    print('pairwise coprime')
elif max_ans_array < n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

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

m=10**6+4
d=[0]*m

dic=Counter(a)
for i,val in dic.items(): d[i]=val
flag2=0
for i in range(2,max(a)):
    flag=0
    for j in range(i,m,i):
        if d[j] and flag:
            flag2=1
            break
        elif d[j]: flag=1

s=a[0]
for i in a:
    s=gcd(s,i)
    
if not flag2: print("pairwise coprime")
elif s==1: print("setwise coprime")
else: print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

N=int(input())
A=list(map(int,input().split()))
ans=["pairwise coprime","setwise coprime","not coprime"]
factor={}
cond=False
g=A[0]
a=0
for i in range(N):
    g=gcd(g,A[i])

    for j in range(2,int(A[i])+1):
        if A[i]%j==0:
            if j not in factor:
                factor[j]=1
            else:
                cond=True

if g>1:
    a=2
elif cond:
    a=1
print(ans[a])

Submission status: Time Limit Exceeded

Solution code:
import math

def primes(n):
    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]]

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

Ps = primes(10 ** 6)
n = int(input())
As = list(map(int, input().split()))

# setwiseFlag
gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)

# pairwiseFlag
pairwiseFlag = True
for p in Ps:
  count = 0
  for _p in range(p, 10 ** 6 + 1, p):
    if _p in As:
      count += 1
  if count > 1:
    pairwiseFlag = False

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import math

def divisors(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table


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

fd = set([1])
flag = 'pairwise coprime'

mimm = min(ab)


for a in ab:
    if fd & set(divisors(a)) != {1}:
        flag = 'setwise coprime'
        break
    fd = fd | set(divisors(a))

if flag ==  'setwise coprime':
    flag = 'not coprime'
    for a in ab:
        mimm =  math.gcd(mimm,a)
        if mimm  == 1:
            flag ='setwise coprime'
            break
        
print(flag)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
A=list(map(int,input().split()))
# cnt=[0]*(10**6+1)
cnt=np.zeros(10**6+1, dtype='int')
for a in A:cnt[a]+=1
 
if np.gcd.reduce(A)!=1:
  print("not coprime")
elif np.all([sum(cnt[i::i])<=1 for i in range(2,10**6+1)]):
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
def divisors(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

def divisor(n,m): 
    i = 1
    table = []
    while i * i <= max(n,m):
        if n%i == 0 & m%i == 0:
            table.append(i)
            table.append(n//i)
            table.append(m//i)
        i += 1
    table = list(set(table))
    return table
  
n = int(input())
ab = list(map(int, input().split()))

fd = set([1])
flag = 'pairwise coprime'

mimm = set(divisors(min(ab)))


for a in ab:
    if fd & set(divisors(a)) != {1}:
        flag = 'setwise coprime'
        break
    fd = fd | set(divisors(a))

if flag ==  'setwise coprime':
    flag = 'not coprime'
    for a in ab:
        mimm =  mimm & set(divisors(a))
        if mimm  == {1}:
            flag ='setwise coprime'
            break
        
print(flag)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from math import floor
from collections import defaultdict

def eratosthenes(n):
    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]]


def factorize(N):  # 素因数分解
    prime = set()
    for p in prime_list:
        if p * p > N:
            break
        while N % p == 0:
            N //= p
            prime.add(p)
    if N > 1:
        prime.add(N)
    return prime


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

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

prime_list = eratosthenes(10 ** 6)
num = set()

class PrimeFactorization:
    '''1つの因数分解クエリをO(log(k))で実行する（初期化にO(N))
    >>> pf = PrimeFactorization(100)
    >>> pf.query(100)
    ((2, 2), (5, 2))
    
    '''
    # https://atcoder.jp/contests/abc177/editorial/82
    # 高速素因数分解
    # 問題： A 以下の数が N 個与えられる。全て素因数分解せよ。
    # 前計算としてエラトステネスの篩を行い、「その数をふるい落とした素数」を配列 D に記録します。
    # 例えば D[4]=D[6]=2,D[35]=5 です。x が素数のときは D[x]=x としておきます。この配列はエラトステネスの篩と同様 O(AloglogA) で構築できます。
    # D[x] は x を割り切る最小の素数なので、この配列 D を利用すると素因数分解を行うときに「試し割り」をする必要がなくなり(D[x]で割ればよい)、1つの数の素因数分解が素因数の個数である O(logA) でできるようになります。
    from collections import defaultdict
    def __init__(self, Num=10**6):
        self.Num = Num
        self.D = [-1] * (Num+1)
        for i in range(2, Num+1):
            if self.D[i] != -1:
                continue
            self.D[i] = i
            for j in range(1, floor(Num/i)+1):
                if self.D[j*i] != -1:
                    continue
                else:
                    self.D[j*i] = i
    
    def query(self, k):
        ans = defaultdict(int)
        tmp = k
        while self.D[tmp] != -1:
            div = self.D[tmp]
            ans[div] += 1
            tmp = tmp//div
        return set(ans.keys())
      
pf = PrimeFactorization(10**6)
for ai in a:
    prime = pf.query(ai)
    # prime = factorize(ai)
    if len(prime & num) > 0:
        print('setwise coprime')
        break
    num |= prime
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math

def primes(n):
    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]]

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

Ps = primes(10 ** 6)
n = int(input())
As = list(map(int, input().split()))

# setwiseFlag
gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)

# pairwiseFlag
pairwiseFlag = True
target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target |= primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
aa = np.array(input().split(), dtype='int')
ma = np.max(aa)
cnt = np.zeros(max(aa)+1, dtype='int')

for a in aa:
    cnt[a] += 1

if np.gcd.reduce(aa) != 1:
    print('not coprime')

elif np.all([cnt[i::i].sum() <= 1 for i in range(2, ma)]):
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math

input()
d = None
u = set()
r = 'pairwise'
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  s = set()
  i = 2
  while i * i <= x:
    while x % i == 0:
      if i in u:
        r = 'setwise'
      s.add(i)
      x //= i
    i += 1
  if x > 1:
    if x in u:
      r = 'setwise'
    s.add(x)
  u |= s
print((r, 'not')[d > 1], 'coprime')

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
def divisors(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

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

fd = set([1])
flag = 'pairwise coprime'

mimm = set(divisors(min(ab)))


for a in ab:
    if fd & set(divisors(a)) != {1}:
        flag = 'setwise coprime'
    fd = fd | set(divisors(a))

if flag ==  'setwise coprime':
    flag = 'not coprime'
    for a in ab:
        mimm =  mimm & set(divisors(a))
        if mimm  == {1}:
            flag ='setwise coprime'
            break
        
print(flag)

Submission status: Time Limit Exceeded

Solution code:
import math

def pf(n):
  s = set()
  i = 2
  while i * i <= n:
    while n % i == 0:
      s.add(i)
      n //= i
    i += 1
  if n > 1:
    s.add(n)
  return s

input()
d = None
u = set()
r = 'pairwise'
for x in map(int, input().split()):
  d = math.gcd(d or x, x)
  s = pf(x)
  if not s.isdisjoint(u):
    r = 'setwise'
  u |= s
print((r, 'not')[d > 1], 'coprime')

Submission status: Time Limit Exceeded

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

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

    def factorize(n):
        d = set()
        m = 2
        while m*m <= n:
            while n%m == 0:
                n //= m
                d.add(m)
            m += 1
        if n > 1:
            d.add(n)
        return d

    st = set()
    for a in A:
        fac = factorize(a)
        if fac & st:
            print('setwise coprime')
            exit()
        st |= fac
    print('pairwise coprime')
solve()

Submission status: Time Limit Exceeded

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

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

def factorize(n):
    d = set()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d.add(m)
        m += 1
    if n > 1:
        d.add(n)
    return d

st = set()
for a in A:
    fac = factorize(a)
    if fac & st:
        print('setwise coprime')
        exit()
    st |= fac
print('pairwise coprime')

Submission status: Time Limit Exceeded

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

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

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

ctr = Counter()
for a in A:
    fac = factorize(a)
    if fac & ctr:
        print('setwise coprime')
        exit()
    ctr |= fac
print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

# cons = 10 ** 6
# is_prime = [True] * (cons + 1)
# is_prime[0] = False
# is_prime[1] = False
# for i in range(2, int(cons**0.5) + 1):
#     if not is_prime[i]:
#         continue
#     for j in range(i * 2, cons + 1, i):
#         is_prime[j] = False
# Ps = [i for i in range(cons + 1) if is_prime[i]]
def eratosthenes(n):
    is_prime = [0, 0] + [1] * (n - 1)
    for i in range(int(n**0.5) + 1):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return [i for i, pi in enumerate(is_prime) if pi == 1]
Ps = eratosthenes(10 ** 6)

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

gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)

pairwiseFlag = True
target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target = target | primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

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

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

    from collections import Counter
    def factorize(n):
        d = Counter()
        m = 2
        while m*m <= n:
            while n%m == 0:
                n //= m
                d[m] += 1
            m += 1
        if n > 1:
            d[n] += 1
        return d

    ctr = Counter()
    for a in A:
        fac = factorize(a)
        if fac & ctr:
            print('setwise coprime')
            exit()
        ctr |= fac
    print('pairwise coprime')
solve()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

# cons = 10 ** 6
# is_prime = [True] * (cons + 1)
# is_prime[0] = False
# is_prime[1] = False
# for i in range(2, int(cons**0.5) + 1):
#     if not is_prime[i]:
#         continue
#     for j in range(i * 2, cons + 1, i):
#         is_prime[j] = False
# Ps = [i for i in range(cons + 1) if is_prime[i]]
def eratosthenes(n):
    is_prime = [0, 0] + [1] * (n - 1)
    for i in range(int(n**0.5) + 1):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return [i for i, pi in enumerate(is_prime) if pi == 1]
Ps = eratosthenes(10 ** 6)
def factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

gcd = As[0]
for i in range(1, n):
  gcd = math.gcd(gcd, As[i])
setwiseFlag = (gcd == 1)

pairwiseFlag = True
target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target = target | primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    
    def prime_factorize(n):
        r = set()
        while n % 2 == 0:
            r.add(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                r.add(f)
                n //= f
            else:
                f += 2
        if n != 1:
            r.add(n)
        return set(r)
    
    
    j = 0
    a1 = set()
    a2 = prime_factorize(A[0])
    for a in A[1:]:
        tmp = prime_factorize(a)
        if a1 & tmp:
            j = 1
        a1 |= tmp
        a2 &= tmp
    if a2:
        print('not coprime')
    elif j:
        print('setwise coprime')
    else:
        print('pairwise coprime')


main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

cons = 10 ** 6
is_prime = [True] * (cons + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(cons**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, cons + 1, i):
        is_prime[j] = False
Ps = [i for i in range(cons + 1) if is_prime[i]]

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

pairwiseFlag = True

gcd = As[0]
for i in range(1, n):
  gcd = math.gcd(gcd, As[i])
setwiseFlag = (gcd == 1)

target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target = target | primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

cons = 10 ** 6
is_prime = [True] * (cons + 1)
Ds = [i for i in range(cons + 1)]
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(cons**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, cons + 1, i):
        is_prime[j] = False
        if Ds[j] == j:
          Ds[j] = i
Ps = [i for i in range(cons + 1) if is_prime[i]]

def factorize(N):  # 素因数分解
    PRIME = set()
    for p in Ps:
        if p * p > N:
            break
        while N % p == 0:
            N //= p
            PRIME.add(p)
    if N > 1:
        PRIME.add(N)
    return PRIME

pairwiseFlag = True

gcd = As[0]
for i in range(1, n):
  gcd = math.gcd(gcd, As[i])
setwiseFlag = (gcd == 1)

target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target = target | primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

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

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

MAXA = 10**6
B = [0] * (MAXA+1)
for a in A:
    if a==1: continue
    if B[a]:
        print('setwise coprime')
        exit()
    B[a] = 1

for n in range(2,MAXA+1):
    c = 0
    for m in range(n,MAXA+1,n):
        c += B[m]
        if c > 1:
            print('setwise coprime')
            exit()

print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

cons = 10 ** 6
is_prime = [True] * (cons + 1)
Ds = [i for i in range(cons+1)]
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(cons**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, cons + 1, i):
        is_prime[j] = False
        if Ds[j] == j:
          Ds[j] = i 

Ps = [i for i in range(cons + 1) if is_prime[i]]
flags = [[0 for _ in range(n)] for _ in range(len(Ps))]
pairwiseFlag = True
setwiseFlag = True

for ia, a in enumerate(As):
  if a <= 1:
    continue
  while a != 1:
    d = Ds[a]
    i = Ps.index(d)
    flags[i][ia] = 1
    a = a // d
for i in range(len(Ps)):
  s = sum(flags[i])
  if s >= 2:
    pairwiseFlag = False
  if s == n:
    setwiseFlag = False

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'

input()
d = None
p = 1
for x in map(int, input().split()):
  d = gcd(d or x, x)
  e = gcd(p, x)
  if e > 1:
    r = 'setwise'
  p = p // e * x
print((r, 'not')[d > 1], 'coprime')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = [int(a) for a in input().split()]

max_elem = max(arr)
duplicate_mode = False
sett = set([])

for elem in arr:
    if elem in sett and elem != 1:
        duplicate_mode = True
    sett.add(elem)

if not duplicate_mode:
    pos = True
    pos2 = True

    for cand in range(2, max_elem+1):
        cnt = 0
        for cand_ in range(cand, max_elem+1, cand):
            if cand_ in sett:
                cnt += 1

        if cnt == 0 or cnt == 1:
            continue
        elif cnt == len(sett):
            print("not coprime")
            pos2 = False
            break
        else:  # cnt >= 2
           pos &= False

    # if pos:
    #     print("pairwise coprime")
    # else:
    #     if not pos2:
    #         print("setwise coprime")
    #     else:
    #         print("not coprime")

    if pos2:
        if pos:
            print("pairwise coprime")
        else:
            print("setwise coprime")
else:
    pos = True
    for cand in range(2, max_elem+1):
        cnt = 0
        for cand_ in range(cand, max_elem+1, cand):
            if cand_ in sett:
                cnt += 1

        if cnt == len(sett):
            print("not coprime")
            pos = False
            break
    if pos:
        print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
class Sieve:
    """
    N以下の素数を列挙するエラトステネスのふるいです。
    O(NloglogN)でできます。

    Attributes
    sieveList : その数の素因数のうち最小のものの配列
    primes : N以下の素因数のリスト
    """
    def __init__(self, N):
        self.sieveList = [-1 for _ in range(N+1)]
        self.sieveList[1] = 1
        self.primes = []

        for i in range(2, N+1):
            #すでに何らかの数で割られていたらcontinue
            if self.sieveList[i] != -1:
                continue
            self.primes.append(i)
            for j in range(i, N+1, i):
                if self.sieveList[j] != -1:
                    continue
                self.sieveList[j] = i

    def getPrimes(self):
        return self.primes

    def getSieveList(self):
        return self.sieveList

class FastFactorization(Sieve):
    """
    高速素因数分解です。
    与えられたL個の数がA以下の時、
    エラトステネスでO(AloglogA)＋素因数分解でO(LlogA) = O(AloglogA+NlogA)でできます。
    """

    def __init__(self, N):
        """
        前処理でスーパークラスのエラトステネスを使ってN以下の素因数を列挙します。
        """
        super().__init__(N)
        self.N = N
        self.sieveList = self.getSieveList()

    def factorize(self, x):
        if x > self.N:
            raise ValueError("与えられた数がエラトステネスのリストの上限を超えている")
        p = set()
        # p = []
        while x > 1:
            divisor = self.sieveList[x]
            x //= divisor
            p.add(divisor)
            # p.append(divisor)
        return p

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

#is setwise?
gcd = A[0]
for i in range(1, N):
    gcd = math.gcd(gcd, A[i])
isSetwise = (gcd == 1)

#is pairwise?
maxNum = max(A)
factorizor = FastFactorization(maxNum)
factors = set()
isPairwise = True
for i in range(N):
    p = factorizor.factorize(A[i])
    if not factors.isdisjoint(p):
        isPairwise = False
        break
    else:
        factors = factors | p

if isPairwise:
    print("pairwise coprime")
elif isSetwise:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

# 素因数分解、リストで返す
#############################################################


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a.sort()
    return a
#############################################################


primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i])
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

# print(primes)

if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")