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:
NUM_MAX = 10**3 + 1
is_prime = [True] * NUM_MAX
is_prime[0] = False
is_prime[1] = False
primes = []
for i in range(NUM_MAX):
    if is_prime[i]:
        primes.append(i)
        for j in range(2*i, NUM_MAX, i):
            is_prime[j] = False

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

def solve(n, a):
    ok = True
    for p in primes:
        num = 0
        for x in a:
            if x % p == 0:
                num += 1
        if num > 1:
            ok = False
    if ok:
        return "pairwise coprime"
    p = a[0]
    for i in range(1, n):
       p = gcd(p, a[i])
    return "setwise coprime" if p == 1 else "not coprime"

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

Submission status: Wrong Answer

Solution code:
NUM_MAX = 10**3 + 1
is_prime = [True] * NUM_MAX
is_prime[0] = False
is_prime[1] = False
primes = []
for i in range(NUM_MAX):
    if is_prime[i]:
        primes.append(i)
        for j in range(2*i, NUM_MAX, i):
            is_prime[j] = False

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

def solve(n, a):
    if len(set(a)) == n:
        return "pairwise coprime"
    for p in primes:
        num = 0
        for x in a:
            if x % p == 0:
                num += 1
        if num > 1:
            return "pairwise coprime"
    p = a[0]
    for i in range(1, n):
       p = gcd(p, a[i])
    return "setwise coprime" if p == 1 else "not coprime"

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

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for i in range(2, 1000):
        if sum(C[i::i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')

Submission status: Wrong Answer

Solution code:
import sys, math

N = int(input())
A = list(map(int, input().split()))
G = 0
for a in A:
    G = math.gcd(G, a)

if G != 1:
    print("not coprime")
    exit(0)

M = 10 ** 6 + 5
B = dict()
for a in A:
    if a in B:
        B[a] = B[a] + 1
    else:
        B[a] = 1

for i in range(2, M):
    cnt = 0
    for j in range(i, M, i):
        if not j in B:
            continue
        if i == j:
            cnt += B[j] - 1
        else:
            cnt += B[j]
    if cnt > 1:
        print("setwise coprime")
        exit(0)

print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
    if a < b:
        a,b = b,a
    a = a%b
    return gcd(b,a) if a!= 0 else b

# def prime_list(a):
#     for i in range(2,a):
#         if a < i**2:
#             break
#         if a%i == 0:
#             yield i
#             if i != a//i:
#                 yield a//i
#     yield a



def main():
    n = int(input())
    A = list(map(int,input().split()))
    counter = [0 for i in range(int(1e6+1))]

    setwise = A[0]
    for a in A:
        counter[a] += 1
        setwise = gcd(a,setwise)

    for i in range(2,len(counter)):
        if 1 < sum(counter[i::i]):
            if setwise == 1:
                print("setwise coprime")      
            else:
                print("not coprime")
            return
        else:
            print("pairwise coprime")
            return 


    # prime = [True for i in range(int(1e6+2))]
    # setwise = A[0]
    # pairwise = True
    # prime_set = set()
    # for a in A:
    #     if pairwise:
    #         for p in prime_list(a):
    #             if p not in prime_set:
    #                 prime_set.add(p)
    #             else:
    #                 pairwise = False


        #     if pairwise and prime[p] == True:
        #         prime[p] = False
        #         index = p
        #         while index < len(prime):
        #             prime[index] = False
        #             index += p
        #     else:
        #         pairwise = False
        #         break

        # setwise = gcd(setwise,a)

    # pairwise = True
    # setwise = A[0]
    # for a in A[1:]:
    #     if pairwise and gcd(A[0],a) != 1:
    #         pairwise = False

    #     setwise = gcd(setwise,a)
    # if pairwise:
    #     print("pairwise coprime")
    # elif setwise == 1:
    #     print("setwise coprime")      
    # else:
    #     print("not coprime")
    # return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
    if a < b:
        a,b = b,a
    a = a%b
    return gcd(b,a) if a!= 0 else b

def prime_list(a):
    for i in range(2,a):
        if a < i**2:
            break
        if a%i == 0:
            yield i
            if i != a//i:
                yield a//i
    yield a

def main():
    n = int(input())
    A = list(map(int,input().split()))
    prime = [True for i in range(int(1e6+2))]
    setwise = A[0]
    pairwise = True
    prime_set = set()
    for a in A:
        if pairwise:
            for p in prime_list(a):
                if p not in prime_set:
                    prime_set.add(p)
                else:
                    pairwise = False
        #     if pairwise and prime[p] == True:
        #         prime[p] = False
        #         index = p
        #         while index < len(prime):
        #             prime[index] = False
        #             index += p
        #     else:
        #         pairwise = False
        #         break

        setwise = gcd(setwise,a)

    # pairwise = True
    # setwise = A[0]
    # for a in A[1:]:
    #     if pairwise and gcd(A[0],a) != 1:
    #         pairwise = False

    #     setwise = gcd(setwise,a)
    if pairwise:
        print("pairwise coprime")
    elif setwise == 1:
        print("setwise coprime")      
    else:
        print("not coprime")
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd

n = int(input())
A = list(map(int, input().split()))
maxA = 10**6+5

c = [0]*(maxA+1)
for a in A: c[a] += 1

memo = [False]*(maxA+1)
for i in range(2, maxA+1):
    if memo[i]: continue
    memo[i] = True
    cnt = c[i]
    for j in range(i*i, maxA+1, i):
        memo[j] = True
        cnt += c[j]
    if cnt >= 2:
        break
else:
    print('pairwise coprime')
    exit()

g = 0
for a in A:
    g = gcd(g, a)
if g == 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

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):
    while search_list[0]**2 <= 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(78498)
#p=get_primenumber(1010)
p=get_primenumber(10100)

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.sort()
    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()


for pp in p:
    lap=0
    for ai in ap:
        if  ai%pp==0:
            lap+=1
        if lap>=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):
    while search_list[0]**2 <= 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(78498)
#p=get_primenumber(1010)
p=get_primenumber(10100)

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()


for pp in p:
    lap=0
    for ai in ap:
        if  ai%pp==0:
            lap+=1
        if lap>=2:
            print("setwise coprime")
            sys.exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
n=int(input())
a=list(map(int,input().split()))
g=gcd(a[0],a[1])
for i in range(n-2):
    g=gcd(g,a[i+2])
if g!=1:
    print("not coprime")
    exit()
temp=[i for i in range(10**6+5)]
p=2
while p*p<=10**6+5:
    if temp[p]==p:
        for q in range(2*p,10**6+5,p):
            if temp[q]==q:
                temp[q]=p
    p+=1
ans=[0]*(10**6+10)
for j in a:
    count=set()
    while j>1:
        count.add(temp[j])
        j//=temp[j]
    for k in count:
        ans[k]+=1
if max(ans)!=1:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys


def main():
    N = int( sys.stdin.readline() )
    A_list = list(map(int, sys.stdin.readline().split()))


    def get_factor(n :int) -> list:
        ans = set()
        
        for i in range(2, int(n**(1/2)+1) ):  # exclude "factor 1" and "max factor"
            if  n % i == 0:
                ans.add(i)
                
                d = n / i
                if (d != i) and (d % 1 == 0):
                    ans.add( int(d) )
        
        return ans


    factor = [None] * N

    for i in range(N):
        factor[i] = get_factor( A_list[i] )
    

    for i in range(1, N):
        f1 = factor[i-1] | {A_list[i-1]}
        f2 = factor[i] | {A_list[i]}
        common = f1 & f2

        if common:
            break
    
    else:
        print("pairwise coprime")
        return


    f = factor[0] | {A_list[0]}

    for i in range(1, N):
        f &= ( factor[i] | {A_list[i]} )
    
    
    if (not f):
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
import sys
from functools import lru_cache
sys.setrecursionlimit(10000000)

N = int(input())
A_list = [int(e) for e in input().split()]

#pairwise coprime …… 素因数分解したとき、共通のものが1個もない
#setwise coprime　…… 素因数分解したとき、全てで共通のものがない

#試し割の結果の辞書を求める
def make_trial_division_dict(n):
    #import math
    td_dict = dict()
    for i in range(2,n+1):
        if i not in td_dict:
            td_dict[i] = i
            for j in range(2,1+n//i):
                if j*i not in td_dict:
                    td_dict[j*i] = i
    td_dict[1] = 1
    return td_dict

#試し割結果の辞書を利用して素因数分解する
#@lru_cache(maxsize=None)
#def high_speed_prime_factorization(n):
#    pf_list = list()
#    pf_list.append(td_dict[n])
#    
#    if n//td_dict[n] == 1:
#        if n!=1:
#            pf_list.append(1)
#        return pf_list
#    else:
#        pf_list.extend(high_speed_prime_factorization(n//td_dict[n]))
#        return pf_list

td_dict = make_trial_division_dict(max(A_list))

all_pf = set()    #含まれる素因数がすべて集約される
common_pf = set() #共通する素因数が集約される
all_pf.add(td_dict[A_list[0]])
common_pf.add(td_dict[A_list[0]])
is_pairwise = True

#print(A_list[0],set(high_speed_prime_factorization(A_list[0])))

for i in range(1,len(A_list)):
    A_pf = {td_dict[A_list[i]]}
    common_pf &= A_pf 
    
    #print(A_list[i],set(high_speed_prime_factorization(A_list[i])))
    
    if is_pairwise and len(all_pf&A_pf)!=0 and (all_pf&A_pf)!={1}:
        is_pairwise = False
    else:
        all_pf |= A_pf

if is_pairwise:
    print("pairwise coprime")
elif len(common_pf) == 0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

Ones = A.count(1)
R = max(A)
nums = [0]*(R+1)
D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i

for a in A:
    tmp = a
    while tmp > 1:
        nums[D[tmp]] += 1
        while tmp > 1 and tmp%D[tmp] == 0:
            tmp //= D[tmp]
y = max(nums)
if y < 2:
    print('pairwise coprime')
elif y-Ones < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

Ones = A.count(1)
R = max(A)
nums = [0]*(R+1)
D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i

for a in A:
    tmp = a
    while tmp > 1:
        nums[D[tmp]] += 1
        while tmp > 1 and tmp%D[tmp] == 0:
            tmp //= D[tmp]
y = max(nums)
if y < 2:
    print('pairwise coprime')
elif y < N-Ones:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

Ones = A.count(1)
R = max(A)
nums = [0]*(R+1)
D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i

for a in A:
    tmp = a
    while tmp > 1:
        nums[D[tmp]] += 1
        while tmp > 1 and tmp%D[tmp] == 0:
            tmp //= D[tmp]
print(D)
y = max(nums)
if y < 2:
    print('pairwise coprime')
elif y < N-Ones:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

R = max(A)
nums = [0]*(R+1)
D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i

for a in A:
    tmp = a
    while tmp > 1:
        nums[D[tmp]] += 1
        while tmp > 1 and tmp%D[tmp] == 0:
            tmp //= D[tmp]

y = max(nums)
if y < 2:
    print('pairwise coprime')
elif y < N:
    print('setwise coprime')
else:
    print('not 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)
sqrt_max_A = math.ceil(max_A ** 0.5)
sieve = list(range(2, max_A+1))
prime = list(range(max_A+1))
while len(sieve) > 0 and sieve[0] <= sqrt_max_A:
    p = sieve[0]
    prime[p]= p
    new_sieve = []
    for s in sieve:
        if s % p == 0:
            prime[s] = p
        else:
            new_sieve.append(s)
    sieve = new_sieve
factors = {}
pairwise = True
for a in A:
    if a == 1:
        continue
    while prime[a] != a:
        if prime[a] in factors:
            pairwise = False
            break
        factors[prime[a]] = True
        p = prime[a]
        while a % p == 0:
            a //= p
    if a in factors:
        pairwise = False
    else:
        factors[a] = 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:
import math
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
max_A = max(A)
sqrt_max_A = math.ceil(max_A ** 0.5)
sieve = list(range(2, max_A+1))
prime = list(range(max_A+1))
while len(sieve) > 0 and sieve[0] <= sqrt_max_A:
    p = sieve[0]
    prime[p]= p
    new_sieve = []
    for s in sieve:
        if s % p == 0:
            prime[s] = p
        else:
            new_sieve.append(s)
    sieve = new_sieve
factors = {}
pairwise = True
for a in A:
    while prime[a] != a:
        if prime[a] in factors:
            pairwise = False
            break
        factors[prime[a]] = True
        p = prime[a]
        while a % p == 0:
            a //= p
    if a in factors:
        pairwise = False
    else:
        factors[a] = 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:
import math
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
if 1 in A:
    print('setwise coprime')
else:
    max_A = max(A)
    sqrt_max_A = math.ceil(max_A ** 0.5)
    sieve = list(range(2, max_A+1))
    prime = list(range(max_A+1))
    while True:
        p = sieve[0]
        prime[p]= p
        if p > sqrt_max_A:
            break
        new_sieve = []
        for s in sieve:
            if s % p == 0:
                prime[s] = p
            else:
                new_sieve.append(s)
        sieve = new_sieve
    factors = {}
    pairwise = True
    for a in A:
        while prime[a] != a:
            if prime[a] in factors:
                pairwise = False
                break
            factors[prime[a]] = True
            p = prime[a]
            while a % p == 0:
                a //= p
        if a in factors:
            pairwise = False
        else:
            factors[a] = 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:
import sys
import math

prime = []

for i in range(2,100001):
    det = 0
    for j in range(2,int(i**(1/2))+1):
        if i%j==0:
            det = -1
            break
    if det == 0:
        prime.append(i)

#print(len(prime))

N = int(input())
A = list(map(int,input().split()))
B = []###Aのうち1ではないもの
det = False###Aが1を含んでいたか否か

for i in range(N):
    if A[i] == 1:
        det = True
    else:
        B.append(A[i])

if len(B) <= len(prime):

    m = 1

    for p in prime:
        count = 0
        for b in B:
            if b%p==0:
                count += 1
        m = max(m,count)
        if m >= 2:
            break
    
    if m == 1:
        print('pairwise coprime')
        sys.exit(0)

if det:
    print('setwise 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 
N = int(input())
A = list(map(int, input().split()))
m = [0] * int(1e6+1)
for i in range(N):
    m[A[i]] += 1
pw = True
for p in range(2, N+1):
    c = 0
    for i in range(p, len(m), p):
        c += m[i]
    if c > 1:
        pw = False
        break
if pw:
    print('pairwise coprime')
    exit()
d = A[0]
for i in range(N):
    d = math.gcd(d, A[i])
if d == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math 
N = int(input())
A = list(map(int, input().split()))
m = [0] * int(1e6+1)
for i in range(N):
    m[A[i]] = 1
pw = True
for p in range(2, N+1):
    c = 0
    for i in range(p, len(m), p):
        c += m[i]
    if c > 1:
        pw = False
        break
if pw:
    print('pairwise coprime')
    exit()
d = A[0]
for i in range(N):
    d = math.gcd(d, A[i])
if d == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
    if a < b:
        a,b = b,a
    a = a%b
    return gcd(b,a) if a!= 0 else b

def prime_list(a):
    for i in range(2,a):
        if a < i**2:
            break
        if a%i == 0:
            yield i

def main():
    n = int(input())
    A = list(map(int,input().split()))
    A = sorted(A)
    prime = [True for i in range(int(1e6+2))]
    setwise = A[0]
    pairwise = True
    prime_set = set()
    for a in A:
        if pairwise:
            for p in prime_list(a):
                if p not in prime_set:
                    prime_set.add(p)
                else:
                    pairwise = False
        #     if pairwise and prime[p] == True:
        #         prime[p] = False
        #         index = p
        #         while index < len(prime):
        #             prime[index] = False
        #             index += p
        #     else:
        #         pairwise = False
        #         break

        setwise = gcd(setwise,a)

    # pairwise = True
    # setwise = A[0]
    # for a in A[1:]:
    #     if pairwise and gcd(A[0],a) != 1:
    #         pairwise = False

    #     setwise = gcd(setwise,a)
    if pairwise:
        print("pairwise coprime")
    elif setwise == 1:
        print("setwise coprime")      
    else:
        print("not coprime")
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
    if a < b:
        a,b = b,a
    a = a%b
    return gcd(b,a) if a!= 0 else b

def prime_list(a):
    for i in range(2,int(a**0.5)+1):
        if a%i == 0:
            yield i

def main():
    n = int(input())
    A = list(map(int,input().split()))
    A = sorted(A)
    prime = [True for i in range(int(1e6+2))]
    setwise = A[0]
    pairwise = True
    for a in A:
        for p in prime_list(a):
            if pairwise and prime[p] == True:
                prime[p] = False
                index = p
                while index < len(prime):
                    prime[index] = False
                    index += p
            else:
                pairwise = False
                break

        setwise = gcd(setwise,a)

    # pairwise = True
    # setwise = A[0]
    # for a in A[1:]:
    #     if pairwise and gcd(A[0],a) != 1:
    #         pairwise = False

    #     setwise = gcd(setwise,a)
    if pairwise:
        print("pairwise coprime")
    elif setwise == 1:
        print("setwise coprime")      
    else:
        print("not coprime")
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def find_gcd(x, y):
    x=max(x,y)
    y=min(x,y)
    while (y): 
        x, y = y, x % y 
    return x 
def fun(l):
  num1=l[0] 
  num2=l[1] 
  gcd=find_gcd(num1,num2) 
  for i in range(len(l)-1):
    gcd=find_gcd(l[i],l[i+1])
    if gcd!=1:
      pass
  else:
    print("pairwise coprime")
    return 1
  gcd=l[0]
  for i in range(2,len(l)):
    gcd=find_gcd(gcd,l[i])
  if gcd==1:
    print("setwise coprime")
    return 1

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

x=fun(l)
if x!=1:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
def find_gcd(x, y):
    x=max(x,y)
    y=min(x,y)
    while (y): 
        x, y = y, x % y 
    return x 
def fun(l):
  num1=l[0] 
  num2=l[1] 
  gcd=find_gcd(num1,num2) 
  for i in range(len(l)-1):
    gcd=find_gcd(l[i],l[i+1])
    if gcd!=1:
      pass
  else:
    print("pairwise coprime")
    return 1
  gcd=l[0]
  for i in range(2,len(l)):
    gcd=find_gcd(gcd,l[i])
  if gcd==1:
    print("setwise coprime")
    return 1

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

x=fun(l)
if x!=1:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
    if a < b:
        a,b = b,a
    a = a%b
    return gcd(b,a) if a!= 0 else b

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


    pairwise = True
    setwise = A[0]
    for a in A[1:]:
        if pairwise and gcd(A[0],a) != 1:
            pairwise = False

        setwise = gcd(setwise,a)
    if pairwise:
        print("pairwise coprime")
    elif setwise == 1:
        print("setwise coprime")      
    else:
        print("not coprime")
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def find_gcd(x, y): 
    while (y): 
        x, y = y, x % y 
    return x 
def fun(l):
  num1=l[0] 
  num2=l[1] 
  gcd=find_gcd(num1,num2) 
  for i in range(len(l)-1):
    gcd=find_gcd(l[i],l[i+1])
    if gcd!=1:
      pass
  else:
    print("pairwise coprime")
    return 1
 
  for i in range(2,len(l)):
    gcd=find_gcd(gcd,l[i])
  if gcd==1:
    print("setwise coprime")
    return 1

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

x=fun(l)
if x!=1:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
    if a < b:
        a,b = b,a
    a = a%b
    return gcd(b,a) if a!= 0 else b

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

    last_a = A[0]
    pairwise = True
    setwise = gcd(A[0],A[1])
    for a in A[1:]:
        if pairwise and gcd(last_a,a) == 1:
            last_a = a
        else:
            pairwise = False

        setwise = gcd(setwise,a)
    if pairwise:
        print("pairwise coprime")
    elif setwise == 1:
        print("setwise coprime")      
    else:
        print("not coprime")
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd

def main():
    n = int(input())
    A = list(map(int,input().split()))
    
    last_a = A[0]
    all_one = True
    for a in A[1:]:
        if gcd(last_a,a) == 1:
            last_a = a
        else:
            all_one = False
            break
    if all_one:
        print("pairwise coprime")
        return

    all_gcd = A[0]
    for a in A:
        all_gcd = gcd(all_gcd,a)
    if all_gcd == 1:
        print("setwise coprime")
        return
    

    

            
    print("not coprime")
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
n = int(input())
s = list(map(int, input().split()))
s.sort()
dp = [0] * ((10 ** 6) + 100)

res = s[0]
for ss in s:
    dp[ss] += 1
    res = gcd(res, ss)

A = max(s)
pairwise = True
setwise = (res == 1)

for i in range(2, int((A + 1)**0.5+1)):
    cnt = 0
    for j in range(i, A + 1, i):
        cnt += dp[j]
    if cnt > 1:
        pairwise = False
        break

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

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd

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

b = gcd(a[0], a[1])
for i in range(2, n):
    b = gcd(b, a[i])
if b != 1:
    print('not coprime')
else:
    
    c = set()
    for j in a:
        for i in range(2, int(j**0.5)+1):
            while n%i == 0:
                if i in c:
                    print('setwise coprime')
                    sys.exit()
                c.add(i)
                n //= i
            if n != 1:
                c.add(n)
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
sieve = list(range(2, 1001))
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')