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
N = int(input())
A = list(map(int, input().split()))
ans1 = "pairwise coprime"
ans2 = "setwise coprime"
ans3 = "not coprime"

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

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

if a==1:
    b = True
    l = func(A[0])
    for i in range(1, N):
        
        if l&func(A[i])==set():
            l=l|func(A[i])
        else:
            b=False
            break
    if b:
        print(ans1)
    else:
        print(ans2)
        
        
    
else:
    print(ans3)

Submission status: Wrong Answer

Solution code:
import copy
from collections import defaultdict
import math

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

def fast_prime_factrization(A):
    maxA = max(A)
    D = [-1]*(maxA+1)
    for i in range(2,maxA+1):
        if D[i] != -1:
            continue
        for j in range(1,maxA+1):
            if i*j > maxA:
                break
            if D[i*j] == -1:
                D[i*j] = i
    pr_facts = [defaultdict(int) for i in range(len(A))]
    for i,a in enumerate(A):
        X = a
        while 1:
            if X == D[X]:
                pr_facts[i][D[X]] += 1
                break
            else:
                pr_facts[i][D[X]] += 1
                X //= D[X]
    return pr_facts
def check_pc():
    pr_facts = fast_prime_factrization(A)
    maxA = max(A)
    d = [False]*(maxA+1)
    ret = True
    for i in range(len(pr_facts)):
        for key in pr_facts[i].keys():
            if d[key]:
                ret = False
                break
            d[key] = True
        else:
            continue
        break
    return ret
pc = check_pc()

Submission status: Wrong Answer

Solution code:
import copy
from collections import defaultdict
import math

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

def fast_prime_factrization(A):
    maxA = max(A)
    D = [-1]*(maxA+1)
    for i in range(2,maxA+1):
        if D[i] != -1:
            continue
        for j in range(1,maxA+1):
            if i*j > maxA:
                break
            if D[i*j] == -1:
                D[i*j] = i
    pr_facts = [defaultdict(int) for i in range(len(A))]
    for i,a in enumerate(A):
        X = a
        while 1:
            if X == D[X]:
                pr_facts[i][D[X]] += 1
                break
            else:
                pr_facts[i][D[X]] += 1
                X //= D[X]
    return pr_facts

def check_sc():
    gcd = A[0]
    for i in range(1,len(A)):
        gcd = math.gcd(gcd,A[i])
    return gcd == 1

def check_pc():
    pr_facts = fast_prime_factrization(A)
    maxA = max(A)
    d = [False]*(maxA+1)
    ret = True
    for i in range(len(pr_facts)):
        for key in pr_facts[i].keys():
            if d[key]:
                ret = False
                break
            d[key] = True
        else:
            continue
        break
    return ret
                
pc = check_pc()
sc = check_sc()

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

Submission status: Wrong Answer

Solution code:
import copy
from collections import defaultdict

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

def check_sc():
    scs = set([i for i in range(1,A[0]+1)])
    for a in A:
        now = copy.copy(scs)
        for sc in now:
            if a % sc != 0:
                scs.remove(sc)
    
    scs = list(scs)
    return (len(scs) == 1)
  
sc = check_sc()

Submission status: Wrong Answer

Solution code:
import copy
from collections import defaultdict

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

def fast_prime_factrization(A):
    maxA = max(A)
    D = [-1]*(maxA+1)
    for i in range(2,maxA+1):
        if D[i] != -1:
            continue
        for j in range(1,maxA+1):
            if i*j > maxA:
                break
            if D[i*j] == -1:
                D[i*j] = i
    pr_facts = [defaultdict(int) for i in range(len(A))]
    for i,a in enumerate(A):
        X = a
        while 1:
            if X == D[X]:
                pr_facts[i][D[X]] += 1
                break
            else:
                pr_facts[i][D[X]] += 1
                X //= D[X]
    return pr_facts

def check_sc():
    scs = set([i for i in range(1,A[0]+1)])
    for a in A:
        now = copy.copy(scs)
        for sc in now:
            if a % sc != 0:
                scs.remove(sc)
    
    scs = list(scs)
    return (len(scs) == 1)

def check_pc():
    pr_facts = fast_prime_factrization(A)
    maxA = max(A)
    d = [False]*(maxA+1)
    ret = True
    for i in range(len(pr_facts)):
        for key in pr_facts[i].keys():
            if d[key]:
                ret = False
                break
            d[key] = True
        else:
            continue
        break
    return ret
                
pc = check_pc()
sc = check_sc()

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

Submission status: Wrong Answer

Solution code:
import copy
from collections import defaultdict

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

def fast_prime_factrization(A):
    maxA = max(A)
    D = [-1]*(maxA+1)
    for i in range(2,maxA+1):
        for j in range(1,maxA+1):
            if i*j > maxA:
                break
            if D[i*j] == -1:
                D[i*j] = i
    pr_facts = [defaultdict(int) for i in range(len(A))]
    for i,a in enumerate(A):
        X = a
        while 1:
            if X == D[X]:
                pr_facts[i][D[X]] += 1
                break
            else:
                pr_facts[i][D[X]] += 1
                X //= D[X]
    return pr_facts

def check_sc():
    scs = set([i for i in range(1,A[0]+1)])
    for a in A:
        now = copy.copy(scs)
        for sc in now:
            if a % sc != 0:
                scs.remove(sc)
    
    scs = list(scs)
    return (len(scs) == 1)

def check_pc():
    pr_facts = fast_prime_factrization(A)
    maxA = max(A)
    d = [False]*(maxA+1)
    ret = True
    for i in range(len(pr_facts)):
        for key in pr_facts[i].keys():
            if d[key]:
                ret = False
                break
            d[key] = True
        else:
            continue
        break
    return ret
                
pc = check_pc()
sc = check_sc()

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

Submission status: Wrong Answer

Solution code:
import copy
from collections import defaultdict

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

def fast_prime_factrization(A):
    maxA = max(A)
    print(maxA)
    D = [-1]*(maxA+1)
    for i in range(2,maxA+1):
        for j in range(1,maxA+1):
            if i*j > maxA:
                break
            if D[i*j] == -1:
                D[i*j] = i
    pr_facts = [defaultdict(int) for i in range(len(A))]
    for i,a in enumerate(A):
        X = a
        while 1:
            if X == D[X]:
                pr_facts[i][D[X]] += 1
                break
            else:
                pr_facts[i][D[X]] += 1
                X //= D[X]
    return pr_facts

def check_sc():
    scs = set([i for i in range(1,A[0]+1)])
    for a in A:
        now = copy.copy(scs)
        for sc in now:
            if a % sc != 0:
                scs.remove(sc)
    
    scs = list(scs)
    return (len(scs) == 1)

def check_pc():
    pr_facts = fast_prime_factrization(A)
    maxA = max(A)
    d = [False]*(maxA+1)
    ret = True
    for i in range(len(pr_facts)):
        for key in pr_facts[i].keys():
            if d[key]:
                ret = False
                break
            d[key] = True
        else:
            continue
        break
    return ret
                
pc = check_pc()
sc = check_sc()

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

Submission status: Wrong Answer

Solution code:
import copy
from collections import defaultdict

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

def fast_prime_factrization(A):
    maxA = max(A)
    print(maxA)
    D = [-1]*(maxA+1)
    for i in range(2,maxA+1):
        print(i)
        for j in range(1,maxA+1):
            if i*j > maxA:
                break
            if D[i*j] == -1:
                D[i*j] = i
    pr_facts = [defaultdict(int) for i in range(len(A))]
    for i,a in enumerate(A):
        X = a
        while 1:
            if X == D[X]:
                pr_facts[i][D[X]] += 1
                break
            else:
                pr_facts[i][D[X]] += 1
                X //= D[X]
    print(D)
    print(pr_facts)
    return pr_facts

def check_sc():
    scs = set([i for i in range(1,A[0]+1)])
    for a in A:
        now = copy.copy(scs)
        for sc in now:
            if a % sc != 0:
                scs.remove(sc)
    
    scs = list(scs)
    return (len(scs) == 1)

def check_pc():
    pr_facts = fast_prime_factrization(A)
    maxA = max(A)
    d = [False]*(maxA+1)
    ret = True
    for i in range(len(pr_facts)):
        for key in pr_facts[i].keys():
            if d[key]:
                ret = False
                break
            d[key] = True
        else:
            continue
        break
    return ret
                
pc = check_pc()
sc = check_sc()

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

Submission status: Wrong Answer

Solution code:
import copy
from collections import defaultdict

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

def fast_prime_factrization(A):
    maxA = max(A)
    D = [-1]*(maxA+1)
    for i in range(2,maxA+1):
        for j in range(1,maxA+1):
            if i*j > maxA:
                break
            if D[i*j] == -1:
                D[i*j] = i
        else:
            continue
        break
    pr_facts = [defaultdict(int) for i in range(len(A))]
    for i,a in enumerate(A):
        X = a
        while 1:
            if X == D[X]:
                pr_facts[i][D[X]] += 1
                break
            else:
                pr_facts[i][D[X]] += 1
                X //= D[X]
    return pr_facts

def check_sc():
    scs = set([i for i in range(1,A[0]+1)])
    for a in A:
        now = copy.copy(scs)
        for sc in now:
            if a % sc != 0:
                scs.remove(sc)
    
    scs = list(scs)
    return (len(scs) == 1)

def check_pc():
    pr_facts = fast_prime_factrization(A)
    maxA = max(A)
    d = [False]*(maxA+1)
    ret = True
    for i in range(len(pr_facts)):
        for key in pr_facts[i].keys():
            if d[key]:
                ret = False
                break
            d[key] = True
        else:
            continue
        break
    return ret
                
pc = check_pc()
sc = check_sc()

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

Submission status: Wrong Answer

Solution code:
import sys
#import time
from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
import heapq
#import math
import itertools
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

n = ri()
a = rl()
max_a = max(a)
for i in range(2, int(max_a**(1/2))+1):
    cnt=0
    for e in a:
        if e%i == 0:
            cnt+=1
    if cnt==n:
        print('not coprime')
        sys.exit()
    elif cnt>1:
        print('setwise coprime')
        sys.exit()
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def get_primes(n):
    max_p = int(n ** 0.5)
    p = 0 # 素数
    pl = []  # 素数リスト
    el = [i for i in range(2, n + 1)]  # 探索リスト
    while p <= max_p:
        nxt = []
        p = el[0]
        pl.append(p)
        for e in el:
            if e % p == 0:
                # D[e] = p
                pass
            else:
                nxt.append(e)
        el = nxt
    return pl


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

is_pc = True
is_sc = True

p_list = get_primes(N)
for p in p_list:
    t = [int(x % p == 0) for x in a]
    s = sum(t)
    if s >= 2:
        is_pc = False
    if s == N:
        is_sc = False
        break
if is_pc:
    print('pairwise coprime')
elif is_sc:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

is_pc = True
is_sc = True

i = 2
t = [int(x % i == 0) for x in a]
s = sum(t)
if s >= 2:
    is_pc = False
if s == N:
    is_sc = False

for i in range(3, 1000, 2):
    t = [int(x % i == 0) for x in a]
    s = sum(t)
    if s >= 2:
        is_pc = False
    if s == N:
        is_sc = False
        break
if is_pc:
    print('pairwise coprime')
elif is_sc:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
import random
J=int(1e9)+7

###############################################################################\n=17
X=[False]*(10**6+1)
P=[]
for i in range(2,len(X)):
    if X[i] is False:
        for j in range(2*i,len(X),i):
            X[j]=True
for i in range(2,len(X)):
    if X[i] is False:
        P.append(i)


n=int(input())
A=INPUT()
ans=0
V=[0]*(10**6+1)
for i in range(n):
    ans=math.gcd(ans,A[i])
    V[A[i]]+=1
if ans==1:
    bool=True
    for i in range(10**6+1):
        if V[i]>=2:
            bool=False
            break
    if bool:
        for ele in P:
            c=0
            for i in range(ele,10**6+1,ele):
                if V[i]>0 and i%ele==0:
                    c+=1
            if c>1:
                bool=False
                break
        if bool:
            print("pairwise coprime")
        else:
            print("setwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
import random
J=int(1e9)+7

###############################################################################\n=17
X=[False]*(10**6+1)
P=[]
for i in range(2,len(X)):
    if X[i] is False:
        for j in range(2*i,len(X),i):
            X[j]=True
for i in range(2,len(X)):
    if X[i] is False:
        P.append(i)


n=int(input())
A=INPUT()
ans=0
V=[0]*(10**6+1)
for i in range(n):
    ans=math.gcd(ans,A[i])
    V[A[i]]+=1
if ans==1:
    bool=True
    for i in range(10**6+1):
        if V[i]>=2:
            bool=False
            break
    if bool:
        for ele in P:
            c=0
            for i in range(ele,10**6+1,ele):
                if V[i]>0 and i%ele==0:
                    c+=1
            if c>1:
                bool=False
                break
        if bool:
            print("pairwise coprime")
        else:
            print("not coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import copy
from collections import defaultdict

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

def fast_prime_factrization(A):
    maxA = max(A)
    D = [-1]*(maxA+1)
    for i in range(2,maxA+1):
        for j in range(1,maxA+1):
            if i*j <= maxA and D[i*j] == -1:
                D[i*j] = i
    pr_facts = [defaultdict(int) for i in range(len(A))]
    for i,a in enumerate(A):
        X = a
        while 1:
            if X == D[X]:
                pr_facts[i][D[X]] += 1
                break
            else:
                pr_facts[i][D[X]] += 1
                X //= D[X]
    return pr_facts

def check_sc():
    scs = set([i for i in range(1,A[0]+1)])
    for a in A:
        now = copy.copy(scs)
        for sc in now:
            if a % sc != 0:
                scs.remove(sc)
    
    scs = list(scs)
    return (len(scs) == 1)

def check_pc():
    pr_facts = fast_prime_factrization(A)
    maxA = max(A)
    d = [False]*(maxA+1)
    ret = True
    for i in range(len(pr_facts)):
        for key in pr_facts[i].keys():
            if d[key]:
                ret = False
                break
            d[key] = True
        else:
            continue
        break
    return ret
                
pc = check_pc()
sc = check_sc()

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

Submission status: Wrong Answer

Solution code:
import sys


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


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

sosudayo = [True] * 1100000
sosudayo[0] = False
sosudayo[1] = False
for i in range(2, 1100000):
    if not sosudayo[i]:
        continue
    for j in range(i*i, 1100000, i):
        sosudayo[j] = False

ruto_sosu = [a for a in range(1100) if sosudayo[a]]

g = 0

for i in A:
    g = gcd(g, i)

if g != 1:
    print("not coprime")
    sys.exit()

used = [False] * 1100000
sosu = [a for a in A if sosudayo[a]]
for i in sosu:
    used[i] = True

not_sosu = [a for a in A if not sosudayo[a]]

for i in not_sosu:
    for j in ruto_sosu:
        if i == 1:
            break
        if i % j != 0:
            continue
        if used[j]:
            print("setwise coprime")
            sys.exit()
        used[j] = True
        while i % j == 0:
            i //= j
    if i > 1:
        if used[i]:
            print("setwise coprime")
        used[i] = True

print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys


def LI():
    return list(map(int, input().split()))


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


input()
A = LI()

sosu = [True]*1100000
sosu[0] = sosu[1] = False
for i in range(2, 1100000):
    if not sosu[i]:
        continue
    for j in range(i*i, 1100000, i):
        sosu[j] = False

g = 0
for i in A:
    g = gcd(g, i)
if g != 1:
    print("not coprime")
    sys.exit()

used = [False]*1100000
ruto_sosu = [a for a in range(1100) if sosu[a]]
sosudayo = [a for a in A if sosu[a]]
for i in sosudayo:
    used[i] = True
not_sosu = [a for a in A if not sosu[a]]


for i in not_sosu:
    for j in ruto_sosu:
        if i == 1:
            break
        if i % j != 0:
            continue
        if used[j]:
            print("setwise coprime")
            sys.exit()
        used[j] = True
        while i % j == 0:
            i //= j
    if i > 1:
        if used[i]:
            print("setwise coprime")
        used[i] = True

print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys


def LI():
    return list(map(int, input().split()))


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


input()
A = LI()

sosu = [True]*1100000
sosu[0] = sosu[1] = False
for i in range(2, 1100000):
    if not sosu[i]:
        continue
    for j in range(i*i, 1100000, i):
        sosu[j] = False

g = 0
for i in A:
    g = gcd(g, i)
if g != 1:
    print("not coprime")
    sys.exit()

used = [False]*1100000
sosudayo = [a for a in A if sosu[a]]
for i in sosudayo:
    used[i] = True

not_sosu = [a for a in A if not sosu[a]]
ruto_sosu = [a for a in range(1100) if sosu[a]]

for i in not_sosu:
    for j in ruto_sosu:
        if i == 1:
            break
        if i % j != 0:
            continue
        if used[j]:
            print("setwise coprime")
            sys.exit()
        used[j] = True
        while i % j == 0:
            i //= j
    if i > 1:
        if used[i]:
            print("setwise coprime")
        used[i] = True
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys


def LI():
    return list(map(int, input().split()))


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


input()
A = LI()
g = 0
for i in A:
    g = gcd(g, i)
if g != 1:
    print("not coprime")
    sys.exit()

sosu = [True]*1100000
sosu[0] = sosu[1] = False
for i in range(2, 1100000):
    if not sosu[i]:
        continue
    for j in range(i*i, 1100000, i):
        sosu[j] = False

used = [False]*1100000
sosudayo = [a for a in A if sosu[a]]
for i in sosudayo:
    used[i] = True
not_sosu = [a for a in A if not sosu[a]]
ruto_sosu = [a for a in range(1100) if sosu[a]]
for i in not_sosu:
    for j in ruto_sosu:
        if i == 1:
            break
        if i % j != 0:
            continue
        if used[j]:
            print("setwise coprime")
            sys.exit()
        used[j] = True
        while i % j == 0:
            i //= j
    if i > 1:
        if used[i]:
            print("setwise coprime")
        used[i] = True
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(11000000)


def LI():
    return list(map(int, input().split()))


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


input()
A = LI()
g = 0
for i in A:
    g = gcd(g, i)
if g != 1:
    print("not coprime")
    sys.exit()

sosu = [True]*1100000
sosu[0] = sosu[1] = False
for i in range(2, 1100000):
    if not sosu[i]:
        continue
    for j in range(i*i, 1100000, i):
        sosu[j] = False

used = [False]*1100000
sosudayo = [a for a in A if sosu[a]]
for i in sosudayo:
    used[i] = True
not_sosu = [a for a in A if not sosu[a]]
ruto_sosu = [a for a in range(1100) if sosu[a]]
for i in not_sosu:
    for j in ruto_sosu:
        if i == 1:
            break
        if i % j != 0:
            continue
        if used[j]:
            print("setwise coprime")
            sys.exit()
        used[j] = True
        while i % j == 0:
            i //= j
    if i > 1:
        if used[i]:
            print("setwise coprime")
        used[i] = True
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)


def LI():
    return list(map(int, input().split()))


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


input()
A = LI()
g = 0
for i in A:
    g = gcd(g, i)
if g != 1:
    print("not coprime")
    sys.exit()

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

used = [False]*(10**6+1)
sosudayo = [a for a in A if sosu[a]]
for i in sosudayo:
    used[i] = True
not_sosu = [a for a in A if not sosu[a]]
ruto_sosu = [a for a in range(1001) if sosu[a]]
for i in not_sosu:
    for j in ruto_sosu:
        if i == 1:
            break
        if i % j != 0:
            continue
        if used[j]:
            print("setwise coprime")
            sys.exit()
        used[j] = True
        while i % j == 0:
            i //= j
    if i > 1:
        if used[i]:
            print("setwise coprime")
        used[i] = True
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    maxA = max(A)
    if maxA == 1:
        print('pairwise coprime')
        return
    prime = [i if i % 2 != 0 else 2 for i in range(maxA+1)]
    f = [False] * (maxA+1)
    for i in range(3, int(maxA//2)+1):
        if prime[i] != i:
            continue
        p = i * 2
        while p <= maxA:
            if prime[p] == p:
                prime[p] = i
            p += i

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

    setwise_coprime = A[0]
    for An in A[1:]:
        setwise_coprime = gcd(setwise_coprime, An)
        if setwise_coprime == 1:
            break
    for An in A:
        if An == 1:
            continue
        # print('An = {}'.format(An))
        not_pairwise_coprime = False
        while prime[An] != An:
            # print('prime[An]={}, f[prime[An]]={}'.format(prime[An], f[prime[An]]))
            if f[prime[An]]:
                not_pairwise_coprime = True
                break
            f[prime[An]] = True
            prime_An = prime[An]
            while An % prime_An == 0:
                An //= prime_An
        else:
            if f[An]:
                not_pairwise_coprime = True
            else:
                f[An] = True
        if not_pairwise_coprime:
            break
        # print(f)
    else:
        print('pairwise coprime')
        return
    if setwise_coprime == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys


def LI():
    return list(map(int, input().split()))


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


N = LI()
A = LI()
g = 0
for a in A:
    g = gcd(g, a)
if g != 1:
    print("not coprime")
    sys.exit()

sosu = [True]*(1100000)
sosu[0] = sosu[1] = False
for i in range(2, 1100000):
    if not sosu[i]:
        continue
    for j in range(i*i, 1100000, i):
        sosu[j] = False

used = [False]*(1100000)
prime = [a for a in A if sosu[a]]
for i in prime:
    used[i] = True
not_prime = [a for a in A if not sosu[a]]
ruto_prime = [a for a in range(1100) if sosu[a]]
for i in not_prime:
    for j in ruto_prime:
        if i == 1:
            break
        if i % j != 0:
            continue
        if used[j]:
            print("setwise coprime")
            sys.exit()
        used[j] = True
        while i % j == 0:
            i //= j
    if i > 1:
        if used[i]:
            print("setwise coprime")
        used[i] = True
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
import sys


def LI():
    return list(map(int, input().split()))


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


N = LI()
A = LI()
g = 0
for a in A:
    g = gcd(g, a)
if g != 1:
    print("not coprime")
    sys.exit()

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

used = [False]*(10**6+1)
prime = [a for a in A if sosu[a]]
for i in prime:
    used[i] = True
not_prime = [a for a in A if not sosu[a]]
ruto_prime = [a for a in range(1001) if sosu[a]]
for i in not_prime:
    for j in ruto_prime:
        if i == 1:
            break
        if i % j != 0:
            continue
        if used[j]:
            print("setwise coprime")
            sys.exit()
        used[j] = True
        while i % j == 0:
            i //= j
    if i > 1:
        if used[i]:
            print("setwise coprime")
        used[i] = True
print("pairwise coprime")

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    maxA = max(A)
    if maxA == 1:
        print('pairwise coprime')
        return
    prime = [i if i % 2 != 0 else 2 for i in range(maxA+1)]
    prime[0] = 0
    f = [False] * (maxA+1)
    for i in range(3, int(maxA**.5)+1):
        if prime[i] != i:
            continue
        p = i * 2
        while p <= maxA:
            if prime[p] == p:
                prime[p] = i
            p += i

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

    pairwise_coprime = A[0]
    setwise_coprime = A[0]
    for An in A[1:]:
        setwise_coprime = gcd(setwise_coprime, An)
        if setwise_coprime == 1:
            break
    for An in A:
        if An == 1:
            continue
        # print('An = {}'.format(An))
        if f[An]:
            break
        else:
            not_pairwise_coprime = False
            while prime[An] != An:
                # print('prime[An]={}, f[prime[An]]={}'.format(prime[An], f[prime[An]]))
                if f[prime[An]]:
                    not_pairwise_coprime = True
                    break
                f[prime[An]] = True
                prime_An = prime[An]
                while An % prime_An == 0:
                    An //= prime_An
            else:
                if f[prime[An]]:
                    not_pairwise_coprime = True
                f[An] = True
            if not_pairwise_coprime:
                break
        # print(f)
    else:
        print('pairwise coprime')
        return
    if setwise_coprime == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


def gcd_list(numbers):
    return reduce(math.gcd, numbers)


def eratosthenes(n):
    D = [0]*(n+1)
    for i in range(2, n+1):
        if D[i] > 0:
            continue
        for j in range(i, n+1, i):
            D[j] = i
    return D


N = int(input())
A = list(map(int, input().split()))
D = eratosthenes(10**6+1)
# D = eratosthenes(max(A))
dic = {}
for i in A:
    while i != 1:
        if i in dic:
            dic[i] += 1
        else:
            dic[i] = 1
        i //= D[i]

isPairwise = True
for i in dic.items():
    if i[1] > 1:
        isPairwise = False

if isPairwise:
    print("pairwise coprime")
elif gcd_list(A) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
import math
 
N = int(input())
vals = [int(x) for x in input().split(" ")]
 
M = max(vals)
M_sqrt = int(math.sqrt(M))
 
count_list = [0 for _ in range(M+1)]
 
S = 1
 
for i in range(2, M_sqrt+1):
  
  k = 0
  
  for v in vals:  
 
    if v%i==0:
      count_list[i]+=1
      count_list[v//i]+=1
 
if N in count_list:
  print("not coprime")
elif any([a>1 for a in count_list]):
  print("setwise coprime")
else:
  print("pairwise coprime")