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.

Solution (Python):
import math
import unittest
import sys


class PrimeFactorization:
    def __init__(self, upper_limit):
        _primes, minimam_prime_factor = PrimeFactorization.list_primes(
            upper_limit)
        self.minimam_prime_factor = minimam_prime_factor

    def list_primes(upper_limit):
        
        if upper_limit <= 2:
            return [], [0, 1]

        minimam_prime_factor = [i if i %
                                2 == 1 else 2 for i in range(upper_limit)]
        minimam_prime_factor[0] = 0
        primes = [2]
        is_prime = [i % 2 == 1 for i in range(upper_limit)]
        for i in range(3, upper_limit, 2):
            if not is_prime[i]:
                continue
            primes.append(i)
            for j in range(i*i, upper_limit, i):
                is_prime[j] = False
                if minimam_prime_factor[j] == j:
                    minimam_prime_factor[j] = i
        return primes, minimam_prime_factor

    def list_prime_factors(self, n) -> set:
        factors = set()
        while 1 < n:
            factors.add(self.minimam_prime_factor[n])
            n //= self.minimam_prime_factor[n]
        return factors


class TestPrimeFactorization(unittest.TestCase):
    def test1(self):
        primes, minimam_prime_factor = PrimeFactorization.list_primes(1)
        self.assertEqual(primes, [])
        self.assertEqual(minimam_prime_factor, [0, 1])

    def test2(self):
        primes, minimam_prime_factor = PrimeFactorization.list_primes(2)
        self.assertEqual(primes, [])
        self.assertEqual(minimam_prime_factor, [0, 1])

    def test3(self):
        primes, minimam_prime_factor = PrimeFactorization.list_primes(3)
        self.assertEqual(primes, [2])
        self.assertEqual(minimam_prime_factor, [
                         0, 1, 2])

    def test20(self):
        primes, minimam_prime_factor = PrimeFactorization.list_primes(20)
        self.assertEqual(primes, [2, 3, 5, 7, 11, 13, 17, 19])
        self.assertEqual(minimam_prime_factor, [
                         0, 1, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19])


def is_pairwise_coprime(n, a):
    pf = PrimeFactorization(max(a)+1)
    e = set()
    for ai in a:
        e2 = pf.list_prime_factors(ai)
        if e & e2:
            return False
        e |= e2
    return True


def is_setwise_coprime(n, a):
    gcd = a[0]
    for i in range(1, n):
        gcd = math.gcd(gcd, a[i])
        if gcd == 1:
            return True
    return gcd == 1


def solve(n, a):
    if is_pairwise_coprime(n, a):
        return 'pairwise coprime'
    elif is_setwise_coprime(n, a):
        return 'setwise coprime'
    else:
        return 'not coprime'


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(n, a))


if __name__ == "__main__":
    main()


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


class Test(unittest.TestCase):
    def test_1(self):
        n = 3
        a = [3, 4, 5]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_2(self):
        n = 3
        a = [6, 10, 15]
        self.assertEqual(is_pairwise_coprime(n, a), False)
        self.assertEqual(is_setwise_coprime(n, a), True)
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_3(self):
        n = 3
        a = [6, 10, 16]
        self.assertEqual(solve(n, a), 'not coprime')

    def test_4(self):
        n = 3
        a = [1, 1, 1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_5(self):
        n = 3
        a = [1, 2, 2]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_6(self):
        n = 10
        a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_7(self):
        n = 11
        a = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_8(self):
        n = 2
        a = [1, 1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_9(self):
        n = 2
        a = [1, 2]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_10(self):
        n = 2
        a = [10**6, 10**6-1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_11(self):
        n = 3
        a = [10**6, 10**6-1, 10**6, ]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_12(self):
        n = len(PRIMES) * 2
        a = PRIMES + PRIMES
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_13(self):
        a = [997, 1009, 1013, 1019, 1021, 1031, 1033, 1039,
             1049, 1051, 1061, 1063, 1069, 1087, ]
        n = len(a)
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_14(self):
        a = [1009*2, 1013*3, 1019*5, 1021, 1031, 1033, 1039,
             1049, 1051, 1061, 1063, 1069, 1087, ]
        n = len(a)
        self.assertEqual(solve(n, a), 'pairwise coprime')

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
max_A = 10**6+1

dp = [0] * (max_A)
for i in range(N):
    dp[A[i]] += 1

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

pairwise = True

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

if pairwise:
    print("pairwise coprime")
    exit()

from math import gcd

g = 0
for i in range(N):
    g = gcd(g, A[i])
if g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
import sys
import math
import fractions
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]



def prime_fact(n):
    if n == 1:
        return {1: 1}

    prime_dict = {}
    for i in range(2, int(n**0.5)+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()

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

    SA = set(A)
    if len(SA) >= 90000:
        print("setwise coprime")
        exit()

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline


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

    counts = [0] * (10**6 + 1)
    for a in A:
        counts[a] += 1

    ans = 1
    for i in range(2, 10**6+1):
        co_primes = 0
        for j in range(i, 10**6+1, i):
            co_primes += counts[j]
        if ans < co_primes:
            ans = co_primes

    if ans == 1:
        print("pairwise coprime")
    elif ans < n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Solution (Python):
from math import gcd


def eratosthenes(n):
    is_prime = [0, 0] + [1] * (n - 1)
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i] == 1:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return [i for i in range(n + 1) if is_prime[i] == 1]


def factorize(N):  
    PRIME = set()
    for p in prime_list:
        if p * p > N:
            break
        while N % p == 0:
            N //= p
            PRIME.add(p)
    if N > 1:
        PRIME.add(N)
    return PRIME


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

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

prime_list = eratosthenes(10 ** 6)
num = set()
for ai in a:
    prime = factorize(ai)
    if len(prime & num) > 0:
        print('setwise coprime')
        break
    num |= prime
else:
    print('pairwise coprime')

Solution (Python):
from math import gcd
from functools import reduce


class SmallestPrimeFactors:
    def __init__(self, n):
        self.spf = list(range(n + 1))
        for i in range(2, int(n ** 0.5) + 1):
            if self.spf[i] == i:
                for j in range(i * i, n + 1, i):
                    if self.spf[j] == j:
                        self.spf[j] = i

    def factor(self, x):
        if self.spf[x] == x:
            return [x]
        nxt = x // self.spf[x]
        return self.factor(nxt) + [self.spf[x]]


def is_PC():
    spf = SmallestPrimeFactors(1_000_000)
    primes = set()
    for a in A:
        if a == 1:
            continue
        new_primes = set(spf.factor(a))
        if primes & new_primes:
            return False
        primes |= new_primes
    return True


def is_SC():
    return reduce(gcd, A) == 1


N, *A = map(int, open(0).read().split())
if not is_SC():
    print("not coprime")
elif is_PC():
    print("pairwise coprime")
else:
    print("setwise coprime")

Solution (Python):
from math import gcd

def p_factorization_osa_k(vl):
    vmax = max(vl)
    min_primes = list(range(vmax+1))  
    for i in range(2, int(vmax**0.5) + 1):
        if min_primes[i] != i: continue  
        for j in range(i,vmax+1,i): 
            min_primes[j] = min(min_primes[j], i) 

    results = []
    for v in vl:
        p_cnt = {}
        curr_v = v
        while curr_v > 1:
            min_p = min_primes[curr_v]
            p_cnt.setdefault(min_p,0)
            p_cnt[min_p] += 1
            curr_v //= min_p
        results.append(p_cnt)
    return results


n = int(input())
al = list(map(int, input().split()))
afl = p_factorization_osa_k(al)

pset = set()
no_pairwise = False
for af in afl:
    for p in af.keys():
        if p in pset:
            no_pairwise = True
            break
        pset.add(p)
    if no_pairwise:
        break
else:
    print('pairwise coprime')
    exit()


c_gcd = al[0]
for a in al[1:]:
    c_gcd = gcd(c_gcd,a)

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
max_A = 10**6+1

dp = [0] * (max_A)
for i in range(N):
    dp[A[i]] += 1

pairwise = True

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

if pairwise:
    print("pairwise coprime")
    exit()

from math import gcd

g = 0
for i in range(N):
    g = gcd(g, A[i])
if g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Solution (Python):
import sys
import math
import fractions
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]



def prime_fact(n, ela):
    if n == 1:
        return {1: 1}

    prime_dict = {}
    for i in ela:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela = [i for i, b in enumerate(ela) if b]

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

    SA = set(A)
    if len(SA) >= 90000:
        print("setwise coprime")
        exit()

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == "__main__":
    main()

Solution (Python):
from math import gcd
from functools import reduce


class SmallestPrimeFactors:
    def __init__(self, n):
        self.spf = list(range(n + 1))
        for i in range(2, int(n ** 0.5) + 1):
            if self.spf[i] == i:
                for j in range(i * i, n + 1, i):
                    if self.spf[j] == j:
                        self.spf[j] = i

    def factor(self, x):
        if self.spf[x] == x:
            return [x]
        nxt = x // self.spf[x]
        return self.factor(nxt) + [self.spf[x]]


def is_PC():
    M = max(A)
    spf = SmallestPrimeFactors(M)
    counter = [0] * (M + 1)
    for a in A:
        if a == 1:
            continue
        new_primes = set(spf.factor(a))
        for np in new_primes:
            if counter[np]:
                return False
            counter[np] = 1
    return True


def is_SC():
    return reduce(gcd, A) == 1


N, *A = map(int, open(0).read().split())
if not is_SC():
    print("not coprime")
elif is_PC():
    print("pairwise coprime")
else:
    print("setwise coprime")

Solution (Python):
def main():
    from math import gcd
    n, *a = map(int, open(0).read().split())
    m = 10 ** 6 + 1

    c = [0] * (m + 1)
    g = a[0]
    for i in a:
        g = gcd(g, i)
        c[i] = 1

    if g > 1:
        pre = "not"
    else:
        for i in range(2, 10 ** 6 + 1):
            if sum(c[i::i]) > 1:
                pre = "setwise"
                break
        else:
            pre = "pairwise"

    print(pre + " coprime")


if __name__ == '__main__':
    main()

Solution (Python):
from math import gcd


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


def factorize(N):  
    prime = set()
    for p in prime_list:
        if p * p > N:
            break
        while N % p == 0:
            N //= p
            prime.add(p)
    if N > 1:
        prime.add(N)
    return prime


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

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

prime_list = eratosthenes(10 ** 6)
num = set()
for ai in a:
    prime = factorize(ai)
    if len(prime & num) > 0:
        print('setwise coprime')
        break
    num |= prime
else:
    print('pairwise coprime')

Solution (Python):
import math
import unittest
import sys


class PrimeFactorization:
    def __init__(self, upper_limit):
        _primes, minimam_prime_factor = PrimeFactorization.list_primes(
            upper_limit)
        self.minimam_prime_factor = minimam_prime_factor

    def list_primes(upper_limit):
        
        minimam_prime_factor = [i for i in range(upper_limit)]
        if upper_limit <= 2:
            return [], [0, 1]

        primes = []
        is_prime = [True] * upper_limit
        for i in range(2, upper_limit):
            if not is_prime[i]:
                continue
            minimam_prime_factor[i] = i
            primes.append(i)
            for j in range(i*i, upper_limit, i):
                is_prime[j] = False
                if minimam_prime_factor[j] == j:
                    minimam_prime_factor[j] = i
        return primes, minimam_prime_factor

    def list_prime_factors(self, n) -> set:
        factors = set()
        while 1 < n:
            factors.add(self.minimam_prime_factor[n])
            n //= self.minimam_prime_factor[n]
        return factors


class TestPrimeFactorization(unittest.TestCase):
    def test(self):
        primes, minimam_prime_factor = PrimeFactorization.list_primes(20)
        self.assertEqual(primes, [2, 3, 5, 7, 11, 13, 17, 19])
        self.assertEqual(minimam_prime_factor, [
                         0, 1, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19])


def is_pairwise_coprime(n, a):
    pf = PrimeFactorization(max(a)+1)
    e = set()
    for ai in a:
        e2 = pf.list_prime_factors(ai)
        if e & e2:
            return False
        e |= e2
    return True


def is_setwise_coprime(n, a):
    gcd = a[0]
    for i in range(1, n):
        gcd = math.gcd(gcd, a[i])
        if gcd == 1:
            return True
    return gcd == 1


def solve(n, a):
    if is_pairwise_coprime(n, a):
        return 'pairwise coprime'
    elif is_setwise_coprime(n, a):
        return 'setwise coprime'
    else:
        return 'not coprime'


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(n, a))


if __name__ == "__main__":
    main()


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


class Test(unittest.TestCase):
    def test_1(self):
        n = 3
        a = [3, 4, 5]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_2(self):
        n = 3
        a = [6, 10, 15]
        self.assertEqual(is_pairwise_coprime(n, a), False)
        self.assertEqual(is_setwise_coprime(n, a), True)
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_3(self):
        n = 3
        a = [6, 10, 16]
        self.assertEqual(solve(n, a), 'not coprime')

    def test_4(self):
        n = 3
        a = [1, 1, 1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_5(self):
        n = 3
        a = [1, 2, 2]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_6(self):
        n = 10
        a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_7(self):
        n = 11
        a = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_8(self):
        n = 2
        a = [1, 1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_9(self):
        n = 2
        a = [1, 2]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_10(self):
        n = 2
        a = [10**6, 10**6-1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_11(self):
        n = 3
        a = [10**6, 10**6-1, 10**6, ]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_12(self):
        n = len(PRIMES) * 2
        a = PRIMES + PRIMES
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_13(self):
        a = [997, 1009, 1013, 1019, 1021, 1031, 1033, 1039,
             1049, 1051, 1061, 1063, 1069, 1087, ]
        n = len(a)
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_14(self):
        a = [1009*2, 1013*3, 1019*5, 1021, 1031, 1033, 1039,
             1049, 1051, 1061, 1063, 1069, 1087, ]
        n = len(a)
        self.assertEqual(solve(n, a), 'pairwise coprime')

Solution (Python):
def main():
    from math import gcd
    n, *a = map(int, open(0).read().split())
    m = 10 ** 6 + 1

    c = [0] * (m + 1)
    g = a[0]
    for i in a:
        g = gcd(g, i)
        c[i] = 1

    if g > 1:
        pre = "not"
    else:
        for i in range(2, 10 ** 6 + 1):
            if sum(c[i::i]) > 1:
                pre = "setwise"
                break
        else:
            pre = "pairwise"

    print(pre + " coprime")


if __name__ == '__main__':
    main()

Solution (Python):
import math
import unittest
import sys


class PrimeFactorization:
    def __init__(self, upper_limit):
        _primes, minimam_prime_factor = PrimeFactorization.list_primes(
            upper_limit)
        self.minimam_prime_factor = minimam_prime_factor

    def list_primes(upper_limit):
        
        minimam_prime_factor = [i for i in range(upper_limit)]
        if upper_limit <= 2:
            return [], [0, 1]

        is_prime = [True] * upper_limit
        sqrt_upper_limit = int(upper_limit**0.5+1)
        for i in range(2, sqrt_upper_limit):
            if not is_prime[i]:
                continue
            minimam_prime_factor[i] = i
            for j in range(i*i, upper_limit, i):
                is_prime[j] = False
                if minimam_prime_factor[j] == j:
                    minimam_prime_factor[j] = i
        primes = [2]
        for i in range(3, upper_limit, 2):
            if is_prime[i]:
                minimam_prime_factor[i] = i
                primes.append(i)
        return primes, minimam_prime_factor

    def list_prime_factors(self, n) -> set:
        factors = set()
        while 1 < n:
            factors.add(self.minimam_prime_factor[n])
            n //= self.minimam_prime_factor[n]
        return factors


class TestPrimeFactorization(unittest.TestCase):
    def test(self):
        primes, minimam_prime_factor = PrimeFactorization.list_primes(20)
        self.assertEqual(primes, [2, 3, 5, 7, 11, 13, 17, 19])
        self.assertEqual(minimam_prime_factor, [
                         0, 1, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19])


def is_pairwise_coprime(n, a):
    pf = PrimeFactorization(max(a)+1)
    e = set()
    for ai in a:
        e2 = pf.list_prime_factors(ai)
        if e & e2:
            return False
        e |= e2
    return True


def is_setwise_coprime(n, a):
    gcd = a[0]
    for i in range(1, n):
        gcd = math.gcd(gcd, a[i])
        if gcd == 1:
            return True
    return gcd == 1


def solve(n, a):
    if is_pairwise_coprime(n, a):
        return 'pairwise coprime'
    elif is_setwise_coprime(n, a):
        return 'setwise coprime'
    else:
        return 'not coprime'


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(n, a))


if __name__ == "__main__":
    main()


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


class Test(unittest.TestCase):
    def test_1(self):
        n = 3
        a = [3, 4, 5]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_2(self):
        n = 3
        a = [6, 10, 15]
        self.assertEqual(is_pairwise_coprime(n, a), False)
        self.assertEqual(is_setwise_coprime(n, a), True)
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_3(self):
        n = 3
        a = [6, 10, 16]
        self.assertEqual(solve(n, a), 'not coprime')

    def test_4(self):
        n = 3
        a = [1, 1, 1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_5(self):
        n = 3
        a = [1, 2, 2]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_6(self):
        n = 10
        a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_7(self):
        n = 11
        a = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_8(self):
        n = 2
        a = [1, 1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_9(self):
        n = 2
        a = [1, 2]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_10(self):
        n = 2
        a = [10**6, 10**6-1]
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_11(self):
        n = 3
        a = [10**6, 10**6-1, 10**6, ]
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_12(self):
        n = len(PRIMES) * 2
        a = PRIMES + PRIMES
        self.assertEqual(solve(n, a), 'setwise coprime')

    def test_13(self):
        a = [997, 1009, 1013, 1019, 1021, 1031, 1033, 1039,
             1049, 1051, 1061, 1063, 1069, 1087, ]
        n = len(a)
        self.assertEqual(solve(n, a), 'pairwise coprime')

    def test_14(self):
        a = [1009*2, 1013*3, 1019*5, 1021, 1031, 1033, 1039,
             1049, 1051, 1061, 1063, 1069, 1087, ]
        n = len(a)
        self.assertEqual(solve(n, a), 'pairwise coprime')