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
from collections import defaultdict

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

am = max(a)

memo = [1] * (am+1)
memo[0] = 0
memo[1] = 0

d = defaultdict(int)

for ai in range(2, am+1):
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0

cs = []
for i, memoi in enumerate(memo):
    if memoi:
        cs.append(i)

# print(cs)


f1 = 1
f2 = 1

for ai in a:
    lim = int(ai**0.5)+1
    f0 = 0
    for i in cs:
        if i >= lim:
            break
        if ai % i == 0:
            d[i] += 1
            if i != ai // i:
                d[ai//i] += 1
            if d[i] > 1 or d[ai//i] > 1:
                f1 = 0
                f0 = 1
                break
    if f0:
        break


if f1:
    print('pairwise coprime')
else:
    g = a[0]
    for ai in a:
        g = gcd(ai, g)
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


N = I()
A = LI()


def pre_fac(n):
    D = [0] * (n + 1)
    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
            if not D[j]:
                D[j] = i
    return D


def fac(prime, n):
    if n == 1:
        return [[1, 1]]
    arr, temp = [], n

    while prime[temp]:
        mod = prime[temp]
        cnt = 0
        while temp % mod == 0:
            cnt += 1
            temp //= mod
        arr.append([mod, cnt])

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

    return arr


prime = pre_fac(10 ** 6)

d = defaultdict(int)
for i, a in enumerate(A):
    tmp = fac(prime, a)
    for t in tmp:
        d[t[0]] += 1

flag = True
for k, v in d.items():
    if flag and v != 1:
        if k != 1:
            flag = False
    if v == N:
        if k == 1:
            print("pairwise coprime")
        else:
            print("not coprime")
            exit()


if flag:
    print("pairwise coprime")
elif 1 in A:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans==1

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

check=set()
if setwise_coprime(a):
  s=erast(1000)
  s.sort()
  for i in range(n):
    for j in range(168):
      if s[j]>a[i]:
          break
      if a[i]%s[j]==0:
        if s[j] in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(s[j])
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import functools
from math import gcd
N = int(input())
A = list(map(int, input().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)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

B = []
for a in A:
    B += factorization(a)

if len(set(B)) == len(B):
    print("pairwise coprime")
elif functools.reduce(gcd, A) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict

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

am = int(max(a)**0.5)+1

memo = [1] * (am+1)
memo[0] = 0
memo[1] = 0

d = defaultdict(int)

for ai in range(2, am+1):
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0

cs = []
for i, memoi in enumerate(memo):
    if memoi:
        cs.append(i)

# print(cs)


f1 = 1
f2 = 1

for ai in a:
    lim = int(ai**0.5)+1
    f0 = 0
    for i in cs:
        if i >= lim:
            break
        if ai % i == 0:
            d[i] += 1
            if i != ai // i:
                d[ai//i] += 1
            if d[i] > 1 or d[ai//i] > 1:
                f1 = 0
                f0 = 1
                break
    if f0:
        break


if f1:
    print('pairwise coprime')
else:
    g = a[0]
    for ai in a:
        g = gcd(ai, g)
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:

import sys

n=int(input())
a=list(map(int,input().split()))
    
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]

ap=a.copy()
for pp in p:
    lap=len([ai for ai in ap if ai%pp==0])
#    print("pp:",pp,lap)
    if lap==n:
        print("not coprime")
        sys.exit()
    elif lap>=2:
        print("setwise coprime")
        sys.exit()
    
print("pairwise coprime")

Submission status: Wrong Answer

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans==1

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

check=set()
if setwise_coprime(a):
  s=erast(1000)
  s.sort()
  for i in range(n):
    for j in range(168):
      if a[i]%s[j]==0:
        if s[j]>a[i]:
          break
        if s[j] in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(s[j])
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Wrong Answer

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans==1

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

check=set()
if setwise_coprime(a):
  s=erast(1000)
  for i in range(n):
    for j in range(168):
      if s[j]>a[i]:
        break
      if a[i]%s[j]==0:
        if s[j] in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(s[j])
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
sa=set(a)
ans=[]
era=[1]*(10**6+1)
era[0]=0
ca=Counter(a)

k=2
while k<(10**6+1)**0.5+1:
  if era[k]==1:
    
    for i in range(k,10**6+1,k):
      if i!=k:
        era[i]=0
      if i in sa:
        for i in range(ca[k]):
          ans.append(k)
  if k==2:
    k+=1
  else:
    k+=2

pflag=True
if len(ans)!=len(set(ans)):
  pflag=False
  
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans==1

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

check=set()
if setwise_coprime(a):
  s=erast(1000)
  for i in range(n):
    for j in range(168):
      if a[i]%s[j]==0:
        if s[j] in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(s[j])
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
gcd=math.gcd

def is_primes(n):
    primes = [True]*n
    primes[0] =False
    primes[1] =False
    p = 2
    while p*p <=n:
        if primes[p]:
            for q in range(2*p,n,p):
                primes[q] = False
        p+=1
    return primes

def factorize(n,primes):
    fct = [(1,1)]
    for b in primes:#primes ::sorted
        if b**2 > n:
            break
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
    if n > 1:
        fct.append((n,1))
    return fct

n =ni()
A = lma()
tmp=0
for a in A:
    tmp = gcd(a,tmp)
if tmp!= 1:
    print("not coprime")
    exit()
mx= 10**6+10
prms = is_primes(mx)
prms2=[i for i in range(mx) if prms[i]]
#print(prms2)
d=collections.Counter()
for a in A:
    fct = factorize(a,prms2)
    print(fct)
    for fc,cnt in fct:
        if cnt>=1:
            d[fc]+=1

f1=True # pp or sp
f2=True # sp or not p
for num,cnt in d.items():
    if num==1:
        continue
    if cnt==n:
        f2=False #全体で共通の約数になる
        break
    else:
        if cnt==1:
            pass
        else:
            f1=False
            break

if f2==False:
    print("not coprime")
elif f1:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


N = I()
A = LI()


def pre_fac(n):
    D = [0] * (n + 1)
    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
            if not D[j]:
                D[j] = i
    return D


def fac(prime, n):
    if n == 1:
        return [[1, 1]]
    arr, temp = [], n

    while prime[temp]:
        mod = prime[temp]
        cnt = 0
        while temp % mod == 0:
            cnt += 1
            temp //= mod
        arr.append([mod, cnt])

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

    return arr


prime = pre_fac(10 ** 6)

d = defaultdict(int)
for i, a in enumerate(A):
    tmp = fac(prime, a)
    for t in tmp:
        d[t[0]] += 1

flag = True
for v in d.values():
    if flag and v != 1:
        flag = False
    if v == N:
        print("not coprime")
        exit()


if flag:
    print("pairwise coprime")
elif 1 in A:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

def eratosthenes_sieve(n):

    table = [0] * (n+1)
    table[1] = 1
    for i in range(2, n+1):
        if table[i] == 0:
            for j in range(i, n+1, i):
                table[j] = i
    return table

def factorize(table, num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    while num != table[num]:
        num = num // table[num]
        d[table[num]] += 1
    if num != 1:
        d[num] += 1
    return d

N = INT()
A = LIST()

def check(se, fact):
    for k in fact:
        if k not in se:
            se.add(k)
        else:
            return False
    return True

table = eratosthenes_sieve(10**6)

is_pc = 1
se = set()
for a in A:
    fact = factorize(table, a)
    if not check(se, fact):
        is_pc = 0
        break

is_sc = 1
g = 0
for a in A:
    g = gcd(g, a)
if g != 1:
    is_sc = 0

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections
from math import gcd
from functools import reduce

from random import randint

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

def find_gcd(list):
    x = reduce(gcd, list)
    return x

def find_lcm(list):
    x = reduce(lambda a,b: lcm(a,b)% MOD, list)
    return x

D = [None for _ in range(10**6)]
MOD = 10**9 + 7
def solve(N: int, A: "List[int]"):

    q1 = reduce(gcd, A) == 1

    def SieveOfEratosthenes(n): 
        prime = [i for i in range(n + 1)] 
        p = 2
        while (p * p <= n): 
            if (prime[p] == p): 
                for i in range(p * 2, n + 1, p): 
                    prime[i] = p
            p += 1
        prime[0]= 0
        prime[1]= 1
        return prime

    D = SieveOfEratosthenes(10**6)
    s = set([])
    q2 = True
    for a in A:
        facs = []
        while True:            
            facs.append(D[a])
            a = a // D[a]
            if D[a] == a:
                break

        for fac in facs:
            if fac in s:
                if fac != 1 and fac != 0:
                    q2 = False
            s.add(fac)


    if q1 and q2:
        print('pairwise coprime')
    elif q1:
        print('setwise coprime')
    else:
        print('not coprime')
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        x, y = y, x % y
    return y


def gcd3(ll):
    ans = ll[0]
    for i in range(1, len(ll)):
        ans = gcd(ans, ll[i])
    return ans


D = {}
def prime_div(n, A):
    if len(D) == 0:
        for a in range(2, A + 1, 2):
            D[a] = 2
        for a in range(3, A + 1):
            if a in D:
                continue
            now = a
            while now <= A:
                if now not in D:
                    D[now] = a
                now += a * 2
    result = []
    while n > 1:
        result.append(D[n])
        n = n // D[n]
    return result
    

def checkPairwise(ll):
    dic = {}
    for n in ll:
        primes = prime_div(n, 1000000)
        for p in primes:
            if p not in dic:
                dic[p] = 1
            else:
                return False
    return True


def main():
    N = int(input())
    A = [int(n) for n in input().split(" ")]
    a1 = checkPairwise(A)
    if a1:
        print("pairwise coprime")
    else:
        a2 = gcd3(A)
        if a2 == 1:
            print("setwise coprime")
        else:
            print("not coprime")


if __name__ == "__main__":
    main()

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

    if all([ae == 1 for ae in a]):
        print('pairwise coprime')
        sys.exit()
    elif 1 in a:
        print('setwise coprime')
        sys.exit()
    d1 = defaultdict(int)
    for ae in a:
        t1 = factorization(ae)
        for t1e in t1:
            d1[t1e[0]] += 1

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
sa=set(a)
ans=[]
era=[1]*(10**6+1)
era[0]=0

k=2
while k<(10**6+1)**0.5+1:
  if era[k]==1:
    
    for i in range(k,10**6+1,k):
      if i!=k:
        era[i]=0
      if i in sa:
        ans.append(k)
  if k==2:
    k+=1
  else:
    k+=2

pflag=True
if len(ans)!=len(set(ans)):
  pflag=False
  
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections
from math import gcd
from functools import reduce

from random import randint

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

def find_gcd(list):
    x = reduce(gcd, list)
    return x

def find_lcm(list):
    x = reduce(lambda a,b: lcm(a,b)% MOD, list)
    return x

D = [None for _ in range(10**6)]
MOD = 10**9 + 7
def solve(N: int, A: "List[int]"):

    q1 = reduce(gcd, A) == 1

    def SieveOfEratosthenes(n): 
        prime = [i for i in range(n + 1)] 
        p = 2
        while (p * p <= n): 
            if (prime[p] == p): 
                for i in range(p * 2, n + 1, p): 
                    prime[i] = p
            p += 1
        prime[0]= 0
        prime[1]= 1
        return prime

    D = SieveOfEratosthenes(10**6)
    s = set([])
    q2 = True
    for a in A:
        facs = []
        while D[a] != a:            
            facs.append(D[a])
            a = a // D[a]

        for fac in facs:
            if fac in s:
                if fac != 1 and fac != 0:
                    q2 = False
            s.add(fac)


    if q1 and q2:
        print('pairwise coprime')
    elif q1:
        print('setwise coprime')
    else:
        print('not coprime')
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
import sys
input=sys.stdin.readline

def divisors(n):
  ret=[]
  for i in range(2,int(n**0.5)+1):
    if n%i==0:
      ret.append(i)
      while n%i==0:
        n//=i
  return ret

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

n=int(input())
arr=list(map(int,input().split()))
cnt=[False]*(max(arr)+1)
is_pairwise=True
tmp=arr[0]
for val in arr:
  tmp=gcd(tmp,val)
  if is_pairwise==False:
    continue
  divisor=divisors(val)
  for val2 in divisor:
    if cnt[val2]==True:
      is_pairwise=False
      break
    cnt[val2]=True
if tmp==1:
  is_setwise=True
else:
  is_setwise=False
if is_pairwise==True:
  print('pairwise coprime')
elif is_setwise==True:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
import collections
import sys
input=sys.stdin.readline

def divisors(n):
  ret=[]
  for i in range(2,int(n**0.5)+1):
    if n%i==0:
      ret.append(i)
      while n%i==0:
        n//=i
  return ret

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

n=int(input())
arr=list(map(int,input().split()))
cnt=collections.defaultdict(int)
is_pairwise=True
tmp=arr[0]
for val in arr:
  tmp=gcd(tmp,val)
  if is_pairwise==False:
    continue
  divisor=divisors(val)
  for val2 in divisor:
    cnt[val2]+=1
    if cnt[val2]==2:
      is_pairwise=False
      break
if tmp==1:
  is_setwise=True
else:
  is_setwise=False
if is_pairwise==True:
  print('pairwise coprime')
elif is_setwise==True:
  print('setwise coprime')
else:
  print('not 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

    if 1 in a:
        print('not coprime')
        sys.exit()
    d1 = defaultdict(int)
    for ae in a:
        t1 = factorization(ae)
        for t1e in t1:
            d1[t1e[0]] += 1

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
N=int(input())
A=list(map(int,input().split()))
for i in range(N-1):
    for j in range(i+1,N):
        if gcd(A[i],A[j]) != 1:
            print(A[i],A[j])
            break
    else:
        continue
    break
else:
    print("pairwise coprime")
    exit()
s=A.pop(0)
for i in A:
    s = gcd(s,i)
    if s == 1:
        print("setwise coprime")
        break
else:
    print("not coprime")

Submission status: Wrong Answer

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


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def main():
    n = int(input())
    a = list(map(int, input().split()))
    num = [0] * (10**6 + 1)
    for i in range(n):
        d = make_divisors(a[i])
        for j in range(len(d)):
            num[d[j]] += 1

    cnt = collections.Counter(num)
    if cnt[n] > 1:
        ans = 'not coprime'
    elif len(cnt) == 3:
        ans = 'pairwise coprime'
    else:
        ans = 'setwise coprime'

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections
from math import gcd
from functools import reduce

from random import randint

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

def find_gcd(list):
    x = reduce(gcd, list)
    return x

def find_lcm(list):
    x = reduce(lambda a,b: lcm(a,b)% MOD, list)
    return x

D = [None for _ in range(10**6)]
MOD = 10**9 + 7
def solve(N: int, A: "List[int]"):

    q1 = reduce(gcd, A) == 1

    def SieveOfEratosthenes(n): 
        prime = [i for i in range(n + 1)] 
        p = 2
        while (p * p <= n): 
            if (prime[p] == p): 
                for i in range(p * 2, n + 1, p): 
                    prime[i] = p
            p += 1
        prime[0]= 0
        prime[1]= 1
        return prime

    D = SieveOfEratosthenes(10**6)
    s = set([])
    q2 = True
    for a in A:
        facs = []
        while D[a] != a:            
            facs.append(D[a])
            a = a // D[a]

        for fac in facs:
            if fac in s:
                q2 = False
            s.add(fac)


    if q1 and q2:
        print('pairwise coprime')
    elif q1:
        print('setwise coprime')
    else:
        print('not coprime')
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math 
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
ans = ["pairwise coprime", "setwise coprime ", "not coprime"]

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
if gcd_list(A) != 1:
  print(ans[2])
  quit()
  
m = max(A)
fac = [1] * (m + 1)
primeNum = []
for i in range(2, m + 1):
    if fac[i] != 1:
      continue
    primeNum.append(i)
    for j in range(i,m+1,i):
      fac[j] = i  
used = [0] * len(primeNum)     
#print(fac)
#print(primeNum)
for i in range(N):
  now = A[i]
  q = []
  #print(now, D[now - 1])
  while now != fac[now]:
    if fac[now] not in q:
      q.append(fac[now])
    now = int(now / fac[now])
  q.append(now)
  #print(q)    
  for i in q:
    if i in primeNum:
      if used[primeNum.index(i)] == 0:
        used[primeNum.index(i)] = 1
      else:
        print(ans[1])
        quit()  

print(ans[0])

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
sa=set(a)
ans=[]
era=[1]*(10**6+1)
era[0]=0

k=2
while k<(10**6+1)**0.5+1:
  if era[k]==1:
    
    for i in range(k,10**6+1,k):
      if i!=k:
        era[i]=0
      if i in sa:
        ans.append(k)
  if k==2:
    k+=1
  else:
    k+=2

pflag=True
if len(ans)!=len(set(ans)):
  pflag=False
  
if len(sa)!=n:
  pflag=False
  
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
sa=set(a)
ans=[]
era=[1]*(10**6+1)
era[0]=0

k=2
while k<(10**6+1)**0.5+1:
  if era[k]==1:
    
    for i in range(k,10**6+1,k):
      if i!=k:
        era[i]=0
      if i in sa:
        ans.append(k)
  if k==2:
    k+=1
  else:
    k+=2

pflag=True
if len(ans)!=len(set(ans)):
  pflag=False
if sa!=n:
  pflag=False
  
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise 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())
    if 1 in a:
        print('not coprime')
        sys.exit()
    from math import sqrt
    from math import ceil
    maxa = max(a)  # maxa＝「素数判定したい数字のうち最大の数字」
    maxa2 = ceil(sqrt(maxa))
    maxa2 = max(6, maxa2)  # maxa2が6未満だとエラーになる
    p = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(maxa2)]
    p[0] = p[1] = False
    p[2] = p[3] = p[5] = True
    for is1 in range(3, maxa2, 2):
        for is2 in range(is1 ** 2, maxa2, is1):
            p[is2] = False
    prime_list = [i for i, b in enumerate(p) if b]

    d1 = defaultdict(int)
    for pn in prime_list:
        d1[pn] = sum([ae % pn == 0 for ae in a])
    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 collections
import sys
input=sys.stdin.readline

def divisors(n):
  ret=[]
  for i in range(2,int(n**0.5)+1):
    if n%i==0:
      ret.append(i)
      while n%i==0:
        n//=i
  return ret

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

n=int(input())
arr=list(map(int,input().split()))
cnt=collections.defaultdict(int)
tmp=arr[0]
for val in arr:
  tmp=gcd(tmp,val)
if tmp==1:
  is_setwise=True
else:
  is_setwise=False
is_pairwise=True
for val in arr:
  divisor=divisors(val)
  for val2 in divisor:
    cnt[val2]+=1
    if cnt[val2]==2:
      is_pairwise=False
      break
if is_pairwise==True:
  print('pairwise coprime')
elif is_setwise==True:
  print('setwise coprime')
else:
  print('not coprime')