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:
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):
            index = head_num * (i + 1)
            if D[index] == index:
                D[index] = 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)
    div_set = set()
    while number > 1:
        number //= div
        div_set.add(div)
        div = D[number]
    if number > 1:
        div_set.add(div)
    for div in div_set:
        ans_array[div] += 1

thre = pow(10, 6) + 1
# thre = max(a_array) + 1
ans_array = [0] * thre
D = list(range(thre + 1))

prime_list = get_primenumber(thre)
# print(D[-10:])
for a in a_array:
    factrization_prime(a)
# print(ans_array)

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

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *                      # ll = deepcopy(l)
from heapq import *                     # heappush(hp,x)
from string import *                    # alpha = ascii_lowercase
from random import *                    # l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *                    # bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin                   # bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize                 # minn = -maxsize
from operator import *                  # d = sorted(d.items(), key=itemgetter(1))
from itertools import *                 # pre = [0] + list(accumulate(l))
from decimal import Decimal             # a = Decimal(a)    # use this for math questions
from collections import Counter         # d = dict(Counter(l))
from collections import defaultdict     # d = defaultdict(list)

'''
3
3 4 5
'''

def solve(l):
	n = len(l)
	maxx = max(l)
	tmp = [1]*(maxx+1)
	zz = 2
	tmp[0] = tmp[1] = 0
	gg = l[0]
	for i in range(1,n):
		gg = gcd(gg,l[i])
	if(gg != 1):
		return 'not coprime'
	d = dict(Counter(l))
	while(zz**2 <= maxx):
		f = 0
		if(tmp[zz]):
			i = 2
			while(i*zz <= maxx):
				if(i*zz in d):
					f += 1
					if(f > 1):
						return 'setwise coprime'
				tmp[i*zz] = 1
				i += 1
		zz += 1
	return 'pairwise coprime'
	

N = int(stdin.readline())
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l)
print(ans)

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]

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

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

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

ptype="pairwise coprime"
for pp in p:
    lap=0
    for ai in ap:
        if  ai%pp==0:
            lap+=1
        if lap>=2:
            ptype="setwise coprime"
            print(ptype)    
            sys.exit()
#    lap=len([ai for ai in ap if ai%pp==0])
#    print("pp:",pp,lap)
#    if lap==n:
#        ptype="not coprime"
#        print("not coprime")
#        break
#    if lap>=2:
#        if ptype!="not coprime":
#        ptype="setwise coprime"

print(ptype)

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]

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

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp=bp[1:]
#    bp=list(bp&set(p))
    for bpi in bp:
#        if not bpi in p:
#            continue
        lap=0
        for ai in ap:
            if ai%bpi==0:
                lap+=1
#        lap=len([ai for ai in ap if ai%bpi==0])
        if lap==n:
            print("not coprime")
            sys.exit()

ptype="pairwise coprime"
for pp in p:
    lap=0
    for ai in ap:
        if  ai%pp==0:
            lap+=1
        if lap>=2:
            ptype="setwise coprime"
            print(ptype)    
            sys.exit()
#    lap=len([ai for ai in ap if ai%pp==0])
#    print("pp:",pp,lap)
#    if lap==n:
#        ptype="not coprime"
#        print("not coprime")
#        break
#    if lap>=2:
#        if ptype!="not coprime":
#        ptype="setwise coprime"

print(ptype)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]

# a,bの最大公約数


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# a,bの最小公倍数


def lcm(a, b):
    return a * b // gcd(a, b)


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    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]


max_a = pow(10, 6)+5
N = z()
A = zz()
pari_flg = True

set_flg = True
count = [0]*max_a
for i in range(N):
    count[A[i]] = 1
for i in range(2, max_a):
    c = 0
    for j in range(i, max_a, i):
        c += count[j]
        if (c > 1):
            pari_flg = False
res = A[0]
for i in range(1, N):
    res = gcd(res, A[i])
if (res != 1):
    set_flg = False

if (pari_flg):
    print('pairwise coprime')
elif (set_flg):
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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):
            index = head_num * (i + 1)
            if D[index] == index:
                D[index] = 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)
    div_set = set()
    while div <= s:
        number //= div
        div_set.add(div)
        if number == 1:
            break
        div = D[number]
    if number > 1:
        div_set.add(div)
    for div in div_set:
        ans_array[div] += 1


thre = pow(10, 6) + 1
# thre = max(a_array) + 1
ans_array = [0] * thre
D = list(range(thre + 1))

prime_list = get_primenumber(thre)
# print(D)
for a in a_array:
    factrization_prime(a)
# print(ans_array)

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

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

maxA = max(A) + 1

C = [0] * maxA

g = 0

for a in A:
    C[a] += 1
    g = math.gcd(g, a)

pairwise = True

for i in range(2, maxA):
    cnt = 0
    for j in range(i, maxA, i):
        cnt += C[j]

    if cnt > 1:
        pairwise = False

if pairwise:
    print("pairwise comrime")
    exit()

if g == 1:
    print("setwise coprime")

else:
    print("not coprime")

Submission status: Wrong Answer

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)
        cnt_list = [0] * (n + 1)
        for i in range(2, limit + 2):
            if cnt_list[i] == 0:
                k = n // i
                for j in range(1, k + 1):
                    s = i * j
                    if cnt_list[s] == 0:
                        D[s] = i
                        cnt_list[s] = 1
        for l in range(limit + 1, n + 1):
            if cnt_list[l] == 0:
                D[l] = l
        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: Wrong Answer

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):
            index = head_num * (i + 1)
            if D[index] == index:
                D[index] = 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)
    div_set = set()
    while div <= s:
        number //= div
        div_set.add(div)
        if number == 1:
            break
        div = D[number]
    if number > 1:
        div_set.add(div)
    for div in div_set:
        ans_array[div] += 1


# thre = pow(10, 6) + 1
thre = max(a_array) + 1
ans_array = [0] * thre
D = list(range(thre + 1))

prime_list = get_primenumber(thre)
# print(D)
for a in a_array:
    factrization_prime(a)
# print(ans_array)

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

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)
        cnt_list = [0] * (n + 1)
        for i in range(2, limit + 1):
            if cnt_list[i] == 0:
                k = n // i
                for j in range(1, k + 1):
                    s = i * j
                    if cnt_list[s] == 0:
                        D[s] = i
                        cnt_list[s] = 1
        for l in range(limit, n + 1):
            if cnt_list[l] == 0:
                D[l] = l
        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: 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]

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

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp=set(bp[1:])
    bp=list(bp&set(p))
    for bpi in bp:
        lap=0
        for ai in ap:
            if ai%bpi==0:
                lap+=1
#        lap=len([ai for ai in ap if ai%bpi==0])
        if lap==n:
            print("not coprime")
            sys.exit()

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

ptype="pairwise coprime"
for pp in p:
    lap=0
    for ai in ap:
        if  ai%pp==0:
            lap+=1
        if lap>=2:
            ptype="setwise coprime"
            print(ptype)    
            sys.exit()
#    lap=len([ai for ai in ap if ai%pp==0])
#    print("pp:",pp,lap)
#    if lap==n:
#        ptype="not coprime"
#        print("not coprime")
#        break
#    if lap>=2:
#        if ptype!="not coprime":
#        ptype="setwise coprime"

print(ptype)

Submission status: Wrong Answer

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

A.sort()

t = []

a = A[0]
for i in range(2, min(a, int(math.sqrt(a)) + 1)):
    if a % i == 0:
        t.append(i)
        t.append(a // i)

t.append(a)

ans = 0
for tt in t:
    tmp = 0
    for a in A:
        if a % tt == 0:
            tmp += 1

    ans = max(ans, tmp)
    
if tmp == 1:
    print("pairwise coprime")

elif tmp < N:
    print("setwise coprime")

else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = [int(_) for _ in input().split()]


class Prime:
    @staticmethod
    def trial_division(x):
        if x % 2 == 0:
            return True
        for p in range(3, int(x**0.5 + 1), 2):
            if x % p == 0:
                return False
        return True

    @staticmethod
    def factorization(x):
        ret = set()
        while True:
            if x % 2:
                break
            x //= 2
            ret.add(2)
        for p in range(3, int(x**0.5 + 1), 2):
            if x % p == 0:
                ret.add(p)
        if x > 1:
            ret.add(x)
        return ret

    @staticmethod
    def miller_rabin(n):
        def suspect(a, t, n):
            x = pow(a, t, n)
            n1 = n - 1
            while t != n1 and x != 1 and x != n1:
                x = pow(x, 2, n)
                t <<= 1
            return t & 1 or x == n1

        if n == 2:
            return True
        if n < 2 or n % 2 == 0:
            return False
        d = (n - 1) >> 1
        while d & 1 == 0:
            d >>= 1

        if n < 2**32:
            check_list = (2, 7, 61)
        elif n < 2**48:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23)
        else:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)

        for i in check_list:
            if i >= n:
                break
            if not suspect(i, d, n):
                return False
        return True


c = collections.defaultdict(int)
for a in A:
    for p in Prime.factorization(a):
        c[p] += 1
ans = 'pairwise coprime'
if c:
    x = max(c.values())
    if x == 1:
        ans = 'pairwise coprime'
    elif x == N:
        ans = 'not coprime'
    else:
        ans = 'setwise coprime'
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = [int(_) for _ in input().split()]


class Prime:
    @staticmethod
    def trial_division(x):
        if x % 2 == 0:
            return True
        for p in range(3, int(x**0.5 + 1), 2):
            if x % p == 0:
                return False
        return True

    @staticmethod
    def factorization(x):
        ret = set()
        while True:
            if x % 2:
                break
            x //= 2
            ret.add(2)
        for p in range(3, int(x**0.5 + 1), 2):
            if x % p:
                break
            ret.add(p)
        if x > 1:
            ret.add(x)
        return ret

    @staticmethod
    def miller_rabin(n):
        def suspect(a, t, n):
            x = pow(a, t, n)
            n1 = n - 1
            while t != n1 and x != 1 and x != n1:
                x = pow(x, 2, n)
                t <<= 1
            return t & 1 or x == n1

        if n == 2:
            return True
        if n < 2 or n % 2 == 0:
            return False
        d = (n - 1) >> 1
        while d & 1 == 0:
            d >>= 1

        if n < 2**32:
            check_list = (2, 7, 61)
        elif n < 2**48:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23)
        else:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)

        for i in check_list:
            if i >= n:
                break
            if not suspect(i, d, n):
                return False
        return True


c = collections.defaultdict(int)
for a in A:
    for p in Prime.factorization(a):
        c[p] += 1
ans = 'pairwise coprime'
if c:
    x = max(c.values())
    if x == 1:
        ans = 'pairwise coprime'
    elif x == N:
        ans = 'not coprime'
    else:
        ans = 'setwise coprime'
print(ans)

Submission status: Wrong Answer

Solution code:
import math


n = int(input())
a = [int(x) for x in input().split()]
l = [[] for i in range(n)]

def gcd(p,q):
    while q != 0:
        p = min(p%q,-(p%q)+q)
        p,q = q,p
    return p


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

if g != 1:
    print("not coprime")

else:
    def fur(x):
        k = [1 for i in range(x+1000)]
        k[0]=k[1]=0
        for i in range(2,x+1):
            for j in range(i-1,x//i):
                k[i+j*i] = 0
        return k

    t = fur(10**6)

    cnt = 0

    def soi(x):
        global t,cnt
        for i in range(2,int(math.sqrt(x))+1):
            if x%i==0:
                if t[i] == 1:
                    t[i] = 2
                if t[x//i] == 1:
                    t[x//i] = 2
                if t[i] == 2 or t[x//i] == 2:
                    cnt = 1
                    break
    
    for i in range(n):
        if cnt == 1:
            break
        else:
            soi(a[i])
    
    if cnt == 1:
        print("setwise coprime")
    
    else:
        print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math


n = int(input())
a = [int(x) for x in input().split()]
l = [[] for i in range(n)]

def gcd(p,q):
    while q != 0:
        p = min(p%q,-(p%q)+q)
        p,q = q,p
    return p


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

if g != 1:
    print("not coprime")

else:
    def fur(x):
        k = [1 for i in range(x+1000)]
        k[0]=k[1]=0
        for i in range(2,x+1):
            for j in range(i-1,x//i):
                k[i+j*i] = 0
        return k

    t = fur(10**6)

    cnt = 0

    def soi(x):
        global t,cnt
        for i in range(2,int(math.sqrt(x))+1):
            if x%i==0:
                if t[i] == 1 and t[x//i] == 1:
                    t[i] = 2
                    t[x//i] = 2
                elif t[i] == 2 or t[x//i] == 2:
                    cnt = 1
                    break
    
    for i in range(n):
        if cnt == 1:
            break
        else:
            soi(a[i])
    
    if cnt == 1:
        print("setwise coprime")
    
    else:
        print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A_list = list(map(int, input().split()))

    maxa = max(A_list)
    lim =int(maxa**0.5)+1

    primes_table = [True] * lim
    primes_table[0] = primes_table[1] = False
    primes = set()
    for i in range(2,lim):
        if primes_table[i] == False:
            continue
        primes.add(i)
        for j in range(i+i, lim, i):
            primes_table[j] = False

    a_set = [set()] * N
    pr_dict = {r: set() for r in primes}
    for a in A_list:
        for p in primes:
            if a%p== 0:
                pr_dict[p].add(a) 
                
    maxlen = 0
    for d in pr_dict.values():
        maxlen=max(maxlen, len(d))

    if maxlen == 1:
        print("pairwise coprime")
    elif maxlen < N:
        print("setwise coprime")
    else:
        print("not coprime")
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

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

a_max = (10**6)+1
hist = [0] * a_max
for a in a_list:
    hist[a] += 1

pairwise = True
for i in range(2, a_max, 1):
    count = 0
    for j in range(2, a_max, i):
        count += hist[j]

    if count > 1:
        pairwise = False

if pairwise:
    print('pairwise coprime')
else:
    setwise = True
    g = a_list[0]
    for a in a_list:
        g = math.gcd(g, a)
    if g > 1:
        setwise = False

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

Submission status: Wrong Answer

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


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


def is_pairwise_coprime(A):
    n = max(A)
    base = [False for i in range(n+1)]
    for a in A:
        base[a] = True
    
    is_prime = [True for i in range(n+1)]
    for i in range(2, n+1):
        if is_prime[i]:
            include_number = set()
            if base[i]:
                include_number.add(i)
            for j in range(i+i, n+1, i):
                is_prime[j] = False
                if base[j]:
                    include_number.add(j)
            if len(include_number) >= 2:
                return False
    return True


def solve(N, A):
    if is_pairwise_coprime(A):
        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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]

# a,bの最大公約数


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# a,bの最小公倍数


def lcm(a, b):
    return a * b // gcd(a, b)


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    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]


max_a = pow(10, 6)+1
N = z()
A = zz()
pari_flg = True

set_flg = True
count = [0]*max_a
for i in range(N):
    count[A[i]] = 1
for i in range(2, max_a):
    c = 0
    for j in range(i, max_a, i):
        c += count[j]
        if (c > 1):
            pari_flg = False
res = A[0]
for i in range(1, N):
    res = gcd(res, A[i])
if (res != 1):
    set_flg = False

if (pari_flg):
    print('pairwise coprime')
elif (set_flg):
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math


n = int(input())
a = [int(x) for x in input().split()]
l = [[] for i in range(n)]

def gcd(p,q):
    while q != 0:
        p = min(p%q,-(p%q)+q)
        p,q = q,p
    return p


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

if g != 1:
    print("not coprime")

else:
    def fur(x):
        k = [1 for i in range(x+1000)]
        k[0]=k[1]=0
        for i in range(2,x+1):
            for j in range(i-1,x//i):
                k[i+j*i] = 0
        return k

    t = fur(10**6)

    cnt = 0

    def soi(x):
        global t,cnt
        for i in range(2,int(math.sqrt(x))+1):
            if t[i] != 0 and x%i==0:
                if t[i] == 1 and t[x//i] == 1:
                    t[i] = 2
                    t[x//i] = 2
                elif t[i] == 2 or t[x//i] == 2:
                    cnt = 1
                    break
    
    for i in range(n):
        if cnt == 1:
            break
        else:
            soi(a[i])
    
    if cnt == 1:
        print("setwise coprime")
    
    else:
        print("pairwise coprime")

Submission status: Wrong Answer

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


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


def is_pairwise_coprime(A):
    n = max(A)
    base = [False for i in range(n+1)]
    for a in A:
        base[a] = True
    
    is_prime = [True for i in range(n+1)]
    for i in range(2, n+1):
        if is_prime[i]:
            n_includes = 0
            if base[i]:
                n_includes += 1
            for j in range(i+i, n+1, i):
                is_prime[j] = False
                if base[a]:
                    n_includes += 1
            if n_includes >= 2:
                return False
    return True


def solve(N, A):
    if is_pairwise_coprime(A):
        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))