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 os
import sys

import numpy as np


def solve(inp):
    aaa = inp[1:]
    aaa = aaa[aaa != 1]
    n = len(aaa)
    if n > 80000:
        return -1
    if n == 0:
        return 1
    PRIMES = [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]
    pairwise = 1
    for p in PRIMES:
        exists_not_multiple = 0
        multiple_count = 0
        for i in range(n):
            if aaa[i] % p == 0:
                multiple_count += 1
                aaa[i] //= p
                while aaa[i] % p == 0:
                    aaa[i] //= p
            else:
                exists_not_multiple = 1

        if exists_not_multiple == 0:
            return -1
        if multiple_count > 1:
            pairwise = 0

    if pairwise == 0:
        return 0

    if (aaa == 1).all():
        return 1

    if len(np.unique(aaa)) == n:
        return 1
    else:
        return 0


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(['setwise coprime', 'pairwise coprime', 'not coprime'][ans])

Submission status: Wrong Answer

Solution code:
# https://cs.stackexchange.com/questions/93030/algorithm-for-checking-if-a-list-of-integers-is-pairwise-coprime

import math
n = int(input())
nums = list(map(int, input().split()))

gcd_ = nums[0]
for num in nums[1:]:
    gcd_ = math.gcd(gcd_, num)

if gcd_ >= 2:
    print('not coprime')
    exit()

mod = 10**9 + 7
lcm_ = nums[0]
product = nums[0]
for num in nums[1:]:
    lcm_ = num * lcm_ // math.gcd(num, lcm_)
    lcm_ %= mod
    product *= num
    product %= mod

if product == lcm_:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = list(map(int,input().split()))
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
PA = 1
c = 0
k = 0
mflag = 12
mnum = 0
for i in range(N):
  tA = A[i]
  PA *= tA
  a = prime_factorize(tA)
  la = len(a)
  c += la
  if la < mflag:
    mflag = la
    mnum = A[i]
am = prime_factorize(PA)
am = set(am)
cm = len(am)
if cm == c:
  print('pairwise coprime')
  sys.exit()
A.remove(mnum)  
am = prime_factorize(mnum)
am = set(am)
lA = len(A)
for i in am:
  k = 0
  for j in range(lA):
    if A[j] % i == 0:
      k += 1
  if k == lA:
    print('not coprime')
    sys.exit()
print('setwise coprime')

Submission status: Wrong Answer

Solution code:
def gcd(x,y):
  return y if x%y==0else gcd(y,x%y)

N=int(input())

A=list(map(int,input().split()))
primes=[];
isprime=[1 for i in range(0,1001)];
for i in range(2,1001):
  if isprime[i]:
    primes.append(i)
    j=2;
    while i*j<=1000:
      isprime[i*j]=0;
      j+=1
s=set();
pc=1

for i in range(N):
  for p in primes:
    a=A[i];
    if(a%p==0):
      while(a%p==0):
        a//=p;
      if p in s:
        pc=0
      s.add(p)
      
    if a>1000:
      if a in s:
        pc=0
      s.add(a)

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

Submission status: Wrong Answer

Solution code:
n = int(input())
*a,=map(int, input().split())
a=sorted(a)
mapa=[0]*(10**6+1)

def func(m):
    for i in range(2,int(m**0.5)+1):
        if m%i==0:
            mapa[i]+=1
        while m%i==0:
            m//=i
    if m>1:
        mapa[m]+=1

for ai in a:
    func(ai)

tmp=max(mapa)
if tmp==n:
    print('not coprime')
elif tmp==1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n, *a = map(int, read().split())

    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

    d1 = defaultdict(int)
    for ae in a:
        t1 = factorization(ae)
        for t1e in t1:
            d1[t1e[0]] += 1

    d1v = d1.values()
    if max(d1v) == n:
        print('not coprime')
    elif all([i == 1 for i in d1v]):
        print('pairwise coprime')
    else:
        print('setwise coprime')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 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 can_factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  # ここにバグがないか心配
        if temp % i == 0:
            arr.append(i)

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

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

    return arr


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


N = a_int()
A = ints()
# A = [10**6] * 10**6

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
for a in A:
    g_set = gcd(g_set, a)
    for p in can_factorization(a):
        if cnt[p] != 0:
            flg = 0
        cnt[p] += 1


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

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

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

n = int(input())
x = list(map(int,input().split()))
mod = int(1e9 + 7)

prod = x[0]
lc = x[0]
gc = x[0]

for i in range(1, len(x)):
    prod = (prod * x[i]) % mod
    lc = lcm(lc, x[i]) % mod
    gc = gcd(gc, x[i])

if gc > 1: print ("not coprime")
elif lc == prod: print ("pairwise coprime")
else: print("setwise coprime")

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd


def func(A):
    if len(set(A)) != len(A):
        return False
    is_A = [False] * (10**6+1)
    for a in A:
        is_A[a] = True
    n = 0
    for i in range(2, 10**6+1, 2):
        if is_A[i]:
            n += 1
    if n > 1:
        return False
    for i in range(3, 10**6+1, 2):
        n = 0
        for j in range(i, 10**6+1, 2*i):
            if is_A[j]:
                n += 1
        if n > 1:
            return False
    return True


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    if func(A):
        print('pairwise coprime')
    elif reduce(gcd, A) == 1:
        print('setwise coprime')
    else:
        print('not coprime')
    

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from math import gcd


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


def factorize(N):  # 素因数分解
    for p in prime_list:
        if p * p > N:
            break
        if N % p == 0 and (p in num):
            print('setwise coprime')
            exit()
        while N % p == 0:
            N //= p
            num.add(p)
    if N > 1:
        if p in num:
            print('setwise coprime')
            exit()
        num.add(N)


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

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

prime_list = eratosthenes(10 ** 6)
num = set()
for ai in a:
    factorize(ai)
else:
    print('pairwise coprime')

Submission status: Wrong Answer

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

pairwise_flag=True
total_set=set()
common_set=set()
i_set = [set() for i in range(n)]

for i in range(n):
    tmp = a[i]
    for j in range(2,a[i]//2+1):
        if tmp%j ==0:
            while tmp%j==0:
                tmp//=j
            i_set[i].add(j)
            if pairwise_flag:
                if j in total_set:
                    pairwise_flag=False
    total_set = total_set.union(i_set[i])
    if i==0:
        common_set=i_set[i]
    else:
        common_set=common_set.intersection(i_set[i])

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

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    primes = []
    isprime = [True for i in range(1001)]
    for i in range(2, 1001):
        if isprime[i]:
            primes.append(i)
            for j in range(i * i, 1001, i):
                isprime[j] = False
    x = a[0]
    f = True
    cnt = [0 for i in range(1000001)]
    for val in a:
        x = gcd(x, val)
        for i in range(len(primes)):
            if val % primes[i] == 0:
                cnt[primes[i]] += 1
                while val % primes[i] == 0:
                    val //= primes[i]
            if val == 1:
                break
        if val > 0:
            cnt[val] += 1
    for i in range(2, n + 1):
        if cnt[i] > 1:
            f = False
            break
    if f:
        print('pairwise coprime')
    elif x == 1:
        print('setwise coprime')
    else:
        print('not coprime')



t = 1
while t > 0:
    solve()
    t -= 1

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:
            ret.add(n)

        return ret

    s = factorization(g)
    ls = len(s)
    flag = True
    for x in A[1:]:
        g = gcd(g, x)
        tmp = factorization(x)
        l = len(tmp)
        s |= tmp
        if len(s) != ls + l:
            flag = False
        ls = len(s)

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

    else:
        print("not coprime")


main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
p = [0 for _ in range(10**6)]
pr = [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]
#print(pr)
at = 0
for x in a:
  d = int(x)
  for y in pr:
    if d % y == 0:
      if p[y] == 1:
        at = 1
        #print(y)
      else:
        p[y] = 1
      while d % y == 0:
        d //= y
  if d != 1:
    p[d] += 1
  if at == 1:
    break
  #print(p)
if at == 0:
  print('pairwise coprime')
  exit()
now = int(a[0])
for x in a:
  big,sml = x,now
  while sml:
    #print(big,sml)
    big,sml = sml,big%sml
  now = big
  if now == 1:
    print('setwise coprime')
    exit()
  #print(now)
print('not coprime')

Submission status: Wrong Answer

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

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False
    # 素数
    return True
# 素数判定
def callIsPrime(input_num=10):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

N=int(input())
A=[int(x) for x in input().split()]
a=0
for i in callIsPrime(min(1000,max(A))):
  a=max(a,sum([x%i==0 for x in A]))

if a==N:
  print("not coprime")
elif a>=2:
  print("setwise coprime")
else:
  print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
from math import gcd

primes = set([i for i in range(2,10**6+1)])

for i in range(2,1001):
  for j in range(i*2,10**6+1,i):
    if j in primes:
      primes.remove(j)
      
#primes = list(set(primes))
#print(primes[:10])

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

ok = 1
tmp = a[0]

for i in range(1,n):
  tmp = gcd(tmp,a[i])
  
if tmp>1:
  print('not coprime')
else:
  used = set([])
  ok = 1
  
  for num in a:
    if num in primes:
      if num in used:
        ok = 0
      else:
        used.add(num)
    else:
      for i in range(2,int(num**0.5)+1):
        if num % i == 0:
          if i in used:
            ok = 0
          else:
            used.add(i)
          x = num//i
          if x in used:
            ok = 0
          else:
            used.add(x)
            
    if ok==0:
      break
      
  if ok==1:
    print('pairwise coprime')
  else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    divisors = []
    # 試し割りで、かつ積でnを作るときの相方も同時に追加してる
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
from math import gcd
import sys
n = int(input())
a_ls = list(map(int, input().split()))
now = a_ls[0]
for i in range(1,n):
    now = gcd(now,a_ls[i])
if now != 1:
    print('not coprime')
    sys.exit()
else:
    a_ls.sort()
    is_in_a = [0] * (10**6+1)
    for a in a_ls:
        is_in_a[a] = 1

    res = 'pairwise coprime'
    
    for i in range(n):
        divisors = make_divisors(a_ls[i])
        for d in divisors:
            if d == 1:
                continue
            base = d
            now = 2*base
            while now <= int((10**6)**0.5)+1:
                if is_in_a[now] and not now == a_ls[i]:
                    res = 'setwise coprime'
                    break
                now += base

    print(res)

Submission status: Wrong Answer

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

def fact(n):
    arr = []
    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
            arr.append([i, cnt])
            ret.add(i)
    if temp!=1:
        arr.append([temp, 1])
        ret.add(temp)
    if arr==[]:
        arr.append([n, 1])
        ret.add(n)

    return ret

from collections import defaultdict
cntd=defaultdict(int)
for i in range(len(a)):
    lis = fact(a[i])
    for i in lis:
        cntd[i]+=1

flg=False
for c in cntd.values():
    if c==n:
        print("not coprime")
        exit()
    if c>1:
        flg=True
if flg:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
ans = "pairwise coprime"
k = math.gcd(a[0],a[1])
a.sort()
v = 0
m = math.gcd(a[0],a[1])
if(m!=1):
    v += 1
for i in range(2,n):
    m = math.gcd(a[i],a[i-1])
    if(m!=1):
        v += 1
    k = math.gcd(k,a[i])
if(k==1):
    if(v>0):
        print("setwise coprime")
    else:
        print("pairwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    A = [a for a in read_ints() if a > 1]
    if len(A) == 0:
        return 'pairwise coprime'
    gcd = A[0]
    for a in A[1:]:
        gcd = math.gcd(gcd, a)
    if gcd > 1:
        return 'not coprime'

    is_prime = [True]*(10**6+1)
    B = [False]*(10**6+1)
    for a in A:
        B[a] = True
    if sum(B) != len(A):
        return 'setwise coprime'

    for p in range(2, 1001):
        if is_prime[p]:
            count = B[p]
            for q in range(2*p, 10**6+1, p):
                is_prime[q] = False
                count += B[q]
            if count > 1:
                return 'setwise coprime'
    return 'pairwise coprime'


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
a = [int(item) for item in input().split()]

smallest_factor = [-1] * (10**6 + 10) 
for i in range(2, n+1):
    base = i
    j = 2
    while base * j <= (10**6 + 1):
        smallest_factor[base * j] = i
        j += 1

factor_count = [0] * (10**6 + 10)
is_pairwise = True
for item in a:
    val = item
    pset = set() 
    while smallest_factor[val] != -1:
        pset.add(factor_count[smallest_factor[val]])
        val //= smallest_factor[val]
    pset.add(val)
    for item in pset:
        factor_count[item] += 1
same_p = max(factor_count)
if same_p == 1:
    print("pairwise coprime")
elif same_p == n:
    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()

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
primes = []
while p*p <= MAXN:
    if sieve[p]:
        primes.append(p)
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1
for i in range(p,MAXN+1):
    if sieve[i]:
        primes.append(i)

from collections import Counter
ctr = Counter(A)
if ctr.most_common()[0][1] > 1:
    print('setwise coprime')
    exit()

for p in primes:
    if p > 1000: break
    c = 0
    for a in A:
        if a%p==0:
            c += 1
            if c > 1:
                print('setwise coprime')
                exit()

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
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]]
n=int(input())
A=list(map(int,input().split()))
P=primes(10**6)
B=[0]*(78498)
for i in range(n):
  x=A[i]
  s=A[i]**(1/2)+5
  j=0
  while P[j]<s:
    if x%P[j]==0:
      B[j]+=1
      x=x//P[j]
      while x%P[j]:
        x=x//P[j]
    s=x**(1/2)+5
    j=j+1
f=0
for i in range(78498):
  if B[i]>1:
    f=1
if f==0:
  print("pairwise coprime")
  exit()
for i in range(78498):
  if B[i]>=n:
    f=0
if f==1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

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

f=1
x=arr[0]
for i in range(1,len(arr)):
	x=math.gcd(x,arr[i])
	if x!=1:
		f=0
if f:
	print('pairwise coprime')
else:
	if x==1:
		print('setwise coprime')
	else:
		print('not coprime')

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 1000010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=-1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]
 
def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))
 
def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))
 
def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD
 
    return (num*(pow(den,MOD-2,MOD)))%MOD
 
def flush():
    return sys.stdout.flush()




'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
sieve()

n = int(input())
a = arrIN()
d = defaultdict(list)

for i in range(n):
    d[spf[a[i]]].append(i)

g = a[0]

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


for i in d.keys():
    if i>1 and len(d[i])>1:
        if g!=1:
            print('not coprime')
        else:
            print('setwise coprime')
        break
else:
    print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

n = int(input())
A = list(map(int, input().split()))
left, right = [0] * n, [0] * n

left[0] = A[0]
for i in range(1, n - 1):
    left[i] = gcd(left[i - 1], A[i])

right[-1] = A[-1]
for i in range(1, n - 1)[::-1]:
    right[i] = gcd(right[i + 1], A[i])

flag=0
for i in range(1,n-1):
    if left[i]!=1:
        flag=1
for i in range(1,n-1):
    if right[i]!=1:
        flag=1
if flag==0:print("pairwise coprime");exit()
cnt=1
for i in range(1,n):
    cnt=max(cnt,gcd(left[i-1],right[i]))
if cnt==1:print("setwise coprime");exit()
print("not 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 A:
    g=gcd(g,i)
if g>1:
    print("not coprime")
    exit()
l=[0]*1000001
for i in A:
    l[i]+=1
for i in range(2,100000):
    c=0
    for j in range(i,100001,i):
        c+=l[j]
    if c>1:
        print("setwise coprime")
        break
else:
    print("pairwise coprime")

Submission status: Wrong Answer

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

# 素因数分解、リストで返す
#############################################################


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a.sort()
    return a
#############################################################


primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i])
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

if len(primes) == 0:
    print("pairwise coprime")
    exit()
max_cnt = max(primes.values())
min_cnt = min(primes.values())

if max_cnt==1:
    print("pairwise coprime")
elif min_cnt>=2 and max_cnt!=N:
    print("setwise coprime")
else:
    print("not coprime")


#
#
# if max_cnt == N:
#     print("not coprime")
# elif min_cnt >= 2:
#     print("setwise coprime")
# else:
#     print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd

input = sys.stdin.buffer.readline


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


N = int(input())
A = tuple(map(int, input().split()))
MAX = 10 ** 6


def pairwise(A):
    st = set(A)
    for p in primes(MAX):
        ct = 0
        for i in range(p, MAX + 1, p):
            if i in st:
                ct += 1
        if ct > 1:
            return False
    return True


def setwise(A):
    g = A[0]
    for a in A:
        g = gcd(a, g)
    return g == 1


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

Submission status: Wrong Answer

Solution code:
from functools import reduce
from math import gcd


def func(A):
    is_A = [False] * (10**6+1)
    for a in A:
        is_A[a] = True
    n = 0
    for i in range(2, 10**6+1, 2):
        if is_A[i]:
            n += 1
    if n > 1:
        return False
    for i in range(3, 10**6+1, 2):
        n = 0
        for j in range(i, 10**6+1, 2*i):
            if is_A[j]:
                n += 1
        if n > 1:
            return False
    return True


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    if func(A):
        print('pairwise coprime')
    elif reduce(gcd, A) == 1:
        print('setwise coprime')
    else:
        print('not coprime')
    

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import math
import functools

def gcd(num : list):
    return functools.reduce(math.gcd, num)

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

    if temp!=1:
        arr.append(temp)

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

    return arr

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

    checked_prime = [0] * 1000001

    for a in A:
        fac_a = factorization(a)
        for f in fac_a:
            if checked_prime[f] == 0:
                checked_prime[f] = 1
            else:
                if gcd(A) == 1:
                    print("setwise coprime")
                    exit()
                else:
                    print("not coprime")
                    exit()
    print("pairwise coprime")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def factorize(n):
    tmp = n
    flag = False

    for i in range(2, int(n**0.5)+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if i in prime_cnt:
                prime_cnt[i] += 1
            else:
                prime_cnt[i] = 1
            flag = True
         
    if tmp != 1:
        if tmp in prime_cnt:
            prime_cnt[tmp] += 1
        else:
            prime_cnt[tmp] = 1
        flag = True
    
    if not flag:
        if n in prime_cnt:
            prime_cnt[n] += 1
        else:
            prime_cnt[n] = 1

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

prime_cnt = {}

for i in range(N):
    factorize(A[i])

pw_cp = True
st_cp = True

for val in prime_cnt.values():
    if val != 1:
        pw_cp = False
    if val == N:
        st_cp = False

if pw_cp:
    print('pairwise coprime')
elif st_cp:
    print('setwise coprime')
else:
    print('not coprime')