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 # Python3.6以降
# --------------------------------------------------------------

# n以下の素数列挙: O-nlogn
def primes(n):
    prs = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            prs.append(i)
    return prs

n    = int(input())
lis  = list(map(int,input().split()))
A    = 10**6
soin = [0]*A
flg_pairwise = True

for i in range(n):
    soin[lis[i]-1] += 1

for i in primes(A):
    cnt = 0
    for j in range(i,A-1,i):
        cnt += soin[j-1]
    if cnt > 1:
        flg_pairwise = False
        break

if flg_pairwise:
    print('pairwise coprime')
else:
    for i in range(n-1):
        if i==0:
            tmp = gcd(lis[i],lis[i+1])
        else:
            tmp = gcd(tmp,lis[i+1])

    if tmp==1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
p = 1000003

def gcd(a, b):
    a, b = sorted([a, b], reverse=True)
    if b == 0:
        return a
    else:
        r = a % b
        ans = gcd(b, r)
        return ans

def modpow(a, n, p):
    if n == 1:
        ans = a % p
    else:
        if n % 2 == 0:
            ans = (modpow(a, n // 2, p) ** 2) % p
        else: # n % 2 == 1
            ans = (a * (modpow(a, n // 2, p) ** 2)) % p

    return ans

N = int(input())
A = sorted([int(x) for x in input().split()])

d, l, P = 0, 1, 1
for i in range(N):
    d = gcd(A[i], d) % p
    P = (P * A[i]) % p
    l = (((A[i] * l) % p) * modpow(gcd(A[i], l), p - 2, p)) % p
            
if d == 1:
    if P == l:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
large = 10**6+1
furui = [True]*(large)
prime_num = []
for num in range(large):
    if num in (0,1):
        furui[num] = False
    else:
        if furui[num]:
            times = 1
            while num * times < large:
                
                if times == 1:
                    prime_num.append(num)
                else:
                    furui[num*times] = False
                times += 1
N = int(input())
ls = list(map(int, input().split()))
num_divided = [0]*len(prime_num)
for element in ls:
    for num in range(len(prime_num)):
        diviser = prime_num[num]
        if diviser ** 2 > element:
            break
        else:
            if element % diviser == 0:
                num_divided[num] += 1

if max(num_divided) <= 1:
    print("pairwise coprime")
elif max(num_divided) < N:
    print("setwise coprime")
else:
    print("neither")

Submission status: Wrong Answer

Solution code:
import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

p=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
   31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
   73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
   127, 131, 137, 139, 149, 151, 157, 163, 167,
   173, 179, 181, 191, 193, 197, 199, 211, 223,
   227, 229, 233, 239, 241, 251, 257, 263, 269,
   271, 277, 281, 283, 293, 307, 311, 313, 317,
   331, 337, 347, 349, 353, 359, 367, 373, 379,
   383, 389, 397, 401, 409, 419, 421, 431, 433, 
   439, 443, 449, 457, 461, 463, 467, 479, 487,
   491, 499, 503, 509, 521, 523, 541, 547, 557,
   563, 569, 571, 577, 587, 593, 599, 601, 607,
   613, 617, 619, 631, 641, 643, 647, 653, 659,
   661, 673, 677, 683, 691, 701, 709, 719, 727,
   733, 739, 743, 751, 757, 761, 769, 773, 787,
   797, 809, 811, 821, 823, 827, 829, 839, 853,
   857, 859, 863, 877, 881, 883, 887, 907, 911,
   919, 929, 937, 941, 947, 953, 967, 971, 977,
   983, 991, 997,1009]

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

if amax==1:
    print("pairwise coprime")
    sys.exit()

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

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


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

Submission status: Wrong Answer

Solution code:
import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

p=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
   31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
   73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
   127, 131, 137, 139, 149, 151, 157, 163, 167,
   173, 179, 181, 191, 193, 197, 199, 211, 223,
   227, 229, 233, 239, 241, 251, 257, 263, 269,
   271, 277, 281, 283, 293, 307, 311, 313, 317,
   331, 337, 347, 349, 353, 359, 367, 373, 379,
   383, 389, 397, 401, 409, 419, 421, 431, 433, 
   439, 443, 449, 457, 461, 463, 467, 479, 487,
   491, 499, 503, 509, 521, 523, 541, 547, 557,
   563, 569, 571, 577, 587, 593, 599, 601, 607,
   613, 617, 619, 631, 641, 643, 647, 653, 659,
   661, 673, 677, 683, 691, 701, 709, 719, 727,
   733, 739, 743, 751, 757, 761, 769, 773, 787,
   797, 809, 811, 821, 823, 827, 829, 839, 853,
   857, 859, 863, 877, 881, 883, 887, 907, 911,
   919, 929, 937, 941, 947, 953, 967, 971, 977,
   983, 991, 997,1009]

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

if amax==1:
    print("pairwise coprime")
    sys.exit()

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

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


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

Submission status: Wrong Answer

Solution code:
p = 1000003

def gcd(a, b):
    a, b = sorted([a, b], reverse=True)
    if b == 0:
        return a
    else:
        r = a % b
        ans = gcd(b, r)
        return ans

def modpow(a, n, p):
    if n == 1:
        ans = a % p
    else:
        if n % 2 == 0:
            ans = (modpow(a, n // 2, p) ** 2) % p
        else: # n % 2 == 1
            ans = (a * (modpow(a, n // 2, p) ** 2)) % p

    return ans

N = int(input())
A = sorted([int(x) for x in input().split()])

pw, sw = False, False
d, l, P = 0, 1, 1
for i in range(N):
    d = gcd(A[i], d)
    P = P * A[i] % p
    l = ((A[i] * l) % p) * modpow(gcd(A[i], l), p - 2, p) % p

if d == 1:
    sw = True
    if P == l:
        pw = True
            
if sw:
    if pw:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
p = 1000003

def gcd(a, b):
    a, b = sorted([a, b], reverse=True)
    if b == 0:
        return a
    else:
        r = a % b
        ans = gcd(b, r)
        return ans

def modpow(a, n, p):
    if n == 1:
        ans = a % p
    else:
        if n % 2 == 0:
            ans = (modpow(a, n // 2, p) ** 2) % p
        else: # n % 2 == 1
            ans = (a * (modpow(a, n // 2, p) ** 2)) % p

    return ans

N = int(input())
A = sorted([int(x) for x in input().split()])

pw, sw = False, False
d, l, P = 0, 1, 1
for i in range(N):
    d = gcd(A[i], d)
    P = P * A[i] % p
    l = A[i] * l * modpow(gcd(A[i], l), p - 2, p) % p

if d == 1:
    sw = True
    if P == l:
        pw = True
            
if sw:
    if pw:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
p = 1000003

def gcd(a, b):
    a, b = sorted([a, b], reverse=True)
    if b == 0:
        return a
    else:
        r = a % b
        ans = gcd(b, r)
        return ans

def modpow(a, n, p):
    if n == 1:
        ans = a % p
    else:
        if n % 2 == 0:
            ans = (modpow(a, n // 2, p) ** 2) % p
        else: # n % 2 == 1
            ans = (a * (modpow(a, n // 2, p) ** 2)) % p

    return ans

N = int(input())
A = sorted([int(x) for x in input().split()])

pw, sw = False, False
d, l, P = 0, 1, 1
for i in range(N):
    d = gcd(A[i], d)
    P = P * A[i] % p
    l = P * modpow(gcd(A[i], l), p - 2, p) % p

if d == 1:
    sw = True
    if P == l:
        pw = True
            
if sw:
    if pw:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
MAX_A = 10**6 + 1
is_prim = [True] * MAX_A
is_prim[0] = is_prim[1] = False
for i in range(2, MAX_A):
    if not is_prim[i]: continue
    for j in range(i+i, MAX_A, i):
        is_prim[j] = False
prim = [i for i in range(MAX_A) if is_prim[i]]

def solve():
    max_c = 0
    C = [0] * MAX_A
    for a in A:
        for p in prim:
            if p*p > a: break
            if a%p == 0:
                while a%p: a //= p
                C[p] += 1
                max_c = max(max_c, C[p])
    if max_c <= 1: return 'pairwise'
    elif max_c <= n-1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Wrong Answer

Solution code:
MAX_A = 10**6 + 1
is_prim = [True] * 1010
is_prim[0] = is_prim[1] = False
for i in range(2, 1010):
    if not is_prim[i]: continue
    for j in range(i+i, 1010, i): is_prim[j] = False

prim = [i for i in range(1010) if is_prim[i]]

def solve():
    max_c = 0
    C = [0] * MAX_A
    for a in A:
        for p in prim:
            if p*p > a: break
            if a%p == 0:
                while a%p: a //= p
                C[p] += 1
                max_c = max(max_c, C[p])
    if max_c <= 1: return 'pairwise'
    elif max_c <= n-1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Wrong Answer

Solution code:
MAX_A = 10**6 + 1
is_prim = [True] * 1010
is_prim[0] = is_prim[1] = False
for i in range(2, 1010):
    # if not is_prim[i]: continue
    for j in range(i+i, 1010, i): is_prim[j] = False

prim = [i for i in range(1010) if is_prim[i]]

def solve():
    max_c = 0
    C = [0] * MAX_A
    for a in A:
        for p in prim:
            if p*p > a: break
            if a%p == 0:
                C[p] += 1
                max_c = max(max_c, C[p])
    if max_c <= 1: return 'pairwise'
    elif max_c <= n-1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Wrong Answer

Solution code:
MAX_A = 10**6 + 1
is_prim = [True] * 1010
is_prim[0] = is_prim[1] = False
for i in range(2, 1010):
    if not is_prim[i]: continue
    for j in range(i+i, 1010, i): is_prim[j] = False

prim = [i for i in range(1010) if is_prim[i]]

def solve():
    max_c = 0
    C = [0] * MAX_A
    for a in A:
        for p in prim:
            if p*p > a: break
            if a%p == 0:
                C[p] += 1
                max_c = max(max_c, C[p])
    if max_c <= 1: return 'pairwise'
    elif max_c <= n-1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Wrong Answer

Solution code:
MAX_A = 10**6 + 1
is_prim = [True] * MAX_A
is_prim[0] = is_prim[1] = False
for i in range(2, 1010):
    if not is_prim[i]: continue
    for j in range(i+i, 1010, i): is_prim[j] = False

prim = [i for i in range(1010) if is_prim[i]]

def solve():
    max_c = 0
    C = [0] * MAX_A
    for a in A:
        for p in prim:
            if p*p > a: break
            if a%p == 0:
                C[p] += 1
                max_c = max(max_c, C[p])
    if max_c <= 1: return 'pairwise'
    elif max_c <= n-1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Wrong Answer

Solution code:
import math

MAX=10**6+3
table = list(range(MAX))
i=2
n=MAX
while i<=n:
    table[i] = 2
    i+=2

p=3
while p*i<=n:
    if table[p]<p:
        continue
    x=p
    while x<=n:
        table[x]=p
        x+=p

def primeFactorSet(n):
    result = set()
    while table[n]!=1:
        result.add(table[n])
        n //= table[n]
    return result
    

n = int(input())
A = list(map(int,input().split()))
pairwise = True
flags = [False for _ in range(MAX)]

for i in range(n):
    a=A[i]
    if pairwise:
        t = primeFactorSet(a)
        for p in t:
            if flags[p]:
                pairwise = False
                break
            flags[p]=True
    if i==0:
        g=a
    else:
        g=math.gcd(g,a)
    
if g>1:
    print("not coprime")
elif pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
MAX_A = 10**6 + 1
is_prim = [True] * MAX_A
is_prim[0] = is_prim[1] = False
for i in range(2, 1010):
    if not is_prim[i]: continue
    for j in range(i+i, 1010, i): is_prim[j] = False

prim = [i for i in range(1010) if is_prim[i]]

def solve():
    max_c = 0
    C = [0] * MAX_A
    for a in A:
        for p in prim:
            if a < p: break
            if a%p == 0:
                C[p] += 1
                max_c = max(max_c, C[p])
    if max_c <= 1: return 'pairwise'
    elif max_c <= n-1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Wrong Answer

Solution code:
# Date [ 2020-08-29 21:59:01 ]
# Problem [ e.py ]
# Author Koki_tkg
# After Contest

import sys
import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

# osa_k 法 O(NloglogN + logA)
class PrimeFactorization():
    def __init__(self, num):
        self.num = num
        self.factor_table = [0] * (num + 1)
        self.eratosthenes()

    def eratosthenes(self):
        for i in range(2, self.num + 1):
            if self.factor_table[i] == 0:
                self.factor_table[i] = i
                for j in range(i * i, self.num + 1, i):
                    if self.factor_table[j] == 0:
                        self.factor_table[j] = i
    
    def factorization(self, a):
        now = a
        ret = []
        while now > 1:
            cnt = 0
            prime = self.factor_table[now]
            while now % prime == 0:
                cnt += 1
                now //= prime
            ret.append((prime, cnt))
        return ret

def Main():
    n = read_int()
    a = read_int_list()
    max_num = max(a)

    pf = PrimeFactorization(max_num + 1)
    used_prime = [False] * (max_num + 1)
    for x in a:
        factor = pf.factorization(x)
        for prime, cnt in factor:
            if used_prime[x]:
                break
            used_prime[x] = True
        else:
            continue
        break
    else:
        print('pairwise coprime')
        exit()

    gcd_num = a[0]
    for x in a[1:]:
        gcd_num = math.gcd(gcd_num, x)
    print('setwise coprime' if gcd_num == 1 else 'not coprime')

if __name__ == '__main__':
    Main()

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
  if a % b == 0:
    return b
  else:
    return gcd(b, a%b)
  
  
N = int(input())
As = list(map(int, input().split()))

t = As[0]
 
for a in As:
  t = gcd(t,a)
  
if t == 1:
  print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

p=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
   31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
   73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
   127, 131, 137, 139, 149, 151, 157, 163, 167,
   173, 179, 181, 191, 193, 197, 199, 211, 223,
   227, 229, 233, 239, 241, 251, 257, 263, 269,
   271, 277, 281, 283, 293, 307, 311, 313, 317,
   331, 337, 347, 349, 353, 359, 367, 373, 379,
   383, 389, 397, 401, 409, 419, 421, 431, 433, 
   439, 443, 449, 457, 461, 463, 467, 479, 487,
   491, 499, 503, 509, 521, 523, 541, 547, 557,
   563, 569, 571, 577, 587, 593, 599, 601, 607,
   613, 617, 619, 631, 641, 643, 647, 653, 659,
   661, 673, 677, 683, 691, 701, 709, 719, 727,
   733, 739, 743, 751, 757, 761, 769, 773, 787,
   797, 809, 811, 821, 823, 827, 829, 839, 853,
   857, 859, 863, 877, 881, 883, 887, 907, 911,
   919, 929, 937, 941, 947, 953, 967, 971, 977,
   983, 991, 997,1009]

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

if amax==1:
    print("pairwise coprime")
    sys.exit()

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

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


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

Submission status: Wrong Answer

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

t = As[0]
 
for a in As:
  t = gcd(t,a)
  
if t == 1:
  print('setwise coprime')

Submission status: Wrong Answer

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

t = As[0]
 
for a in As:
  t = gcd(t,a)
  
if t == 1:
  print('setwise coprime')

Submission status: Wrong Answer

Solution code:
N = int(input())
As = list(map(int, input().split()))
 
lst = [0]*(max(As)+1)
 
for a in As:
  i = 2
  if a % i == 0:
    lst[i] += 1
  while a % i == 0:
    a //= i
  i = 3
  while i**2 <= N:
    if a % i == 0:
      lst[i] += 1  
    while a % i == 0:
      a //= i
    i += 2
  if a > 1:
    lst[a] += 1
    
r = max(lst)
if r < 2:
  print('pairwise coprime')
elif r < N:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()

def fast_prime_factorization(A, max_num):
    """
    リストAに現れる自然数全てをO(NlogN)で素因数分解する（NはリストAの長さ）
    max_numはAに現れる自然数の上界。
    """
    # エラトステネスの篩でprimes[i] = (iを割り切る最小の素数)を記録する
    primes = [1] * (max_num + 1)
    primes[0] = primes[1] = 0
    for i in range(2, int(max_num**0.5) + 1):
        if primes[i] != 1: continue
        for j in range(i, max_num + 1, i):
            primes[j] = i

    # factorization[i] = {p1:n1, p2:n2, ...} (A[i] = p1^{n1} * p2^{n2} * ...)
    factorization_list = [{} for _ in range(len(A))]
    for i, a in enumerate(A):
        while a > 1:
            if primes[a] not in factorization_list[i]:
                factorization_list[i][primes[a]] = 1
            else:
                factorization_list[i][primes[a]] += 1
            a //= primes[a]

    return factorization_list


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

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

    prime_factor_list = fast_prime_factorization(A, 10**6)
    d = set()
    for factor_dict in prime_factor_list:
        for prime in factor_dict:
            if prime in d:
                print("setwize coprime")
                return
            d.add(prime)
    print("pairwise coprime")




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# pythonの場合、ライブラリ関数でgcdがある？ただし、配列まとめてというわけではない模様
from math import gcd

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

	pc = True
	maxA = max(A)

	cnts = [ 0 for _ in range(maxA+1) ]
	for a in A:
		cnts[a] += 1
	for i in range(2,max(A)):
		if pc:
			# 素因数ごとに、A内での登場回数を数える
			# 2つあったらその2つのcommon dividerとして、1以外にそれがあることが確定する
			cnt = 0
			for j in range(i,maxA,i):
				cnt += cnts[j]
				if 1 < cnt:
					# Aの素因数で重複があれば、pcでない
					pc = False
					break

	sc = False

	if pc == False:
		gcdResult = 0
		for a in A:
			# 配列全要素に対してgcdを呼んでるが、結果的に、それが1になればsc、ならなければnot sc
			gcdResult=gcd(gcdResult,a)
		if gcdResult == 1:
			sc = True

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






if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

A = max(As)
lst = [0]*(A+1)
rlt = [0]*(A+1)

for i in range(2, len(lst)//2):
  if lst[i] > 0:
    continue
  j = 2
  while i*j <= A:
    if lst[i*j] == 0:
      lst[i*j] = i
    j += 1
    
for a in As:
  tmp = -1
  while lst[a] > 0:
    if tmp != lst[a]:
      rlt[lst[a]] += 1
    a //= lst[a]
    tmp = lst[a]
  if a != tmp:
    rlt[a] += 1
    
print(rlt)

if max(rlt) < 2:
  print('pairwise coprime')
  exit()
  
t = As[0]

for a in As:
  t = gcd(t,a)
  
if t == 1:
  print('setwise 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

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)==1:
  s=erast(1000)
  s.sort()
  for i in range(n):
    flg=0
    if a[i]!=1:
      for j in range(168):
        if a[i]%s[j]==0:
          flg=1
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
      if flg==0:
        if a[i] in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(a[i])
          
          
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

n = int(input())
a_list = list(map(int, input().split()))
prime_list = list(range(math.ceil(a_list[n - 1] ** 0.5) + 1))

for i in range(2, prime_list[-1] + 1):
    if prime_list[i] != -1:
        for j in range(i * 2, prime_list[-1] + 1, i):
            prime_list[j] = -1
prime_list.sort()
del prime_list[0: prime_list.index(1) + 1]
check_list = [0] * len(prime_list)

def is_pairwise(num):
    for i, prime in enumerate(prime_list):
        if num % prime == 0:
            if check_list[i] == 1:
                return False
            else:
                check_list[i] += 1
    return True

for a in a_list:
    if not is_pairwise(a):
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            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

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)==1:
  s=erast(1000)
  s.sort()
  for i in range(n):
    flg=0
    if a[i]!=1:
      for j in range(168):
        if a[i]%s[j]==0:
          flg=1
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
      if flg==0:
        if a[i] in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(a[i])
  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

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)==1:
  s=erast(1000)
  s.sort()
  for i in range(n):
    flg=0
    if a[i]!=1:
      for j in range(len(s)):
        if s[j]>a[i]:
          break
        if a[i]%s[j]==0:
          flg=1
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
      if flg==0:
        check.add(a[i])
  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

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)==1:
  s=erast(1000)
  for i in range(n):
    flg=0
    if a[i]!=1:
      for j in range(len(s)):
        if s[j]>a[i]:
          break
        if a[i]%s[j]==0:
          flg=1
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
      if flg==0:
        check.add(a[i])
  print("pairwise coprime")    
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

n = int(input())
a_list = list(map(int, input().split()))
prime_list = list(range(math.ceil(a_list[n - 1] ** 0.5) + 1))

for i in range(2, prime_list[-1] + 1):
    if prime_list[i] != -1:
        index = i + i
        while index <= prime_list[-1]:
            prime_list[index] = -1
            index += i
prime_list.sort()
del prime_list[0: prime_list.index(1) + 1]
check_list = [0] * len(prime_list)

def is_pairwise(num):
    for i, prime in enumerate(prime_list):
        if prime > num:
            break
        if num % prime == 0:
            if check_list[i] == 1:
                return False
            else:
                check_list[i] += 1
    return True

for a in a_list:
    if not is_pairwise(a):
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

N = int(input())
A = [int(x) for x in input().split()]

if 1 in A:
    print("not coprime")
elif reduce(math.gcd, A) != 1:
    print("not coprime")
else:
    flg = 0
    arr = []
    for l in range(N):
        temp = A[l]
        for i in range(2, int(-(-A[l]**0.5//1))+1):
            if temp%i==0:
                if i in arr:
                    flg = 1
                else:
                    while temp%i==0:
                        temp //= i
                    arr.append(i)

            if temp!=1:
                if temp in arr:
                    flg = 1
                else:
                    arr.append(temp)
                    break

            if flg == 1:
                break
        if flg == 1:
            break
    if flg == 1:
        print("setwise coprime")
    else:
        print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

n = int(input())
a_list = list(map(int, input().split()))
prime_list = list(range(math.ceil(a_list[n - 1] ** 0.5) + 1))

for i in range(2, prime_list[-1] + 1):
    if prime_list[i] != -1:
        index = i + i
        while index <= prime_list[-1]:
            prime_list[index] = -1
            index += i
prime_list.sort()
del prime_list[0: prime_list.index(1) + 1]
check_list = [0] * len(prime_list)

def is_pairwise(num):
    for i, prime in enumerate(prime_list):
        if num % prime == 0:
            if check_list[i] == 1:
                return False
            else:
                check_list[i] += 1
    return True

for a in a_list:
    if not is_pairwise(a):
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()
print("pairwise coprime")