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:
from math import gcd

# 10**3まで素数列挙
N = 1000
L = list(range(2,N+1))
p = list()
while L[0]**2<=N:
    tmp = L[0]
    p.append(tmp)
    L = [e for e in L if e%tmp!=0]
p = p + L

def function(n):
    memo = set()
    for i in p:
        if n % i == 0:
            c = 0
            while n % i == 0:
                c += 1
                n //= i
            memo.add(i)
    if n > 1:
        memo.add(n)
    return memo

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

# n個の数のgcd
total_gcd = A[0]
for a in A:
    total_gcd = gcd(total_gcd, a)
    if total_gcd == 1:
        break


if total_gcd == 1:  # pairwiseか setwise
    setA = set(A)
    if len(setA) > len(p)+10: # 固有の
        print("setwise coprime")
        exit()

    total = set()
    cnt = 0
    for a in A:
        s = function(a)
        total = total | s
        cnt += len(s)

    if len(total) != cnt:  # どこかに共通あり
        print("setwise coprime")
    else:
        print("pairwise coprime")

else: # setwiseかnot
    print("not coprime")
    exit()

Submission status: Wrong Answer

Solution code:
from math import gcd
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
p = primes(1000)
c = [0]*1001
# print(len(p))

n = int(input())
# a = [999983] * 100 + [1]
a = list(map(int,input().split()))
a = [1] * (1 in a) + [i for i in a if i != 1]
# print(a)
n = len(a)

if n>80000:
    print("not coprime")
    exit()
g = 0
f = 1
c1 = 0
if len(set(a)) != n:
    f = 0
for i in a:
    g = gcd(g,i)
    if f == 1:
        for j in p:
            if i%j == 0:
                c[j] += 1
                if c[j] > 1:
                    f = 0
if g == 1:
    if f == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")
# print(a,g,f)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
import itertools

def gcd(a,b):
    if(b>a):
        a,b=b,a
    i=b
    while i>0:
        if(a%i==0 and b%i==0):
            return i
        i-=1

mod = 1000000000+7
n = int(input())
A = [int(a) for a in input().strip().split()]
s = sum(A)%mod
S = 0

for a in A:
    s = s-a
    S += (s*a)%mod
S = (S%mod)%1000001

if S in A:
    print("not coprime")

else:
    c =False
    for (a, b) in itertools.combinations(A,2):
        if gcd(a,b)!=1:
            True
            print("set comprime")
            break
        else:
            pass
    if not c:
        print("pair comprime")

Submission status: Wrong Answer

Solution code:
import os
import heapq
import sys,threading
import math as mt
import bisect
import operator
from collections import defaultdict
sys.setrecursionlimit(10**5)
from io import BytesIO, IOBase
def gcd(a,b):
    if b==0:

        return a
    else:
        return gcd(b,a%b)
def power(x, p,m):
    res = 1
    while p:
        if p & 1:
            res = (res * x) % m
        x = (x * x) % m
        p >>= 1
    return res
def inar():
    return [int(k) for k in input().split()]
dic={}
def lcm(num1,num2):
    return (num1*num2)//gcd(num1,num2)

# Python3 program to find prime factorization
# of a number n in O(Log n) time with
# precomputation allowed.


MAXN = 10**6+1
spf = [0 for i in range(MAXN)]
def sieve():
    spf[1] = 1
    for i in range(2, MAXN):
        spf[i] = i
    for i in range(4, MAXN, 2):
        spf[i] = 2

    for i in range(3, mt.ceil(mt.sqrt(MAXN))):

        # checking if i is prime
        if (spf[i] == i):

            # marking SPF for all numbers
            # divisible by i
            for j in range(i * i, MAXN, i):
                if (spf[j] == j):
                    spf[j] = i

                # A O(log n) function returning prime


# factorization by dividing by smallest
# prime factor at every step
def getFactorization(x):
    ret = defaultdict(int)
    while x != 1:
        ret[spf[x]]+=1
        x = x // spf[x]

    return ret

#
# # Driver code
#
# # precalculating Smallest Prime Factor
#
# x = 12246
# print("prime factorization for", x, ": ",
#       end="")
#
# # calling getFactorization function
# p = getFactorization(x)
#
# for i in range(len(p)):
#     print(p[i], end=" ")


# This code is contributed
# by Mohit kumar 29


def main():
    #t=int(input())
    global dic
    t=1
    for _ in range(t):
        n=int(input())
        arr=inar()
        sieve()
        coprime=True
        dic=defaultdict(int)
        for i in range(n):
            take=getFactorization(arr[i])
            #print(take)
            for key in take.keys():
                dic[key]+=1
                if dic[key]>1:
                    coprime=False
                    break
            if coprime==False:
                break
        if coprime:
            print("pairwise coprime")
        else:
            gc=arr[0]
            for i in range(n):
                gc=gcd(arr[i],gc)
            if gc==1:
                print("setwise coprime")
            else:
                print("not coprime")





BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def _init_(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def _init_(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "_main_":
    main()
    #threadin.Thread(target=main).start()

Submission status: Wrong Answer

Solution code:
from math import gcd

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

g = A[0]
l = A[0]
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if gcd(l, a) == 1:
    print('pairwise coprime')
    exit()
  else:
    l = l*a//gcd(l, a)
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

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

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

sa = set(A)
if len(sa) < N:
    print('setwise coprime')
    exit()

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
small_primes = []
while p*p <= MAXN:
    if sieve[p]:
        small_primes.append(p)
        c = 0
        if p in sa: c += 1
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
            if q in sa:
                c += 1
                if c > 1:
                    print('setwise coprime')
                    exit()
    p += 1

st = set()
for a in A:
    for p in small_primes:
        while a%p==0:
            a //= p
        if a==1: break
    else:
        assert a > 1000
        if a in st:
            print('setwise coprime')
            exit()
        st.add(a)

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
def eratos(n):
    isprime = [0 for i in range(n+1)]
    # isprime[0] = 0
    isprime[1] = 1
    for i in range(2, int(math.sqrt(n))+1):
        if isprime[i] == 0:
            j = i
        while j <= n:
            if isprime[j] == 0:
                isprime[j] = i
            j = j + i
    return isprime        

N = int(input())
A = list(map(int, input().split()))
isprime = eratos(10**6)
one_count = 0
ans = []
for ai in A:
    if ai == 1:
        one_count += 1
        continue
    ans += [isprime[ai]]
set_ans = set(ans)
# print(set_ans)
if len(set_ans) == (N - one_count):
    print('pairwise coprime')
elif len(set_ans) == 1 and one_count == 0:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
conf = False

def test_prime(m, check_list):
    global conf
    for i in range(2,int(m**0.5)+1):
        if m % i == 0:
            if check_list[i] >= 1:
                conf = True
            check_list[i] += 1
    return check_list

def main():
    N = int(input())
    A = list(map(int, input().split()))
    check_list = [0]*(max(A))
    for i in range(len(A)):
        check_list = test_prime(A[i], check_list)
    if max(check_list) == len(A):
        return "not coprime"
    else:
        if conf:
            return "setwise coprime"
        else:
            return "pairwise coprime"

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
import numpy as np

def seachPrimes(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

primes = seachPrimes(10**3)
n = int(input())
A = list(map(int, input().split()))


cnts = []
for prime in primes:
    cnt = 0
    for a in A:
        if a % prime == 0:
            cnt += 1
    cnts.append(cnt)
if max(cnts) == n or min(A) == max(A):
    print("not coprime")
elif max(cnts) >= 2:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
import math

if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    check_pairwise()
    check_set()
    return


def check_pairwise():
    active = set()
    for i in range(0, n):
        pp = getprimes(a[i])
        for p in pp:
            if p in active:
                return
            else:
                active.add(p)
    print("pairwise coprime")
    exit()



def check_set():
    active = getprimes(a[0])
    for i in range(1, n):
        if not a[i] % a[i-1] == 0:
            rm = []
            for act in active:
                if not a[i] % act == 0:
                    rm.append(act)
            for r in rm:
                active.remove(r)
                if not active:
                    print("setwise coprime")
                    exit()
    if not active:
        print("setwise coprime")
        exit()
    print("not coprime")
    exit()




def getprimes(num):
    if num in primes:
        return set([num])
    pp = set()
    for p in iterprimes:
        if p > int(math.sqrt(num)+2):
            break
        if num % p == 0:
            pp.add(p)

    return pp




def n_primes(n):
    nums = list(range(0, n + 1))
    primes = []
    for i in range(2, n + 1):
        num = nums[i]
        if num != 0:
            primes.append(num)
            for i in range(0, n // num + 1):
                nums[i * num] = 0
    return primes


n = RN()
a = sorted(RA())
iterprimes = n_primes(10 ** 6)
primes = set(iterprimes)
solve()

Submission status: Wrong Answer

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

for v in itertools.combinations(a, 2):
    c+=1
    print(math.gcd(v[0],v[1]))
    if math.gcd(v[0],v[1]) == 1:
        ans += 1

if c==ans:
    print('pairwise coprime')
    exit()

m=min(a)
pf={}
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
print(pf)

tmp = 0
for v in pf:
    for i in range(len(a)):
        tmp += a[i]%v
    if tmp==0:
        print('not coprime')
        exit()
    else:
        print('setwise coprime')
        exit()
    tmp=0

Submission status: Wrong Answer

Solution code:
import math

def sieve(data,num):
    return [x for x in data if (x % num != 0)]

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

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

prime = [i for i in prime if M > i]

# 累積GCD
left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
    left[i + 1] = (math.gcd(left[i], a[i]))
    right[n - i - 1] = (math.gcd(right[n - i], a[n - 1 - i]))

#print(left,right)
if left[n] != 1 or right[0] != 1:
    print("not coprime")
else:
    count = 0
    for i in prime:
        if len(sieve(a,i)) != n-1:
            count = 1
            break
    if count == 1:
        print("setwise coprime")
    else:
        print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[0]*(10**6+100)
x=0
for m in a:
  l[m]+=1

j=2
#print(l)


while j <10**3+1:
  c=0
  k=1
  while j*k<=10**6+1 :
    if l[j*k]>0:
      c+=l[j*k]
    k+=1

  if c==n:
    print("not coprime")
    exit()
  elif c>1:
    x=1
  j+=1 
  
if x==1:
  print("setwise coprime")
else:
  print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
def g(a):
    al=len(a)
    if al==2:
        return gcd(a[0],a[1])
    elif al==1:
        return a[0]
    return gcd(g(a[:al//2]),g(a[al//2:]))
n=int(input())
a=list(map(int,input().split()))
if g(a)!=1:
    print("not coprime")
    exit()
one=a.count(1)
if len(a)-one>168:
    print("setwise coprime")
    exit()
a=[i for i in a if i!=1]
for i in range(len(a)-1):
    for j in range(i+1,len(a)):
        if gcd(a[i],a[j])!=1:
            print("setwise coprime")
            exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys, math

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))

ok = True
tmp = A[0]
for a in A[1:]:
    tmp = math.gcd(a, tmp)
    if tmp != 1:
        ok = False

if tmp != 1:
    print("not coprime")
else:
    if ok:
        print("pairwise coprime")
    else:
        print("setwise coprime")

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]


N = z()
A = zz()
lim = max(A)
'pairwise coprime'
pari_flg = True

set_flg = True
res = A[0]
for i in range(1, N):
    res = gcd(res, A[i])
    if (res != 1):
        pari_flg = False
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 itertools
import collections
def prime_factor_table(n):
    table = [0] * (n + 1)
    
    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i
    
    return table

def prime_factor(n, prime_factor_table):
    prime_count = dict()
    
    while prime_factor_table[n] != 0:
        prime_count[prime_factor_table[n]] = 1
        n //= prime_factor_table[n]
    prime_count[n] = 1
    
    return prime_count

pp = prime_factor_table(10**6)
#n = 18
#y = prime_factor(n, pp)
#print(y)
N, = map(int, input().split())
X = list(map(int, input().split()))
d = dict()
f = 0
for x in X:
    y = prime_factor(x, pp)
    for k in y:
        if k in d:
            f = 1
            d[k] += 1
        else:
            d[k] = 0
#            continue
#        d.add(k)
#    if f:
#        break
if f:
    m = 0
#    print(d)
    for k in d:
        m = max(m, d[k])
#    print(m)
    if m != N:
        print("setwise coprime")
    else:
        print("not coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
from math import gcd
n=int(stdin.readline())
a=list(map(int,stdin.readline().split()))
s=set(a)
p=2;d={}
N=max(a)+2
primes=[1]*N;not_pairwise=0
vis=set()
while p*p<=N:
    if primes[p]:
        for mul in range(p,N,p):
            primes[mul]=0
            if mul in s and mul not in vis:
                vis.add(mul)
                d[p]=d.get(p,0)+1
                if d[p]>=2:not_pairwise=1;break;
        if not_pairwise:break
    p+=1
g=a[0]
for v in a:
    g=gcd(g,v)
if not_pairwise==0:print('pairwise coprime')
elif g==1:print('setwise coprime')
else:print('not coprime')

Submission status: Wrong Answer

Solution code:
def gen_prime(n) :
    arr = [True] * (n+1)
    arr[0] = False
    arr[1] = False

    for i in range(len(arr)) :
        if i**2 >= n :
            break

        if arr[i] :
            idx = i*2
            while idx <= n :
                arr[idx] = False
                idx += i

    return [p for p in range(len(arr)) if arr[p]]

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

    p_list = gen_prime(10**3)
    p_cnt = [0] * len(p_list)

    for i in range(len(a)) :
        for j in range(len(p_list)) :
            if a[i] < p_list[j] :
                break

            if a[i] % p_list[j] == 0 :
                p_cnt[j] += 1

    if max(p_cnt) == n :
        print("not coprime")
    
    elif 2 <= max(p_cnt) < n :
        print("setwise coprime")

    else :
        print("pairwise coprime")

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
ans1 = A[0]
ans2 = 0
f = True
for i in range(1, N):
    ans1 = math.gcd(ans1, A[i])
    ans2 = math.gcd(A[i-1],A[i])

    if (ans2 > 1):
        f = False

if f:
    print('pairwise coprime')
else:
    if ans1==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
# O(n^2)未満
import math
import sys
n = int(input())
a = list(map(int, input().split()))

ispair = True
isset = False

gcds = [0 for i in range(n-1)]
prev = a[0]
for i in range(1, n):
    prev = math.gcd(a[i], prev)
if prev == 1:
    isset = True
else:
    print("not coprime")
    exit(0)

dp = [a[0] for i in range(n)]
for i in range(1, n-1):
    dp[i] = int(a[i] * a[i-i] / math.gcd(a[i], a[i-1]))
# print(dp)

for i in range(1, n):
    if math.gcd(a[i], dp[i-1]) != 1:
        print("setwise coprime")
        exit(0)
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math

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

ans = A[0]
for i in range(1, N):
    ans = math.gcd(ans, A[i])

if ans == 1:
    print('setwise coprime')
    exit()

if sum(1 for i in range(0,N-1) for j in range(i+1,N) if math.gcd(A[i], A[j]) != 1) == 0:
    print('pairwise coprime')
    exit()

print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return [a[0] for a in arr]

N = int(input())
A = sorted([int(i) for i in input().split()])
dict_A = defaultdict(int)
dep_flag = False
for a in A:
  dict_A[a] += 1
  if a != 1 and dict_A[a] >= 2:
    dep_flag=True
if dep_flag == False:  
  all_flag = True
  devisors = set()
  for n in range(N-1):
      if n == 0:
          g = gcd(A[n],A[n+1])
      else:
          g = gcd(A[n+1],g)
      if g != 1:
        break
      temp = factorization(A[n])
      if temp == [1]:
        pass
      else:
        for t in temp:
            if t in devisors:
                all_flag=False
            else:
                devisors.add(t)
  if all_flag and g == 1:
      print('pairwise coprime')
  elif g==1:
      print('setwise coprime')
  else:
      print('not coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    def factorization(n):
        ret = set()
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp % i == 0:
                cnt = 0
                while temp % i == 0:
                    cnt += 1
                    temp //= i
                ret.add(i)

        if temp != 1:
            ret.add(temp)

        if len(ret) == 0 and n != 1:
            ret.add(n)

        return ret
    flag = False
    s = set()
    for x in A:
        g = gcd(g,x)

    if flag:
        print("pairwise coprime")
    elif g == 1:
        print("setwise coprime")

    else:
        print("not coprime")


main()

Submission status: Wrong Answer

Solution code:
def main():
    from math import gcd
    MINFact = [-1] * (10**6 + 10)
    MINFact[0] = 0
    MINFact[1] = 1

    def Eratosthenes(sup: int) -> set:
        primes = [True for i in range(sup+1)]
        primes[0] = False
        primes[1] = False
        for i in range(2, sup+1):
            if sup < i*i:
                break
            if primes[i]:
                MINFact[i] = i
                mul = 2
                while i*mul <= sup:
                    primes[i*mul] = False
                    if MINFact[i*mul] == -1:
                        MINFact[i*mul] = i
                    mul += 1

    def prime_factor(n):
        while n != 1:
            prime = MINFact[n]
            if prime <= 1:
                break
            x = n // prime
            n -= x * prime
            B[prime] += 1

    _ = int(input())
    A = [int(i) for i in input().split()]
    g = A[0]
    for a in A:
        g = gcd(g, a)
    Eratosthenes(10**6 + 5)
    B = [0]*(10**6 + 5)
    for a in A:
        prime_factor(a)
    # 素因数分解したのをBにいれる
    # 1より大きいのがあったら gcd != 1 のペアが存在する
    if g != 1:
        print("not coprime")
    elif max(B) <= 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = [int(x) for x in input().split()]
P = [2]
for L in range(3, math.ceil(math.sqrt(max(A))), 2): 
    if all(L % L2 != 0 for L2 in P):  
        P.append(L)
lst = [0] * len(P)
for i, p in enumerate(P):
    cnt = 0
    for a in A:
        cnt += a % p == 0
    lst[i] = cnt
tmp = max(lst)
if tmp == 1:
    print('pairwise coprime')
elif tmp == N:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import math

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

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

if ans!=1:
    print('not coprime')

else:
    for l in range(1,n):
        if a[l]==a[l-1] and a[l]!=1:
            print('setwise coprime')
            exit()
    for i in range(min(1000,n-1)):
        for k in range(min(i+1,n-1),min(n,1000)):
            if math.gcd(a[i],a[k])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:

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

def get_primenumber(N):
    prime_list = [2]
    for num in range(3,N+1,2):
      if all( num % prime != 0 for prime in prime_list):
        prime_list.append(num)
    return prime_list

sosu=get_primenumber(1000)

flag=False
for i in sosu:
    cnt=0
    for a in A:
        if a%i ==0:
            cnt+=1
    
    if cnt==len(A):
        print("not coprime")
        exit()
        
    if cnt>1:
        flag=True

if flag:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
import sys
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

n=int(input())
alist=list(map(int, input().split()))
amax=max(alist)
if n<=len(primes(amax+1)):
  blist=[0]*1000001
  for i in alist:
    for j in factorization(i):
      blist[j[0]]+=1
  cnt=1
  for i in primes(amax+1):
    cnt=max(cnt,blist[i])
  if cnt==1:
    print('pairwise coprime')
    sys.exit()
num=alist[0]
for i in range(n):
  num=math.gcd(num,alist[i])
if num==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
def gen_prime(n) :
    arr = [True] * (n+1)
    arr[0] = False
    arr[1] = False

    for i in range(len(arr)) :
        if i**2 >= n :
            break

        if arr[i] :
            idx = i*2
            while idx <= n :
                arr[idx] = False
                idx += i

    return [p for p in range(len(arr)) if arr[p]]

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

    p_list = gen_prime(10**3)
    p_cnt = [0] * len(p_list)

    for i in range(len(a)) :
        for j in range(len(p_list)) :
            if a[i] < p_list[j] :
                break

            if a[i] % p_list[j] == 0 :
                p_cnt[j] += 1

    print(p_cnt)

    if max(p_cnt) == n :
        print("not coprime")
    
    elif 2 <= max(p_cnt) < n :
        print("setwise coprime")

    else :
        print("pairwise coprime")

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
check_list = [0]*1000010
conf = False

def test_prime(m):
    global check_list
    global conf
    for i in range(2,int(m**0.5)+1):
        if m % i == 0:
            if check_list[i] >= 1:
                conf = True
            check_list[i] += 1

def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(len(A)):
        test_prime(A[i])
    if max(check_list) == len(A):
        return "not coprime"
    else:
        if conf:
            return "setwise coprime"
        else:
            return "pairwise coprime"

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


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


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


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


def main():
    N = II()
    targets = LI()
    MAX_INT = max(targets) + 1
    counter = cl.Counter(targets)
    targets = set(targets)
    is_pw = True

    num_1 = counter[1]
    if num_1 > 1:
        N -= num_1 - 1

    if len(targets) != N:
        is_pw = False

    if len(targets) == 1:
        if 1 in targets:
            print("setwise coprime")
            return
        print("not coprime")
        return

    for i in range(2, MAX_INT):
        origin = i
        kosuu = 0
        while origin <= MAX_INT:
            if origin in targets:
                kosuu += 1
            origin += i

        if kosuu <= 1:
            continue
        elif kosuu < len(targets):
            is_pw = False
        else:
            print("not coprime")
            return

    if is_pw:
        print("pairwise coprime")
        return
    print("setwise coprime")


main()