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: Wrong Answer

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

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


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


max_A = max(A)

if max_A == 1:
    print('pairwise coprime')
    exit()
# エラトステネスの篩により素数を高速で求める
# そのかんにある数値がふるい落とされたその素数をメモしておく

D = [0] * (max_A + 1)
is_prime = [True] * (max_A + 1)
is_prime[0] = False
is_prime[1] = False
prime = deque()
for i in range(2, int(max_A ** 0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, max_A + 1, i):
        is_prime[j] = False
        D[j] = i

for i in range(len(is_prime)):
    if is_prime[i]:
        D[i] = i

# print(D)

pairwise = True
check = [0] * (max_A + 1)
new_A = A[:]
for i in range(N):
    min_prime = D[new_A[i]]
    while True:
        if D[min_prime] == 0:
            break
        if D[min_prime] == min_prime:
            check[D[min_prime]] += 1
            break

        check[D[min_prime]] += 1


# print(D)
# print(check)

if max(check) > 1:
    pairwise = False
# print(check)
if pairwise:
    print('pairwise coprime')
else:
    if gcd_list(A) == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

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

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


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


max_A = max(A)

if max_A == 1:
    print('pairwise coprime')
    exit()
# エラトステネスの篩により素数を高速で求める
# そのかんにある数値がふるい落とされたその素数をメモしておく

D = [0] * (max_A + 1)
is_prime = [True] * (max_A + 1)
is_prime[0] = False
is_prime[1] = False
prime = deque()
for i in range(2, int(max_A ** 0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, max_A + 1, i):
        is_prime[j] = False
        D[j] = i

for i in range(len(is_prime)):
    if is_prime[i]:
        D[i] = i

# print(D)

pairwise = True
check = [0] * (max_A + 1)
new_A = A[:]
for i in range(N):
    min_prime = D[new_A[i]]
    while True:
        if D[min_prime] == 0:
            break
        check[D[min_prime]] += 1
        if D[min_prime] == min_prime:
            break


if max(check) > 1:
    pairwise = False
# print(check)
if pairwise:
    print('pairwise coprime')
else:
    if gcd_list(A) == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys
import math
import functools


def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))

    max_a = max(A)
    temp = [0] * (max_a + 1)
    temp[1] = 1

    for i in range(2, max_a + 1):
        if temp[i]:
            continue

        j = i
        while j < max_a + 1:
            if not temp[j]:
                temp[j] = i
            j += i

    B = []
    for a in A:
        while a > 1:
            B.append(temp[a])
            a = a // temp[a]
    
    C = tuple(filter(lambda x: x > 1, B))
    D = frozenset(C)
    if len(C) == len(D):
        return 'pairwise coprime'

    if functools.reduce(math.gcd, A) == 1:
        return 'setwise coprime'

    return 'not coprime'
    

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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


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


max_A = max(A)

if max_A == 1:
    print('pairwise coprime')
    exit()
# エラトステネスの篩により素数を高速で求める
# そのかんにある数値がふるい落とされたその素数をメモしておく

D = [0] * (max_A + 1)
is_prime = [True] * (max_A + 1)
is_prime[0] = False
is_prime[1] = False
prime = deque()
for i in range(2, int(max_A ** 0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, max_A + 1, i):
        is_prime[j] = False
        D[j] = i

for i in range(len(is_prime)):
    if is_prime[i]:
        D[i] = i

# print(D)

pairwise = True
check = [0] * (max_A + 1)
new_A = A[:]
for i in range(N):
    min_prime = D[new_A[i]]
    while True:
        check[D[min_prime]] += 1
        if D[min_prime] == min_prime:
            break


if max(check) > 1:
    pairwise = False
# print(check)
if pairwise:
    print('pairwise coprime')
else:
    if gcd_list(A) == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

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

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


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


max_A = max(A)
# エラトステネスの篩により素数を高速で求める
# そのかんにある数値がふるい落とされたその素数をメモしておく

D = [0] * (max_A + 1)
is_prime = [True] * (max_A + 1)
is_prime[0] = False
is_prime[1] = False
prime = deque()
for i in range(2, int(max_A ** 0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, max_A + 1, i):
        is_prime[j] = False
        D[j] = i

for i in range(len(is_prime)):
    if is_prime[i]:
        D[i] = i

# print(D)

pairwise = True
check = [0] * (max_A + 1)
new_A = A[:]
for i in range(N):
    min_prime = D[new_A[i]]
    while True:
        check[D[min_prime]] += 1
        if D[min_prime] == min_prime:
            break


if max(check) > 1:
    pairwise = False
# print(check)
if pairwise:
    print('pairwise coprime')
else:
    if gcd_list(A) == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:

import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret


import math

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の倍数を除去
        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

p=get_primenumber(79000)

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1
    
for pp in p:
    psum=0
#    for pi in range(pp,amax+1,pp):
#    for pi in range(pp,amax+pp-1,pp):
#        psum+=aa[pi]
    psum=sum(aa[pp: :pp])
#    print("pp:",pp,psum)
    if psum>=2:
            print("setwise coprime")
            sys.exit()
## max_13.txt ... max_16.txt : "setwise coprime"
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:

import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret


import math

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の倍数を除去
        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

p=get_primenumber(79000)

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1
    
for pp in p:
    psum=0
    for pi in range(pp,amax+1,pp):
        psum+=aa[pi]
#    print("pp:",pp,psum)
    if psum>=2:
            print("setwise coprime")
            sys.exit()
## max_13.txt ... max_16.txt : "setwise coprime"
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

p=[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]

import math

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の倍数を除去
        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

p=get_primenumber(78500)

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()


aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1
    
for pp in p:
    psum=0
    for pi in range(pp,amax+1,pp):
        psum+=aa[pi]
    if psum>=2:
            print("setwise coprime")
            sys.exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:

import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

p=[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]

import math

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の倍数を除去
        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

p=get_primenumber(20000)

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()


aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1
    
for pp in p:
    psum=0
    for pi in range(pp,amax+1,pp):
        psum+=aa[pi]
    if psum>=2:
            print("setwise coprime")
            sys.exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math


def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


data = get_sieve_of_eratosthenes(10**6)


n=int(input())
a=list(map(int,input().split()))
arr = [0]*(10**6+1)
def factorization(n):
    temp = n
    flag=0
    a=[]
    for i in data:
        if i>=int(-(-n**0.5//1))+1:
            break
        if temp%i==0:
            flag=1
            while temp%i==0:
                temp //= i
            a.append(i)
    if flag==0:
        a.append(n)
    return a


f=False
for num in a:
    for s in factorization(num):
        arr[s]+=1
ans=max(arr)
if ans==n:
    print("not coprime")
elif ans>=2:
    print("setwise coprime")
elif ans==1:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math

n=int(input())
a=input().split(' ')
s=0
for i in range(0,n-1):
  flag=0
  for j in range(i+1,n):
    if math.gcd(int(a[i]),int(a[j]))!=1:
      break
    if j==n-1:
      s+=1
if s==n-1:
  print('pairwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
sosuu=callIsPrime(10**6)
n=int(input())
a=list(map(int,input().split()))
arr = [0]*(10**6+1)
def factorization(n):
    temp = n
    flag=0
    a=[]
    for i in sosuu:
        if i>=int(-(-n**0.5//1))+1:
            break
        if temp%i==0:
            flag=1
            while temp%i==0:
                temp //= i
            a.append(i)
    if flag==0:
        a.append(n)
    return a


f=False
for num in a:
    for s in factorization(num):
        arr[s]+=1
ans=max(arr)
if ans==n:
    print("not coprime")
elif ans>=2:
    print("setwise coprime")
elif ans==1:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math

# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
sosuu=callIsPrime(10**6)
n=int(input())
a=list(map(int,input().split()))
arr = [0]*(10**6+1)
def factorization(n):
    temp = n
    flag=0
    a=[]
    for i in sosuu:
        if i>=int(-(-n**0.5//1))+1:
            break
        if temp%i==0:
            flag=1
            while temp%i==0:
                temp //= i
            a.append(i)
    if flag==0:
        a.append(n)
    return a


f=False
for num in a:
    for s in factorization(num):
        arr[s]+=1
ans=max(arr)
if ans==n:
    print("not coprime")
elif ans>=2:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
arr = [0]*(10**6+1)
def factorization(n):
    temp = n
    flag=0
    a=[]
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            flag=1
            while temp%i==0:
                temp //= i
            a.append(i)
    if flag==0:
        a.append(n)
    return a


f=False
for num in a:
    for s in factorization(num):
        arr[s]+=1
ans=max(arr)
if ans==n:
    print("not coprime")
elif ans>=2:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
temp=[0]*(10**6+1)
for i in a:
    temp[i]+=1
ans=[]
for i in range(2,10**6+1):
    count=0
    j=1
    while True:
        count+=temp[i*j]
        j+=1
        if i*j>=10**6:
            break
    ans.append(count)
if max(ans)==1:
    print("pairwise coprime")
elif max(ans)==n:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
max_A = max(A)
sieve = list(range(2, math.ceil(max_A ** (1 / 2))))
prime = []
while len(sieve) > 0:
    p = sieve[0]
    prime.append(p)
    sieve = [s for s in sieve if s % p != 0]

factors = {}
pairwise = True
for a in A:
    for p in prime:
        if a % p == 0:
            if p in factors:
                pairwise = False
                break
            else:
                factors[p] = True
    if not pairwise:
        break
if pairwise:
    print('pairwise coprime')
else:
    gcd = reduce(math.gcd, A)
    if gcd == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
primes = [2]

from math import ceil, gcd, sqrt
from functools import reduce
for i in range(3, ceil(sqrt(max(a)))):
  for p in primes:
    if i % p == 0:
      break
  else:
    primes.append(i)
primesdic = {p: 0 for p in primes}

def pfact(x):
  for p in primes:
    if x % p == 0:
      if primesdic[p] > 0:
        return False
      primesdic[p] += 1
  else:
    return True
      
for i in range(n):
  if i > 0 and a[i] > 1:
    if a[i] == a[i-1]:
      print('not coprime')
      break
  if not pfact(a[i]):
    if reduce(gcd, a) == 1:
      print('setwise coprime')
    else:
      print('not coprime')
    break
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
import functools
import sys

N = int(input())
A = list(filter(lambda i: i != 1, map(int, input().split())))

if len(A) == 0:
    print('pairwise coprime')
    sys.exit(0)

#pcount = 78498
#if len(A) > pcount:
#    print('setwise coprime')
#    sys.exit(0)

Amax = max(A) + 1

hurui = [1] * 1001
primes = []

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

    primes.append(n)

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


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

count = [0] * (Amax+1)

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

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

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

Submission status: Wrong Answer

Solution code:
import math
import functools
import sys

N = int(input())
A = list(filter(lambda i: i != 1, map(int, input().split())))

if len(A) == 0:
    print('pairwise coprime')
    sys.exit(0)

Amax = max(A) + 1
pcount = 78498

if len(A) > pcount:
    print('setwise coprime')
    sys.exit(0)

hurui = [1] * 1001
primes = []

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

    primes.append(n)

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


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

count = [0] * (Amax+1)

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

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
primes = [2]

from math import ceil, gcd, sqrt
from functools import reduce
for i in range(3, ceil(sqrt(max(a)))):
  for p in primes:
    if i % p == 0:
      break
  else:
    primes.append(i)
primesdic = {p: 0 for p in primes}

def pfact(x):
  for p in primes:
    if x % p == 0:
      if primesdic[p] > 0:
        return False
      primesdic[p] += 1
    if p > ceil(sqrt(x)):
      return True
  else:
    return True
      
for i in range(n):
  if i > 0 and a[i] > 1:
    if a[i] == a[i-1]:
      print('not coprime')
      break
  if not pfact(a[i]):
    if reduce(gcd, a) == 1:
      print('setwise coprime')
    else:
      print('not coprime')
    break
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
primes = [2]

from math import ceil, gcd, sqrt
from functools import reduce
for i in range(3, ceil(sqrt(max(a)))):
  for p in primes:
    if i % p == 0:
      break
  else:
    primes.append(i)
primesdic = {p: 0 for p in primes}

def pfact(x):
  for p in primes:
    if x % p == 0:
      if primesdic[p] > 0:
        return False
      primesdic[p] += 1
    if p > ceil(sqrt(x)):
      return True
  else:
    return True
      
for i in range(n):
  if i > 0:
    if a[i] == a[i-1]:
      print('not coprime')
      break
  if not pfact(a[i]):
    if reduce(gcd, a) == 1:
      print('setwise coprime')
    else:
      print('not coprime')
    break
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
primes = [2]

from math import ceil, gcd, sqrt
from functools import reduce
for i in range(3, ceil(sqrt(max(a)))):
  for p in primes:
    if i % p == 0:
      break
  else:
    primes.append(i)
primesdic = {p: 0 for p in primes}

def pfact(x):
  for p in primes:
    if x % p == 0:
      if primesdic[p] > 0:
        return False
      primesdic[p] += 1
    if p > ceil(sqrt(x)):
      return True
  else:
    return True
      
for i in range(n):
  if not pfact(a[i]):
    if reduce(gcd, a) == 1:
      print('setwise coprime')
    else:
      print('not coprime')
    break
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math

def sieve():
  n = 10**6
  primes = [set() for _ in range(n+1) ]

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

  return primes

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

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

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

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

Submission status: Wrong Answer

Solution code:
import math
import functools
import sys

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

hurui = [1] * 1001
primes = []

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

    primes.append(n)

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


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

#print(primes)

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

count = [0] * (Amax+1)

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

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

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

Submission status: Wrong Answer

Solution code:
import math
import functools
import sys

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

hurui = [1] * 1001
primes = []

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

    primes.append(n)

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


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

#print(primes)

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

count = [0] * (Amax+1)

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

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

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

Submission status: Wrong Answer

Solution code:
import math

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

  for i in range(2,int(math.sqrt(MAX_INT)+1)):
    if type(primes[i])==bool and primes[i] == True:
      # multiple of i
      j = 2
      while i*j < MAX_INT:
        if type(primes[i*j]) == bool:
          primes[i*j] = i
        j += 1

  return primes

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

dic = {}
flg = True
for a in A:
  if type(primes[a]) == bool:
    p = a
  else:
    p = primes[a]
  if p in dic:
    flg = False
    break
  else:
    dic[p] = 1

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