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 math
from functools import reduce

n = int(input())
a_list = list(map(int, input().split()))
prime_list = list(range(a_list[n - 1] + 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")

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

# 素数と個数を求める
def factorize(n):
    res = []
    for i in range(2,n):
        if i*i > n: break
        if n%i: continue
        res += [[i,0]]
        while n%i == 0:
            n //= i
            res[-1][1] += 1
    if n != 1: res += [[n,1]]
    return res

def solve():
    prim = [i for i in range(1100) if is_prim[i]]
    C = [0] * MAX_A
    for a in A:
        PC = factorize(a)
        for p,c in PC:
            C[p] += 1
    pairwise = True
    for p in prim:
        if sum(C[p: MAX_A: p]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), '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 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, A[l]+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 = [int(x) for x in input().split()]

if 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:
from math import gcd
n = int(input())
A = list(map(int, input().split()))
min_A = min(A)
max_A = max(A)

def is_pairwise():
    arr = [0] * (max_A + 1)
    for a in A:
        arr[a] = 1
    max_counter = 0
    for num in range(2, max_A + 1):
        counter = 0
        for i in range(1, 10**6 + 1):
            try:
                counter += arr[num * i]
            except:
                break
        max_counter = max(max_counter, counter)
    if max_counter == 1:
        return True
    else:
        return False

if min_A == 1 and max_A == 1:
    print("pairwise coprime")
elif min_A == 1 and max_A != 1:
    A = [num for num in A if num != 1]
    if is_pairwise():
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    if is_pairwise():
        print("pairwise coprime")
    else:
        g = A[0]
        for a in A:
            g = gcd(a, g)
        if g == 1:
            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, 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():
    C = [0] * 1010
    for a in A:
        for p in prim:
            if a%p == 0:
                C[p] += 1
    pairwise = True
    for p in prim:
        if sum(C[p: MAX_A: p]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'

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

Submission status: Wrong Answer

Solution code:
from math import gcd
n = int(input())
A = list(map(int, input().split()))
min_A = min(A)
max_A = max(A)

def is_pairwise():
    arr = [0] * (max_A + 1)
    for a in A:
        arr[a] = 1
    max_counter = 0
    for num in range(2, max_A + 1):
        counter = 0
        for i in range(1, 10**6 + 1):
            try:
                counter += arr[num * i]
            except:
                break
        max_counter = max(max_counter, counter)
    if max_counter == 1:
        return True
    else:
        return False

if min_A == 1:
    A = [num for num in A if num != 1]
    if is_pairwise():
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    if is_pairwise():
        print("pairwise coprime")
    else:
        g = A[0]
        for a in A:
            g = gcd(a, g)
        if g == 1:
            print("setwise coprime")
        else:
            print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

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 list(set(a))

n = int(input())
a = list(map(int, input().split()))
c0, c1 = False, False
vals = []

for i, j in enumerate(a):
    vals += prime_factorize(j)
    if len(vals) != len(set(vals)) and c0 is False:
        c0 = True
    if i < n-1 and c1 is False:
        if gcd(a[i], a[i+1]) > 1:
            c1 = True
            
if c0 is True and c1 is True:
    print('not coprime')
elif c0 is False:
    print('pairwise coprime')
elif c1 is False:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
dp = [0 for i in range(a[-1])]
p = [0 for i in range(a[-1])]
for i in range(n):
    p[a[i]-1] += 1
ans = 1
for i in range(2,a[-1]+1):
    if dp[i-1] == 1:
        continue
    u = 0
    k = 1
    while i*k <= a[-1]:
        dp[i*k-1] = 1
        if p[i*k-1] == 1:
            u += p[i*k-1]
        k += 1
    if u == n:
        ans = -1
    elif u > 1:
        ans = min(ans,0)
if ans == 1:
    print('pairwise coprime')
elif ans == 0:
    print('setwise coprime')
elif a[0] == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

def calc_spf(n):
    num = list(range(2,n+1))
    #1の扱いは気にしない
    spf = [0]*n
    
    while len(num)>0:
        p = num.pop(0)
        delta = p
        spf[p-1]=p
        p *= delta
        while p<=n:
            if p in num and spf[p-1]==0:
                spf[p-1]=delta
                num.remove(p)
            p += delta
    return spf

def get_prime(n,spf):
    if n==1:
        return {1}
    ans = []
    while n > 1:
        tmp = spf[n-1]
        ans.append(tmp)
        n //= tmp
    return set(ans)

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
b = a[:]
pgcd = True
sgcd = a[n-1]
spf = calc_spf(max(a))
b[n-1] = get_prime(a[n-1],spf)
tmp = b[n-1]
for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
    b[i] = get_prime(a[i],spf)
    if pgcd and len(tmp&b[i]) >0:
        pgcd = False
    tmp = tmp | b[i]
if sgcd!=1:
    print('not coprime')
elif pgcd:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
chohuku=set()
arr = [0]*(10**6+1)
def factorization(n):
    temp = n
    flag=0
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            flag=1
            while temp%i==0:
                temp //= i
            arr[i]+=1
    if flag==0:
        arr[n]+=1
    return arr


f=False
for num in a:
    factorization(num)
ans=max(arr)
if ans==n:
    print("not coprime")
elif ans>=2:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Wrong Answer

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

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

    prod = A[0]
    for i, a in enumerate(A):
        if i == 0: continue
        if gcd(prod, a) != 1:
            print("setwise coprime")
            return
        prod *= a
        prod %= mod
    print("pairwise coprime")




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

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

    prod = A[0]
    for i, a in enumerate(A):
        if i == 0: continue
        if gcd(prod, a) != 1:
            print("setwise coprime")
            return
        prod *= a
        prod %= mod
    print("pairwise coprime")




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

def calc_spf(n):
    num = list(range(2,n+1))
    #1の扱いは気にしない
    spf = [0]*n
    
    while len(num)>0:
        p = num.pop(0)
        delta = p
        spf[p-1]=p
        p *= delta
        while p<=n:
            if p in num and spf[p-1]==0:
                spf[p-1]=delta
                num.remove(p)
            p += delta
    return spf

def get_prime(n,spf):
    if n==1:
        return {1}
    ans = []
    while n > 1:
        tmp = spf[n-1]
        ans.append(tmp)
        n //= tmp
    return set(ans)

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
b = a[:]
pgcd = True
sgcd = a[n-1]
spf = calc_spf(max(a))
b[n-1] = get_prime(a[n-1],spf)

for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
    b[i] = get_prime(a[i],spf)

if sgcd!=1:
    print('not coprime')
else:
    for i in range(0,n-1):
        for j in range(i+1,n):
            if len(b[i]&b[j]) >0:
                print('setwise coprime')
                break
        else:
            continue
        break
    else:
        print('pairwise 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

def solve():
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for p in [i for i in range(1100) if is_prim[i]]:
        if sum(C[p: MAX_A: p]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'

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, MAX_A):
    if not is_prim[i]: continue
    for j in range(i+i, MAX_A, i): is_prim[j] = False

def solve():
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for p in [i for i in range(1010) if is_prim[i]]:
        if sum(C[p: MAX_A: p]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'

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

Submission status: Wrong Answer

Solution code:
import math

def calc_spf(n):
    num = list(range(2,n+1))
    #1の扱いは気にしない
    spf = [0]*n
    
    while len(num)>0:
        p = num.pop(0)
        delta = p
        spf[p-1]=p
        p *= delta
        while p<=n:
            if p in num and spf[p-1]==0:
                spf[p-1]=delta
                num.remove(p)
            p += delta
    return spf

def get_prime(n,spf):
    if n==1:
        return {1}
    ans = []
    while n > 1:
        tmp = spf[n-1]
        ans.append(tmp)
        n //= tmp
    return set(ans)

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
b = a[:]
pgcd = True
sgcd = a[n-1]
spf = calc_spf(max(a))
b[n-1] = get_prime(a[n-1],spf)

for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
    b[i] = get_prime(a[n-1],spf)

if sgcd!=1:
    print('not coprime')
else:
    for i in range(0,n-1):
        for j in range(i+1,n):
            if len(b[i]&b[j]) >0:
                print('setwise coprime')
                break
        else:
            continue
        break
    else:
        print('pairwise coprime')

Submission status: Wrong Answer

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


def get_sieve_of_eratosthenes(n):
    """
    エラトステネスの篩。√N以下の数に対して2から順にその数の倍数を消していく。
    計算量は「調和級数」になるのがミソ。具体的には
        N/2 + N/3 + N/5 + ... + N/(√N) = N * (1/2 + 1/3 + 1/5 + ... + 1/√N)
                                       = N * loglog(√N) (素数の逆数和の発散スピードがこれ)
                                       = N(loglogN - log2)
    """
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        return [0] * (n + 1)
    prime = [1] * (n + 1)
    prime[0] = prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not prime[i]: continue
        for j in range(i * 2, n + 1, i):
            prime[j] = 0
    return prime


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

    primes = get_sieve_of_eratosthenes(1000)
    for p, is_prime in enumerate(primes):
        if is_prime == 0: continue
        appeared = False
        for a in A:
            if a % p != 0: continue
            if not appeared:
                appeared = True
                continue
            if appeared:
                print("setwise coprime")
                return
    print("pairwise coprime")




if __name__ == "__main__":
    main()

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:0 for i in range(n + 1) if is_prime[i]}

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

for i in a:
    for k , v in d.items():
        if v == 0:
            if i % k == 0:
                d[k] += 1
        elif v > 0:
            if i % k == 0:
                d[k] += 1
            elif i % k != 0:
                d[k] = -1
flag = True  
for v in d.values():
    if v == n:
        print("not coprime")
        exit()
    elif v == -1:
        flag = False
if flag:
    print("pairwise coprime")
else:
    print("setwise 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:0 for i in range(n + 1) if is_prime[i]}

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

for i in a:
    for k , v in d.items():
        if v >= 0:
            if i % k == 0:
                d[k] += 1
            elif i % k != 0:
                d[k] = -1
flag = True  
for v in d.values():
    if v == n:
        print("not coprime")
        exit()
    elif v == -1:
        flag = False
if flag:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
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 arr == []:
        arr.append(n)
    return arr

# sosuu=set(seachPrimeNum(10**6))
n=int(input())
a=list(map(int,input().split()))
chohuku=set()
wa=set()
f=False
for idx,num in enumerate(a):
    s=factorization(num)
    if idx==0:
        chohuku=set(s)
        wa=set(s)
    else:
        chohuku=chohuku&set(s)
        if f==False:
            for ss in s:
                if ss in wa:
                    f=True
                    break
                else:wa.add(ss)
if len(chohuku)==0 :
    if f==False:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
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 arr == []:
        arr.append(n)
    return arr

# sosuu=set(seachPrimeNum(10**6))
n=int(input())
a=list(map(int,input().split()))
num_list=set()
all=set()
flag=0#0 最大公約数　1　一部
f=True# True not coprime
for idx,num in enumerate(a):
    s=factorization(num)
    common=set()
    if idx>=1:
        num_list=num_list&set(s)
    for soin in s:
        if idx==0:
            num_list.add(soin)
        elif soin in all :
            if soin not in num_list:
                flag=1
                f=False
        else:
            f=False
        all.add(soin)

if f:
    print("not coprime")
elif flag==0:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import defaultdict

INF = 10 ** 6 + 1
is_prime = [1] * INF

def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return

def f(n):
    yakusu = []
    if is_prime[n]:
        yakusu.append(n)
    else:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                yakusu.append(i)
                if i != n //i:
                    yakusu.append(n // i)
                break

    for i in yakusu:
        if i != 1:
            d[i] += 1


eratorasu()
d = defaultdict(int)
N = int(input())
A = np.array(list(map(int, input().split())))
for i in A:
    f(i)

cnt = 1
for i, v in d.items():
    if v != 1:
        cnt = max(cnt, v)

if cnt == N:
    print('not coprime')
elif cnt == 1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

INF = 10 ** 6 + 1
is_prime = [1] * INF

def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return

def f(n):
    yakusu = []
    if is_prime[n]:
        yakusu.append(n)
    else:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                yakusu.append(i)
                if i != n //i:
                    yakusu.append(n // i)
                break

    for i in yakusu:
        if i != 1:
            d[i] += 1


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

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

cnt = 1
for i, v in d.items():
    if v != 1:
        cnt = max(cnt, v)

if cnt == N:
    print('not coprime')
elif cnt == 1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict,Counter
input = sys.stdin.readline

N = int(input())
As = list(map(int,input().split()))
divisors = defaultdict(int)
def make_divisors(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors[i]+=1
            if i != n // i:
                divisors[n//i]+=1

dvs = []
for i in As:
  make_divisors(i)

res=0
print(divisors)
for k,v in divisors.items():
  if k != 1 and v == N:
    res = 2
    break
  elif k != 1 and v>1:
    res = 1
#for i in com[1:]:
#  if i[1] == N:
#    res = 2
#    break
#  elif i[1] >1:
#    res = 1

if res == 0:
  print("pairwise coprime")
elif res == 1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict,Counter
input = sys.stdin.readline

N = int(input())
As = list(map(int,input().split()))
divisors = defaultdict(int)
def make_divisors(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors[i]+=1
            if i != n // i:
                divisors[n//i]+=1

dvs = []
for i in As:
  make_divisors(i)

res=0

for k,v in divisors.items():
  if k != 1 and v == N:
    res = 2
    break
  elif v>1:
    res = 1
#for i in com[1:]:
#  if i[1] == N:
#    res = 2
#    break
#  elif i[1] >1:
#    res = 1

if res == 0:
  print("pairwise coprime")
elif res == 1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict,Counter
input = sys.stdin.readline

N = int(input())
As = list(map(int,input().split()))
divisors = defaultdict(int)
def make_divisors(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors[i]+=1
            if i != n // i:
                divisors[n//i]+=1

dvs = []
for i in As:
  make_divisors(i)

res=0

for k,v in divisors.items():
  if k != 1 and v == N:
    res = 2
    break
  elif v>2:
    res = 1
#for i in com[1:]:
#  if i[1] == N:
#    res = 2
#    break
#  elif i[1] >1:
#    res = 1

if res == 0:
  print("pairwise coprime")
elif res == 1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
import numpy as np

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

seachPrimeNum(10**6)
print("finish")

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5)
        cnt_list = [0] * (n + 1)
        for i in range(2, limit + 1):
            if cnt_list[i] == 0:
                k = n // i
                for j in range(1, k + 1):
                    s = i * j
                    if cnt_list[s] == 0:
                        D[s] = i
                        cnt_list[s] = 1
        for l in range(limit, n + 1):
            if cnt_list[l] == 0:
                D[l] = l
                cnt_list[l] = 1
        return D



    N = I()
    A = LI()
    D = defaultdict()
    num_list = [0] * (10 ** 6 + 1)
    
    max_a = max(A)
    if max_a == 1:
        print("pairwise coprime")
        exit()
        
    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print('not coprime')
        exit()

    A_ = set(A)
    A_.discard(1)
    if len(A_) >= 90000:
        print('setwise coprime')
        exit()

    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        while a != 1:
            x = D[a]
            if num_list[x] == 1:
                print('setwise coprime')
                exit()
            num_list[x] = 1
            a //= x

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5)
        cnt_list = [0] * (n + 1)
        for i in range(2, limit + 1):
            if cnt_list[i] == 0:
                k = n // i
                for j in range(1, k + 1):
                    s = i * j
                    if cnt_list[s] == 0:
                        D[s] = i
                        cnt_list[s] = 1
        for l in range(limit, n + 1):
            if cnt_list[l] == 0:
                D[l] = l
                cnt_list[l] = 1
        return D



    N = I()
    A = LI()
    D = defaultdict()
    num_list = [0] * (10 ** 6 + 1)

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()

    A_ = set(A)
    A_.discard(1)
    if len(A_) >= 90000:
        print('setwise coprime')
        exit()

    max_a = max(A)

    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        while a != 1:
            x = D[a]
            if num_list[x] == 1:
                print('setwise coprime')
                exit()
            num_list[x] = 1
            a //= x

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5)
        cnt_list = [0] * (n + 1)
        for i in range(2, limit + 1):
            if cnt_list[i] == 0:
                k = n // i
                for j in range(1, k + 1):
                    s = i * j
                    if cnt_list[s] == 0:
                        D[s] = i
                        cnt_list[s] = 1
        for l in range(limit, n + 1):
            if cnt_list[l] == 0:
                D[l] = l
                cnt_list[l] = 1
        return D



    N = I()
    A = LI()
    D = defaultdict()
    num_list = [0] * (10 ** 6 + 1)

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()

    A_ = set(A)
    A_.discard(1)
    if len(A_) >= 90000:
        print("setwise coprime")
        exit()

    max_a = max(A)
    if max_a == 1:
        print('pairwise coprime')
        exit()
    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        while a != 1:
            x = D[a]
            if num_list[x] == 1:
                print('setwise coprime')
                exit()
            num_list[x] = 1
            a //= x

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
from functools import reduce


def facs(n):
    """試し割り法における割る数を生成する。"""
    yield 2
    for x in range(3, n, 2):
        yield x


def main():
    input()  # N
    array = [int(x) for x in input().split()]
    MAX_A = 10 ** 6 + 1
    histogram = [0] * MAX_A
    primes = []
    not_primes = set()
    divided_by = [-1] * MAX_A
    for x in facs(MAX_A):
        if x in not_primes:
            continue
        primes.append(x)
        divided_by[x] = x
        for y in range(x * 2, MAX_A, x):
            not_primes.add(y)
            if divided_by[y] == -1:
                divided_by[y] = x
    for x in array:
        histogram[divided_by[x]] += 1
    if max(histogram) < 2:
        return 'pairwise coprime'

    gcd_total = reduce(gcd, array)
    if gcd_total == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'


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