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:
#高速素因数分解  osa_k法 
#下準備
def osa_k(a,MAXN):
    sieve = [i for i in range(MAXN+1)]
    p = 2
    while p*p <= MAXN:
        if sieve[p] == p:
            for q in range(2*p,MAXN+1,p):
                if sieve[q] == q:
                    sieve[q] = p
        p += 1

    #素因数分解の値
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
    return tmp

    # 初期入力
import math
import sys
from bisect import bisect_left
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
used =set()

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    max_a =10**6 +10
    for a in A:
        aa =osa_k(a,max_a)
        if used & aa:
            ans ="setwise coprime"
            break #共通要素があったらpair_wではない→set_w
        used |=aa
        ans ="pairwise coprime"
print(ans)

Submission status: Time Limit Exceeded

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

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



NUM = 10**6
T = [True]*(NUM+1)
prime = []
for i in range(2, NUM+1):
    if T[i]:
        prime.append(i)
        tmp = i
        while tmp <= NUM:
            T[tmp] = False
            tmp += i
L = len(prime)
T = [False]*L

for num in A:
    for i in range(L):
        if num%prime[i] == 0:
            if T[i]:
                print("setwise coprime")
                sys.exit()
            T[i] = True
            while num%prime[i] == 0:
                num //= prime[i]
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
def eratosthenes2(n):
    D=[-1]*(n+1)
    D[0]=0
    D[1]=1
    for i in range(2, n+1):
        if D[i] == -1:
            D[i] = i
            for j in range(i*i, n+1, i):
                if D[j] == -1:
                    D[j] = i
    return D

N=int(input())
A=list(map(int,input().split()))
maxA=max(A)
D=eratosthenes2(maxA)
count=[0]*(maxA+1)
for x in A:
    pre=x+1
    while x>1:
        if pre!=D[x]:
            count[D[x]]+=1
            pre=D[x]
        x//=D[x]
maxc=max(count)
if maxc==N:
    print('not coprime')
elif maxc<=1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

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

def generate_D(maxA):
  seq = [i for i in range(maxA+1)]
  p = 2
  while p*p <= maxA:
    if seq[p]==p:
      for q in range(p*2,maxA+1,p):
        if seq[q]==q:
          seq[q] = p
    p += 1
  return seq

cur = a[0]
for v in a[1:]:
  cur = math.gcd(cur,v)
if cur > 1:
  print('not coprime')
else:  
  d = generate_D(max(a))
  primes = set([])
  tf = 1
  for v in a:
    tmp = set([])
    while v > 1:
      tmp.add(d[v])
      v //= d[v]
    for k in tmp:
      if k in primes:
        tf = 0
      else:
        primes.add(k)
  if tf:
    print('pairwise coprime')
  else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
sz=10**6+1
primes=[1]*(sz)

# l=[]
for i in range(2,sz):
	if primes[i]:
		for j in range(i*i,sz,i):
			primes[j]=0

l=[i for i,j in enumerate(primes[2:],2) if j]
n=int(input())
arr=list(map(int,input().split()))

# print(len(l))
r=(max(arr))**(0.5)
ok=True
# print(r)
for pr in l:
	
	cnt=0
	for i in range(n):
		if arr[i]%pr==0:
			cnt+=1
	if cnt>1:
		ok=False
		break
	# print(pr,cnt)


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

if ok :
	print("pairwise coprime ")
elif g==1:
	print('setwise coprime ')
else:
	print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def sieve_of_eratosthenes(n):
  primes = [2]
  cands = list(range(3, n+1, 2))
  while len(cands) != 0:
    prime = primes[-1]
    cands = list(filter(lambda x:x%prime != 0, cands))
    if len(cands) == 0:
      break
    primes.append(cands.pop(0))
  return primes

def factorize(n, primes):
  factors = []
  for prime in primes:
    while n%prime == 0:
      factors.append(prime)
      n//=prime
      if n < 2:
        break
  if n > 1:
    factors.append(n)
  return factors

def main():
  n = int(input())
  lc = [0] * (10**6)
  primes = sieve_of_eratosthenes(int((10**6)**0.5))
  for a in list(map(int, input().strip().split())):
    for p in set(factorize(a, primes)):
      lc[p] += 1
  if max(lc) < 2:
    print('pairwise coprime')
  elif max(lc) < n:
    print('setwise coprime')
  else:
    print('not coprime')

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#素因数分解（10**6まで）
def soinsu_bunkai(m):
    pf=set()
    mm =m
    for i in pri_num:
        while mm %i==0:
            pf.add(i)
            mm //=i
    if mm !=1:
        pf.add(mm)
    return pf

    # 初期入力
import math
import sys
from bisect import bisect_left
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
intersect =set()
pair_w =set()

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
#pri_num =prime_numbers(sq_pri +10 )
pri_num =[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    A.sort()
    x =bisect_left(A,2)
    if N -x >= 78498 +1:
        #10**6以下の素数は78498個、鳩ノ巣原理により必ず素因数が重複、または素数以外の数が出ている
        ans ="setwise coprime"
        
    else:
        for a in A:
            aa =soinsu_bunkai(a)
            if intersect & aa:
                print("setwise coprime")
                sys.exit() #共通要素があったらpair_wではない→set_w
            intersect |=aa

        ans ="pairwise coprime"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#素因数分解（10**6まで）
def soinsu_bunkai(m):
    pf=set()
    mm =m
    for i in pri_num:
        while mm %i==0:
            pf.add(i)
            mm //=i
    if mm !=1:
        pf.add(mm)
    return pf

    # 初期入力
import math
import sys
from bisect import bisect_left
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
intersect =set()
pair_w =set()

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
#pri_num =prime_numbers(sq_pri +10 )
pri_num =[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    A.sort()
    x =bisect_left(A,2)
    if N -x >= 78498 +1:
            print("setwise coprime")
            sys.exit() #10**6以下の素数は78498個、鳩ノ巣原理により必ず素因数が重複、または素数以外の数が出ている
    for a in A:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            print("setwise coprime")
            sys.exit() #共通要素があったらpair_wではない→set_w
        intersect |=aa

    ans ="pairwise coprime"
print(ans)

Submission status: Time Limit Exceeded

Solution code:

#素因数分解（10**6まで）
def soinsu_bunkai(m):
    pf=set()
    mm =m
    for i in pri_num:
        while mm %i==0:
            pf.add(i)
            mm //=i
    if mm !=1:
        pf.add(mm)
    return pf

    # 初期入力
import math
import sys
from collections import Counter
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
intersect =set()
pair_w =set()

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
#pri_num =prime_numbers(sq_pri +10 )
pri_num =[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    for a in A:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            print("setwise coprime")
            sys.exit() #共通要素があったらpair_wではない→set_w
        intersect |=aa

    ans ="pairwise coprime"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def eratosthenes(N):
    is_prime = {i: True for i in range(2, N+1)}
    primes = []
    for i in range(2, N+1):
        if is_prime[i]:
            primes.append(i)
            if i**2 <= N:
                for j in range(i**2, N+1, i):
                    is_prime[j] = False
    return primes


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    allgcd = A[0]
    primes = eratosthenes(1000)
    divs = set()
    pairwise_coprime = True
    for a in A:
        if allgcd > 1:
            allgcd = gcd(allgcd, a)
        if not pairwise_coprime:
            continue
        for p in primes:
            if a % p == 0:
                if p in divs:
                    pairwise_coprime = False
                while a % p == 0:
                    a //= p
                divs.add(p)
        if a != 1:
            if a in divs:
                pairwise_coprime = False
            divs.add(a)
    if pairwise_coprime:
        print("pairwise coprime")
    else:
        if allgcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def eratosthenes(N):
    is_prime = {i: True for i in range(2, N+1)}
    primes = []
    for i in range(2, N+1):
        if is_prime[i]:
            primes.append(i)
            if i**2 <= N:
                for j in range(i**2, N+1, i):
                    is_prime[j] = False
    return primes


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    allgcd = A[0]
    primes = eratosthenes(1000)
    divs = set()
    pairwise_coprime = True
    for a in A:
        allgcd = gcd(allgcd, a)
        if not pairwise_coprime:
            continue
        for p in primes:
            if a % p == 0:
                if p in divs:
                    pairwise_coprime = False
                while a % p == 0:
                    a //= p
                divs.add(p)
        if a != 1:
            if a in divs:
                pairwise_coprime = False
            divs.add(a)
    if pairwise_coprime:
        print("pairwise coprime")
    else:
        if allgcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def eratosthenes(N):
    is_prime = {i: True for i in range(2, N+1)}
    primes = []
    for i in range(2, N+1):
        if is_prime[i]:
            primes.append(i)
            if i**2 <= N:
                for j in range(i**2, N+1, i):
                    is_prime[j] = False
    return primes


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    allgcd = A[0]
    primes = eratosthenes(1000)
    divs = set()
    pairwise_coprime = True
    for a in A:
        allgcd = gcd(allgcd, a)
        if not pairwise_coprime:
            continue
        for p in primes:
            if a % p == 0:
                if p in divs:
                    pairwise_coprime = False
                while a % p == 0:
                    a //= p
                divs.add(p)
        if a != 1:
            if a in divs:
                pairwise_coprime = False
            divs.add(a)
    if pairwise_coprime:
        print("pairwise coprime")
    else:
        if allgcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
a = LIST()
m = max(a)

primes = [0]*(m+1)
primes[1] = 1
for i in range(2, m+1):
    if primes[i] == 0:
        for j in range(1, m//i+1):
            primes[i*j] = i

count = [0]*(m+1)
for x in a:
    y = x
    while primes[y] != y:
        count[primes[y]] += 1
        p = primes[y]
        while y % p == 0:
            y //= p
    if primes[y] >= 2:
        count[primes[y]] += 1

if max(count) <= 1:
    print("pairwise coprime")
else:
    g = 0
    for x in a:
        g = gcd(g, x)
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(max(A)+1)]
C = [0 for i in range(max(A)+1)]

lenB = len(B)
for i in range(2, lenB):
  if i**2 > lenB:
    break
  if B[i] != 0:
    continue
  for j in range(i**2, lenB, i):
    B[j] = i
flag1 = False
flag2 = False
 
def func(X):
  global flag1, flag2
  while X>1:
    x = B[X]
    if x==0:
      x = X
    if C[x]==1:
      flag1 = True
    if C[x]==N-1:
      flag2 = True
    C[x] += 1
    while X%x==0:
      X = X//x
    #print(C)
for a in A:
  func(a)
#print(flag1, flag2)
if flag2:
  print("not coprime")
elif flag1:
  print("setwise coprime")
else:
  print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(max(A)+1)]
C = [0 for i in range(max(A)+1)]
 
for i in range(2, len(B)):
  if B[i] != 0:
    continue
  for j in range(i, len(B), i):
    B[j] = i
flag1 = False
flag2 = False
 
def func(X):
  global flag1, flag2
  while X>1:
    x = B[X]
    if C[x]==1:
      flag1 = True
    if C[x]==N-1:
      flag2 = True
    C[x] += 1
    while X%x==0:
      X = X//x
    #print(C)
for a in A:
  func(a)
#print(flag1, flag2)
if flag2:
  print("not coprime")
elif flag1:
  print("setwise coprime")
else:
  print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
 
B = [0 for i in range(max(A)+1)]
 
for i in range(2, len(B)):
  if B[i] != 0:
    continue
  for j in range(i, len(B), i):
    B[j] = i

def func(X):
  buf = set()
  while X>1:
    x = B[X]
    buf.add(x)
    while X%x==0:
      X = X//x
  #print(buf)
  return buf
 
set1 = func(A[0])
set2 = func(A[0])
totallen = len(set1)
for a in A[1:]:
  set3 = func(a)
  totallen += len(set3)
  #print(a, set1, set2)
  set1 |= set3
  set2 &= set3
  #print(set1, set2, set3)
#print(totallen, set1, set2)
if len(set2)!=0:
  print("not coprime")
elif len(set1)==totallen:
  print("pairwise coprime")
else:
  print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
mxa=max(a)

def get_sieve_of_eratosthenes(mxa):
    fact = [0]*(mxa+1)
    limit = int(math.sqrt(mxa))
    for i in range(2,limit+1):
        if fact[i]!=0:
            continue
        else:
            fact[i]=i
            for j in range(i, mxa+1, i):
                if fact[j]==0:
                    fact[j]=i
    for i in range(2,mxa+1):
        if fact[i]==0:
            fact[i]=i

    return fact

fact = get_sieve_of_eratosthenes(mxa)

lst=[0]*(len(fact))
for i in range(n):
    divisor = set()
    while a[i]!=1:
        divisor.add(fact[a[i]])
        a[i]//=fact[a[i]]
    for d in divisor:
        lst[d]+=1

pair=True
st=True

for i in lst:
    if i>=2:
        pair=False
    if i==n:
        st=False
if pair:
    print("pairwise coprime")
elif st:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
mxa=max(a)

def get_sieve_of_eratosthenes(mxa):
    fact = [0]*(mxa+1)
    limit = int(math.sqrt(mxa))
    for i in range(2,mxa+1):
        if fact[i]!=0:
            continue
        else:
            fact[i]=i
            for j in range(i, mxa+1, i):
                if fact[j]==0:
                    fact[j]=i
    for i in range(2,mxa+1):
        if fact[i]==0:
            fact[i]=i

    return fact

fact = get_sieve_of_eratosthenes(mxa)

lst=[0]*(len(fact))
for i in range(n):
    divisor = set()
    while a[i]!=1:
        divisor.add(fact[a[i]])
        a[i]//=fact[a[i]]
    for d in divisor:
        lst[d]+=1

pair=True
st=True

for i in lst:
    if i>=2:
        pair=False
    if i==n:
        st=False
if pair:
    print("pairwise coprime")
elif st:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
import sys

MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p,MAXN+1,p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1
    
def pf(a):
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
        
    return list(tmp)




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')
    sys.exit()

A=[i for i in A if i != 1]    

B=[pf(A[i]) for i in range(len(A))]
B=sum(B,[])

if len(B) == len(set(B)):
    print("pairwise coprime")
    
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
#ABC177E
N = int(input())
#N = 1000000
A = list(map(int, input().split()))
#A = [i+1 for i in range(1000000)]
p = {2*i+1: 1 for i in range(1, 500)}
for i in range(3, 1000, 2):
  for j in p:
    if j != i:
      if j % i == 0:
        p[j] = 0
L = [2]
for i in p:
  if p[i] == 1:
    L.append(i)
def gcd(x, y):
  k, l = x, y
  while l:
    k, l = l, k % l
  return k
g = A[0]
i = 0
nn = len(L)
while i < N:
  g = gcd(g, A[i])
  if g == 1:
    break
  i += 1
if g > 1:
  print("not coprime")
else:
  D = {}
  m = 0
  for i in A:
    pnt = 0
    x = i
    for j in L:
      cnt = False
      while x % j == 0:
        cnt = True
        x //= j
      if cnt:
        if j in D:
          D[j] += 1
          if D[j] == 2:
            m = 2
            break
        else:
          D[j] = 1
      pnt += 1
      if pnt == nn and x != 1:
        if x in D:
          D[x] += 1
          if D[x] == 2:
            m = 2
        else:
          D[x] = 1
        break
      if x == 1:
        break
    if m >= 2:
      break
  if D == {}:
    print("pairwise coprime")
  else:
    if m > 1:
      print("setwise coprime")
    else:
      print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from functools import reduce
N = str(input())
A = list(map(int, input().split()))

def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
d = 0
for i,o in enumerate(A):
    if i == N:
        break
    for l in A[i+1:]:
        if math.gcd(o,l) != 1:
            d = 1
            break
            
if d == 0:
    print('pairwise coprime')
    exit()

if gcd(*A) == 1:
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math

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

is_prime = [1] * 1000001
D = [0] * 1000001

for i in range(2, 1001):
    if is_prime[i]:
        D[i] = i
        j = 2 * i
        while j <= 1000000:
            if is_prime[j]:
                D[j] = i
                is_prime[j] = 0
            j += i
for i in range(1001, 1000001):
    if is_prime[i]:
        D[i] = i

count = [0] * 1000001
for a in A:
    k = a
    pre = 0
    while k != 1:
        if pre != D[k]:
            count[D[k]] += 1
        pre = D[k]
        k = int(k / D[k])

ans = 'pairwise coprime'
for x in count:
    if x == N:
        print('not coprime')
        exit()
    if x > 1:
        ans = 'setwise coprime'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
MAX = 10**6+5

divs = [[] for _ in range(MAX)]
cnt = [0]*MAX

for i in range(2,n):
  m = i
  while m < MAX:
    divs[m].append(i)
    m += i
    
pair = True
setwise = True

for i in range(n):
  for d in divs[a[i]]:
    if cnt[d] > 0:
      pair = False
    cnt[d] += 1
    
if pair:
  print('pairwise coprime')
else:
  for i in range(MAX):
    if cnt[i] == n:
      setwise = False
      break
  if setwise:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

N = int(input())
A = list([int(x) for x in input().split()])

max_a = 10**6 + 1

before = 0
result = [0 for _ in range(max_a + 1)]

for i in A:
    before = gcd(before, i)
    result[i] += 1

is_pairwise = True
for i in range(2, max_a + 1):
    cnt = 0
    for j in range(i, max_a + 1, i):
        cnt += result[j]

    if cnt > 1:
        is_pairwise = False
        break

if is_pairwise:
    print('pairwise coprime')
    exit()

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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

N = int(input())
A = list([int(x) for x in input().split()])

before = 0
result = [0] * (max(A) + 1)

for i in A:
    before = gcd(before, i)
    result[i] += 1

is_pairwise = True
for i in range(2, max(A) + 1):
    cnt = 0
    for j in range(i, max(A) + 1, i):
        cnt += result[j]

    if cnt > 1:
        is_pairwise = False
        break

if is_pairwise:
    print('pairwise coprime')
    exit()

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

Submission status: Time Limit Exceeded

Solution code:

#素因数分解（10**6まで）
def soinsu_bunkai(m):
    pf=set()
    mm =m
    for i in pri_num:
        while mm %i==0:
            pf.add(i)
            mm //=i
    if mm !=1:
        pf.add(mm)
    return pf

    # 初期入力
import math
import sys
from collections import Counter
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
intersect =set()
pair_w =set()

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
#pri_num =prime_numbers(sq_pri +10 )
pri_num =[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    for a in A:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            pair_w.add(0)
            break #共通要素があったらpair_wではない→set_w
        else:
            pair_w.add(1)
        intersect |=aa

    if 0 in pair_w:
        ans ="setwise coprime"        
    else:
        ans ="pairwise coprime"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#素因数分解（10**6まで）
def soinsu_bunkai(m):
    pf=set()
    mm =m
    for i in pri_num:
        while mm %i==0:
            if i >m:
                break
            elif mm %i==0:
                pf.add(i)
                mm //=i
    if mm !=1:
        pf.add(mm)
    return pf

    # 初期入力
import math
import sys
from collections import Counter
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
intersect =set()
pair_w =set()

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
#pri_num =prime_numbers(sq_pri +10 )
pri_num =[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    for a in A:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            pair_w.add(0)
            break #共通要素があったらpair_wではない→set_w
        else:
            pair_w.add(1)
        intersect |=aa

    if 0 in pair_w:
        ans ="setwise coprime"        
    else:
        ans ="pairwise coprime"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 自然数m以下の素数を返す（SETでRETURN）
import math
def prime_numbers(m):
    # 素数を保持するset
    primes = []

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.append(n)
        n += 1
    return primes

#素数で割れるか、同じ素数で何回割れるかは見てないから素因数分解とは違う（10**6まで）
def soinsu_bunkai(m):
    pf=set()
    mm =m
    for i in pri_num:
        while mm %i==0:
            if i >m:
                break
            elif mm %i==0:
                pf.add(i)
                mm //=i
    if mm !=1:
        pf.add(mm)
    return pf

    # 初期入力
import sys
from collections import Counter
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
intersect =set()
pair_w =set()

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
pri_num =prime_numbers(sq_pri +10 )

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    for a in A:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            pair_w.add(0)
            break #共通要素があったらpair_wではない→set_w
        else:
            pair_w.add(1)
        intersect |=aa

    if 0 in pair_w:
        ans ="setwise coprime"        
    else:
        ans ="pairwise coprime"
print(ans)