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: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
s.sort()
dp = [0] * ((10 ** 6) + 100)

for ss in s:
    dp[ss] += 1

A = max(s)
pairwise = True
setwise = True

for i in range(2, A + 1):
    cnt = 0
    for j in range(i, A + 1, i):
        cnt += dp[j]
    if cnt > 1:
        pairwise = False
    if cnt >= n:
        setwise = False
        break

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

Submission status: Accepted

Solution code:
import sys
from math import gcd

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

b = gcd(a[0], a[1])
for i in range(2, n):
    b = gcd(b, a[i])
if b != 1:
    print('not coprime')
else:
    c = set()
    num = max(a)
    m = 1000000
    vals = [0]*(m+1)

    for i in range(2, m):
        if vals[i] != 0:
            continue
        j = 1
        while True:
            t = i*j
            if t > m:
                break
            if vals[t] == 0:
                vals[t] = i
            j += 1
    d = dict()
    for i in a:
        p = i
        while p != 1:
            if p in d:
                print("setwise coprime")
                sys.exit()
            d[p] = 1
            p = int(p/vals[p])
    print("pairwise coprime")

Submission status: Accepted

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

def is_pairwise(A):
    D = gen_d_prim(10**6)
    past = set()
    for a in A:
        now = set()
        while a != 1:
            # 素数 D[a]: 今回は未済 & 過去で済
            if not D[a] in now and D[a] in past: return False
            now.add(D[a])
            past.add(D[a])
            a //= D[a]
    return True

def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def solve():
    if is_pairwise(A): return 0
    if gcd_all(A) == 1: return 1
    return 2

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

Submission status: Accepted

Solution code:
import sys
import math
import functools

def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))

    max_a = max(A)
    temp = [0] * (max_a + 1)
    temp[1] = 1

    for i in range(2, max_a + 1):
        if temp[i]:
            continue

        j = i
        while j < max_a + 1:
            if not temp[j]:
                temp[j] = i
            j += i

    B = set()
    for a in A:
        s = set()
        while a > 1:
            s.add(temp[a])
            a = a // temp[a]
        for v in s:
            if v in B:
                if functools.reduce(math.gcd, A) == 1:
                    return 'setwise coprime'
                else:
                    return 'not coprime'
            B.add(v)
    
    return 'pairwise coprime'
    

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
s = list(map(int, input().split()))
s.sort()
dp = [0] * ((10 ** 6) + 100)

res = s[0]
for ss in s:
    dp[ss] += 1
    res = gcd(res, ss)

A = max(s)
pairwise = True
setwise = (res == 1)

primes = set(range(2, A+1))
for i in range(2, int(A**0.5+1)):
    if i not in primes:
        i += 1
    else:
        ran = range(i*2, A+1,i)
        primes.difference_update(ran)
primes = list(primes)

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

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

Submission status: Accepted

Solution code:
# ρ法でとおるかためす。

# 参考1: https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
# 参考2: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
# 参考3: https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%A9%E3%83%BC%E3%83%89%E3%83%BB%E3%83%AD%E3%83%BC%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E6%B3%95


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def is_prime(n):
    "Miller Rabin primality test. 2 <= n <= 2 ** 64 is required"
    if n % 2 == 0:
        return n == 2
    d = n - 1
    r = (d & -d).bit_length() - 1
    d >>= r

    # witnesses をいい感じに決める。
    if n < 2152302898747:
        if n < 9080191:
            if n < 2047:
                witnesses = [2]
            else:
                witnesses = [31, 73]
        else:
            if n < 4759123141:
                witnesses = [2, 7, 61]
            else:
                witnesses = [2, 3, 5, 7, 11]
    else:
        if n < 341550071728321:
            if n < 3474749660383:
                witnesses = [2, 3, 5, 7, 11, 13]
            else:
                witnesses = [2, 3, 5, 7, 11, 13, 17]
        else:
            if n < 3825123056546413051:
                witnesses = [2, 3, 5, 7, 11, 13, 17, 19]
            else:
                witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
    # witnesses の決定終了

    for a in witnesses:
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x *= x
            x %= n
            if x == n - 1:
                break
        else:
            return False
    return True


def find_factor(n):
    "Find a non-trivial factor of n by using Pollard's rho algorithm."
    m = int(n ** 0.125) + 1
    c = 1
    while True:
        y = 1
        r = 1
        q = 1
        g = 1
        while g == 1:
            x = y
            for _ in range(r):
                y = (y * y + c) % n
            for k in range(0, r, m):
                ys = y
                for _ in range(m):
                    y = (y * y + c) % n
                    q = q * (x - y) % n
                g = gcd(q, n)
                if g != 1:
                    break
            else:  # 残りの k から r までをやる
                ys = y
                for _ in range(r-k):
                    y = (y * y + c) % n
                    q = q * (x - y) % n
                g = gcd(q, n)
            r *= 2

        if g == n:
            g = 1
            while g == 1:
                ys = (ys * ys + c) % n
                g = gcd(x - ys, n)

        if g == n:
            c += 1  # c を変えて続行。
        else:  # g は n の非自明な素因数。
            return g


def fac(n):
    "計算量は O(n ^ 1/4) 程度。"
    if n == 1:
        return []
    if is_prime(n):
        return [n]

    ret = []
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]:
        while n % p == 0:
            ret.append(p)
            n //= p
        if n == 1:
            return ret

    while n != 1 and not is_prime(n):
        f = find_factor(n)
        if is_prime(f):
            while n % f == 0:
                ret.append(f)
                n //= f
        elif is_prime(n // f):
            ret.append(n // f)
            n = f
        else:
            return sorted(ret + fac(f) + fac(n // f))

    if n == 1:
        return sorted(ret)
    else:
        ret.append(n)
        return sorted(ret)




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

g = 0
for A in As:
    g = gcd(g, A)

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

primes = set()
for A in As:
    ps = set(fac(A))
    if ps & primes:
        print("setwise coprime")
        exit()
    else:
        primes |= ps

print("pairwise coprime")

Submission status: Accepted

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

n = int(input())
s = list(map(int, input().split()))
s.sort()
dp = [0] * ((10 ** 6) + 100)

res = s[0]
for ss in s:
    dp[ss] += 1
    res = gcd(res, ss)

A = max(s)
pairwise = True
setwise = (res == 1)

for i in range(2, A + 1):
    cnt = 0
    for j in range(i, A + 1, i):
        cnt += dp[j]
    if cnt > 1:
        pairwise = False
        break

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

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import math,sys

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))
#n = int(input())
#a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])

for e in a:
    asf = set(factrial(e))
    if judge & asf != set():
        print("setwise coprime")
        exit()
    judge |= asf
    #judge = judge | asf #too slow
print("pairwise coprime")

Submission status: Accepted

Solution code:
def gen_d_prim(n):
    D = [n+1 if i%2 else 2 for i in range(n+1)]
    D[0] = D[1] = 0
    for i in range(3, n+1, 2):
        if D[i] != n+1: continue
        for j in range(i, n+1, i): D[j] = i
    return D

def is_pairwise(A):
    D = gen_d_prim(10**6)
    past = set()
    for a in A:
        now = set()
        while a != 1:
            # 素数 D[a]: 今回は未済 & 過去で済
            if not D[a] in now and D[a] in past: return False
            now.add(D[a])
            past.add(D[a])
            a //= D[a]
    return True

def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def solve():
    if is_pairwise(A): return 0
    if gcd_all(A) == 1: return 1
    return 2

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

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import math,sys

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))
#n = int(input())
#a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])

for e in a:
    asf = set(factrial(e))
    if judge & asf != set():
        print("setwise coprime")
        exit()
    judge |= asf
    #judge = judge | asf #too slow
print("pairwise coprime")

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import math,sys

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))
#n = int(input())
#a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])
pc = True

pairwise = True
p = set() #all prime

for e in a:
    if not pairwise:
        break
    asf = set(factrial(e))
    if judge & asf != set():
        pc = False
    #     #pairwise = False
    #     print("setwise coprime")
    #     exit(0)
    judge |= asf
# for i in a:
#     if not pc:
#         break
#     asf = set(factrial(i))

#     if judge & asf != set():
#         pc = False
#     judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import math,sys

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))
#n = int(input())
#a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])
pc = True

pairwise = True
p = set() #all prime

for e in a:
    if not pairwise:
        break
    # f = set(factrial(e))
    # #print(p,f)
    # if p & f != set():
    #     pc = False
    #     #pairwise = False
    #     print("setwise coprime")
    #     exit(0)
    # p = p | f
for i in a:
    if not pc:
        break
    asf = set(factrial(i))

    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
s = list(map(int, input().split()))
s.sort()
dp = [0] * ((10 ** 6) + 100)

res = s[0]
for ss in s:
    dp[ss] += 1
    res = gcd(res, ss)

A = max(s)
pairwise = True
setwise = (res == 1)

for i in range(2, A + 1):
    cnt = 0
    for j in range(i, A + 1, i):
        cnt += dp[j]
    if cnt > 1:
        pairwise = False
        break

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

Submission status: Accepted

Solution code:
# def gen_is_prim(n):
#     is_prim = [i%2==1 for i in range(n+1)]
#     is_prim[1] = False; is_prim[2] = True
#     for i in range(3, n+1, 2):
#         if not is_prim[i]: continue
#         for j in range(i+i, n+1, i):
#             is_prim[j] = False
#     return is_prim

def gen_d_prim(n):
    D = [n+1 if i%2 else 2 for i in range(n+1)]
    D[0] = D[1] = 0
    for i in range(3, n+1, 2):
        if D[i] != n+1: continue
        for j in range(i, n+1, i): D[j] = i
    return D

def gcd_all(A):
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    return g

def is_pairwise():
    # MAX_A = 10**6 + 1
    # C = [0] * MAX_A
    # for a in A: C[a] += 1
    # if sum(C[2::2]) > 1: return False
    # for i in range(3, MAX_A, 2):
    #     if sum(C[i::i]) > 1: return False
    # return True

    MAX_A = 10**6
    D = gen_d_prim(MAX_A)
    C = [0] * (MAX_A + 1)
    all_p = set()
    for a in A:
        p = set()
        while a != 1:
            if not D[a] in p:
                if D[a] in all_p:
                    return False
            all_p.add(D[a])
            p.add(D[a])
            a //= D[a]
        # print('pre {}'.format(pre))
        # print('now {}'.format(now))
        # print('now & pre {}'.format(now & pre))
        # if len(now & all) > 0: return False
        # all = all | now
    return True

def solve():
    if is_pairwise(): return 0
    if gcd_all(A) == 1: return 1
    return 2

    # if gcd_all(A) > 1: return 2
    # if is_pairwise(): return 0
    # return 1


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

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
s = list(map(int, input().split()))
s.sort()
dp = [0] * ((10 ** 6) + 100)

res = s[0]
for ss in s:
    dp[ss] += 1
    res = gcd(res, ss)

A = max(s)
pairwise = True
setwise = (res == 1)

for i in range(2, A + 1):
    cnt = 0
    for j in range(i, A + 1, i):
        cnt += dp[j]
    if cnt > 1:
        pairwise = False

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

Submission status: Accepted

Solution code:
import math

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
NUM = 1_000_005
aa = [0]*NUM
pgcd = True
sgcd = a[n-1]
aa[a[n-1]]+=1
for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
    aa[a[i]]+=1

for i in range(2,NUM):
    tmp = sum(aa[i::i])
    if tmp >= 2:
        pgcd = False
        break
        
if sgcd!=1:
    print('not coprime')
elif pgcd:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
s = list(map(int, input().split()))
s.sort()
dp = [0] * ((10 ** 6) + 100)

res = s[0]
for ss in s:
    dp[ss] += 1
    res = gcd(res, ss)

A = max(s)
pairwise = True

for i in range(2, A + 1):
    cnt = 0
    for j in range(i, A + 1, i):
        cnt += dp[j]
    if cnt > 1:
        pairwise = False

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque

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


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


max_A = max(A)

if max_A == 1:
    print('pairwise coprime')
    exit()
# エラトステネスの篩により素数を高速で求める
# そのかんにある数値がふるい落とされたその素数をメモしておく

D = [0] * (max_A + 1)
is_prime = [True] * (max_A + 1)
is_prime[0] = False
is_prime[1] = False
prime = deque()
for i in range(2, int(max_A ** 0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, max_A + 1, i):
        is_prime[j] = False
        D[j] = i

for i in range(len(is_prime)):
    if is_prime[i]:
        D[i] = i

pairwise = True
check = [0] * (max_A + 1)
new_A = A[:]
for i in range(N):
    min_prime = D[new_A[i]]
    while True:
        if D[min_prime] == 0:
            break

        check[D[min_prime]] += 1
        while new_A[i] % min_prime == 0:
            new_A[i] //= min_prime

        min_prime = new_A[i]

        # print(check)


# print(D)
# print(check)

if max(check) > 1:
    pairwise = False
# print(check)
if pairwise:
    print('pairwise coprime')
else:
    if gcd_list(A) == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Accepted

Solution code:

import sys
from math import gcd
from functools import reduce

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

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

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

if reduce(gcd,ap)!=1:
    print("not coprime")
    sys.exit()
    
if n>=78500 :
    print("setwise coprime")
    sys.exit()

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1
    
for pp in range(2,amax+1):
    psum=sum(aa[pp: :pp])
#    print("pp:",pp,psum)
    if psum>=2:
            print("setwise coprime")
            sys.exit()
## max_13.txt ... max_16.txt : "setwise coprime"
print("pairwise coprime")

Submission status: Accepted

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

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

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1
    
for pp in range(2,amax+1):
    psum=sum(aa[pp: :pp])
#    print("pp:",pp,psum)
    if psum>=2:
            print("setwise coprime")
            sys.exit()
## max_13.txt ... max_16.txt : "setwise coprime"
print("pairwise coprime")

Submission status: Accepted

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


import math

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
    while search_list[0] <= math.sqrt(number):
      #search_listの先頭の値が√nの値を超えたら終了
      #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        search_list = [num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list

#p=get_primenumber(79000)

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

p=get_primenumber(amax)

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1
    
#for pp in range(2,amax+1):
for pp in p:
#    psum=0
#    for pi in range(pp,amax+1,pp):
#        psum+=aa[pi]
    psum=sum(aa[pp: :pp])
#    print("pp:",pp,psum)
    if psum>=2:
            print("setwise coprime")
            sys.exit()
## max_13.txt ... max_16.txt : "setwise coprime"
print("pairwise coprime")

Submission status: Accepted

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


import math

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
    while search_list[0] <= math.sqrt(number):
      #search_listの先頭の値が√nの値を超えたら終了
      #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        search_list = [num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list

#p=get_primenumber(79000)

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

p=get_primenumber(amax)

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1
    
#for pp in range(2,amax+1):
for pp in p:
    psum=0
    for pi in range(pp,amax+1,pp):
        psum+=aa[pi]
#    psum=sum(aa[pp: :pp])
#    print("pp:",pp,psum)
    if psum>=2:
            print("setwise coprime")
            sys.exit()
## max_13.txt ... max_16.txt : "setwise coprime"
print("pairwise coprime")

Submission status: Accepted

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


import math

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
    while search_list[0] <= math.sqrt(number):
      #search_listの先頭の値が√nの値を超えたら終了
      #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        search_list = [num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list

#p=get_primenumber(79000)

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

p=get_primenumber(amax)

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1
    
for pp in range(2,amax+1):
#for pp in p:
    psum=0
    for pi in range(pp,amax+1,pp):
        psum+=aa[pi]
#    psum=sum(aa[pp: :pp])
#    print("pp:",pp,psum)
    if psum>=2:
            print("setwise coprime")
            sys.exit()
## max_13.txt ... max_16.txt : "setwise coprime"
print("pairwise coprime")

Submission status: Accepted

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


import math

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
    while search_list[0] <= math.sqrt(number):
      #search_listの先頭の値が√nの値を超えたら終了
      #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        search_list = [num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list

p=get_primenumber(79000)

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

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1
    
for pp in range(2,amax+1):
#for pp in p:
    psum=0
    for pi in range(pp,amax+1,pp):
#    for pi in range(pp,amax+pp-1,pp):
        psum+=aa[pi]
#    psum=sum(aa[pp: :pp])
#    print("pp:",pp,psum)
    if psum>=2:
            print("setwise coprime")
            sys.exit()
## max_13.txt ... max_16.txt : "setwise coprime"
print("pairwise coprime")