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):
        
        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')

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

    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):
def main():
    from math import gcd
    n, *a = map(int, open(0).read().split())
    m = max(a)

    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 sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def _make_minimum_prime(N: int):
    
    min_prime = [x for x in range(N + 1)]
    
    
    for i in range(2, int(N ** 0.5) + 1):
        if min_prime[i] == i:  
            for j in range(2 * i, N + 1, i):  
                if min_prime[j] == j:
                    min_prime[j] = i
    return min_prime


min_prime = _make_minimum_prime(10**6)


from collections import Counter


def fast_factorization(N: int):
    
    
    if N == 1:
        return Counter()  
    
    arr = []
    tmp = N
    while tmp != 1:
        p = min_prime[tmp]
        tmp //= p
        arr.append(p)

    return Counter(arr)


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
import random
from math import gcd


N = a_int()
A = ints()
random.shuffle(A)






g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  
for a in A:
    g_set = gcd(g_set, a)
    if flg:
        for p, n in fast_factorization(a).items():
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n








if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def _make_minimum_prime(N: int):
    
    min_prime = [x for x in range(N + 1)]
    
    
    for i in range(2, int(N ** 0.5) + 1):
        if min_prime[i] == i:  
            for j in range(2 * i, N + 1, i):  
                if min_prime[j] == j:
                    min_prime[j] = i
    return min_prime


min_prime = _make_minimum_prime(10**6)


from collections import Counter


def fast_factorization(N: int):
    
    
    if N == 1:
        return Counter()  
    
    arr = []
    tmp = N
    while tmp != 1:
        p = min_prime[tmp]
        tmp //= p
        arr.append(p)

    return Counter(arr)


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from math import gcd


N = a_int()
A = ints()






g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  
for a in A:
    g_set = gcd(g_set, a)
    for p, n in fast_factorization(a).items():
        if cnt[p] != 0:
            flg = 0
        cnt[p] += n








if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Solution (Python):
class Prime():
    def __init__(self, n):
        self.p = [] 
        self.d = [0] * n 

        
        for i in range(2, n):
            if self.d[i] == 0:
                self.p.append(i)
                for j in range(i, n, i):
                    if self.d[j] == 0:
                        self.d[j] = i

        self.ind = [-1] * n 
        for i in range(len(self.p)):
            self.ind[self.p[i]] = i

    def prime_factorization_index(self, x): 
        l = [self.ind[self.d[x]]]
        x //= self.d[x]
        while x != 1:
            if l[-1] != self.ind[self.d[x]]:
                l.append(self.ind[self.d[x]])
            x //= self.d[x]
        return l

    def num_prime(self): 
        return len(self.p)

def main():

    from math import gcd
 
    n = int(input())
    a = list(map(int, input().split()))

    
    g = a[0]
    for i in a:
        g = gcd(g, i)
        if g == 1:
            break
    else:
        print('not coprime')
        exit()

    
    p = Prime(10**6 + 1)

    tf = [False] * p.num_prime() 

    for i in a:
        if i == 1:
            continue

        l = p.prime_factorization_index(i)
        for j in l:
            if tf[j]:
                print('setwise coprime')
                exit()
            else:
                tf[j] = True

    print('pairwise coprime')

main()

Solution (Python):
import math
import unittest
import sys


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

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

        is_prime = [True] * (max_n+1)
        sqrt_max_n = int(max_n**0.5+1)
        for i in range(2, sqrt_max_n):
            if not is_prime[i]:
                continue
            minimam_prime_factor[i] = i
            for j in range(i*i, max_n+1, i):
                is_prime[j] = False
                if minimam_prime_factor[j] == j:
                    minimam_prime_factor[j] = i
        for i in range(3, max_n+1, 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, 2])


def is_pairwise_coprime(n, a):
    pf = PrimeFactorization(max(a))
    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):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def _make_minimum_prime(N: int):
    
    min_prime = [x for x in range(N + 1)]
    
    
    for i in range(2, int(N ** 0.5) + 1):
        if min_prime[i] == i:  
            for j in range(2 * i, N + 1, i):  
                if min_prime[j] == j:
                    min_prime[j] = i
    return min_prime


min_prime = _make_minimum_prime(10**6)


from collections import Counter


def fast_factorization(N: int):
    
    
    if N == 1:
        return Counter()  
    
    arr = []
    tmp = N
    while tmp != 1:
        p = min_prime[tmp]
        tmp //= p
        arr.append(p)

    return Counter(arr)


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from math import gcd


N = a_int()
A = ints()






g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  
for a in A:
    g_set = gcd(g_set, a)
    if flg:
        for p, n in fast_factorization(a).items():
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n








if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def _make_minimum_prime(N: int):
    
    min_prime = [x for x in range(N + 1)]
    
    
    for i in range(2, int(N ** 0.5) + 1):
        if min_prime[i] == i:  
            for j in range(2 * i, N + 1, i):  
                if min_prime[j] == j:
                    min_prime[j] = i
    return min_prime


min_prime = _make_minimum_prime(10**6)


from collections import Counter


def fast_factorization(N: int):
    
    
    if N == 1:
        return Counter()  
    
    arr = []
    tmp = N
    while tmp != 1:
        p = min_prime[tmp]
        tmp //= p
        arr.append(p)

    return Counter(arr)


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from math import gcd


N = a_int()
A = ints()






g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  
for a in A:
    g_set = gcd(g_set, a)
    if flg:
        for p, n in fast_factorization(a).items():
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n








if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Solution (Python):
class Prime():
    def __init__(self, n):
        self.p = [] 
        self.d = [0] * n 

        
        for i in range(2, n):
            if self.d[i] == 0:
                self.p.append(i)
                for j in range(i, n, i):
                    if self.d[j] == 0:
                        self.d[j] = i

        self.ind = [-1] * n 
        for i in range(len(self.p)):
            self.ind[self.p[i]] = i

    def prime_factorization_index(self, x): 
        l = [self.ind[self.d[x]]]
        x //= self.d[x]
        while x != 1:
            if l[-1] != self.ind[self.d[x]]:
                l.append(self.ind[self.d[x]])
            x //= self.d[x]
        return l

    def num_prime(self): 
        return len(self.p)

def main():

    from math import gcd
 
    n = int(input())
    a = list(map(int, input().split()))

    
    g = a[0]
    for i in range(1, n):
        g = gcd(g, a[i])
        if g == 1:
            break
    else:
        print('not coprime')
        exit()

    
    p = Prime(10**6 + 1)

    tf = [False] * p.num_prime()

    for i in a:
        if i == 1:
            continue

        l = p.prime_factorization_index(i)
        for j in l:
            if tf[j]:
                print('setwise coprime')
                exit()
            else:
                tf[j] = True

    print('pairwise coprime')

main()

Solution (Python):
class Prime():
    def __init__(self, n):
        self.p = [] 
        self.d = [0] * n 

        
        for i in range(2, n):
            if self.d[i] == 0:
                self.p.append(i)
                for j in range(i, n, i):
                    if self.d[j] == 0:
                        self.d[j] = i

        self.ind = [-1] * n 
        for i in range(len(self.p)):
            self.ind[self.p[i]] = i

    def prime_factorization_index(self, x): 
        l = [self.ind[self.d[x]]]
        x //= self.d[x]
        while x != 1:
            if l[-1] != self.ind[self.d[x]]:
                l.append(self.ind[self.d[x]])
            x //= self.d[x]
        return l

    def num_prime(self): 
        return len(self.p)

def main():

    from math import gcd
 
    n = int(input())
    a = list(map(int, input().split()))

    
    g = a[0]
    for i in range(1, n):
        g = gcd(g, a[i])
        if g == 1:
            break
    else:
        print('not coprime')
        exit()

    
    p = Prime(10**6 + 1)

    tf = [False] * p.num_prime()

    for i in a:
        if i == 1:
            continue

        l = p.prime_factorization_index(i)
        for j in l:
            if tf[j]:
                print('setwise coprime')
                exit()
            else:
                tf[j] = True

    print('pairwise coprime')

main()

Solution (Python):
import sys
from math import gcd
stdin = sys.stdin

n = int(input())
an = list(map(int, stdin.readline().split()))
bn = []

m = max(an)
ls = [i for i in range(m+1)]
for i in range(2, m+1):
    if ls[i] == i:
        for j in range(2, m//i+1):
            ls[i*j] = i


def primeset(t):
    ls2 = set()
    while t != 1:
        ls2.add(ls[t])
        t = t//ls[t]
    return ls2



primes= set()
for i in an:
    for j in primeset(i):
        if j in primes:
            break
    else:
        primes |= primeset(i)
        continue
    break
else:
    print("pairwise coprime")
    exit(0)

GCD = an[0]
for i in range(1, n):
    GCD = gcd(GCD, an[i])
if GCD == 1:
    print("setwise coprime")
else:
    print('not coprime')

Solution (Python):
import collections
N = int(input())
A = [int(_) for _ in input().split()]


def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a


d = collections.defaultdict(int)
for a in A:
    for x in prime_factorize(a):
        d[x] += 1
if len(d):
    e = max(d.values())
if len(d) == 0 or e == 1:
    ans = 'pairwise coprime'
elif e == N:
    ans = 'not coprime'
else:
    ans = 'setwise coprime'
print(ans)

Solution (Python):
import math
import sys
import random

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

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

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 serial >= sqrt:
            return input_list

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

input_list = sieve_of_erastosthenes(10**6+1)
prime_list = [i for i, b in enumerate(input_list) if b == True]

def factorization(n):
    arr = []
    temp = n
    for i in prime_list:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr
random.shuffle(a)
g = a[0]
arr = factorization(a[0])
used = set()
for i in arr:
    if i == 1: continue
    used.add(i)


for i in range(n-1):
    g = gcd(g, a[i+1])
if g > 1:
    print('not coprime')
    exit(0)


used = [0] * (10**6+1)
pair = True
for _a in a:
    if _a == 1:
        continue
    if used[_a]:
        print('setwise coprime')
        exit(0)
    else:
        used[_a] = True

for p in prime_list:
    v = p
    cnt = 0
    while v < 10**6+1:
        if used[v]:
            cnt+=1
        v += p
    if cnt > 1:
        print('setwise coprime')
        exit(0)
print('pairwise coprime')

Solution (Python):

import sys
from math import gcd
from functools import reduce
from typing import Iterable
M = 10**6
def main(N, A):
    g = reduce(gcd, A)
    if g > 1:
        print('not coprime')
        return

    s = EratosthenesSieve(M)
    u = [False] * (M + 1)
    for a in A:
        for f in set(s.factor(a)):
            if u[f]:
                print('setwise coprime')
                return
            u[f] = True
    print('pairwise coprime')

class EratosthenesSieve:
    def __init__(self, max_n: int):
        f = list(range(max_n + 1))
        for i in range(2, int(max_n**0.5) + 1):
            if f[i] < i: continue
            for j in range(i * i, max_n + 1, i):
                if f[j] == j: f[j] = i
        self.f = f

    def is_prime(self, n: int) -> bool:
        return self.f[n] == n

    def factor(self, n: int) -> Iterable[int]:
        r, f = [], self.f
        while n > 1:
            m = f[n]
            r.append(m)
            n //= m
        return r

    def primes(self) -> Iterable[int]:
        return [x for i, x in enumerate(self.f) if i == x]

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)

Solution (Python):
import math
import sys
import random

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

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

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 serial >= sqrt:
            return input_list

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

input_list = sieve_of_erastosthenes(10**6+1)
prime_list = [i for i, b in enumerate(input_list) if b == True]

def factorization(n):
    arr = []
    temp = n
    for i in prime_list:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr
random.shuffle(a)
g = a[0]
arr = factorization(a[0])
used = set()
for i in arr:
    if i == 1: continue
    used.add(i)


for i in range(n-1):
    g = gcd(g, a[i+1])
if g > 1:
    print('not coprime')
    exit(0)


used = [0] * (10**6+1)
pair = True
for _a in a:
    if _a == 1:
        continue
    if used[_a]:
        print('setwise coprime')
        exit(0)
    else:
        used[_a] = True

for p in prime_list:
    v = p
    cnt = 0
    while v < 10**6+1:
        if used[v]:
            cnt+=1
        v += p
    if cnt > 1:
        print('setwise coprime')
        exit(0)
print('pairwise coprime')

Solution (Python):
def main():
    from math import gcd
    from functools import reduce, lru_cache

    n, *a, = map(int, open(0).read().split())
    m = max(a)

    d = [0] * (m + 1)
    d[1] = 1
    for i in range(2, m + 1):
        for j in range(i, m + 1, i):
            if d[j] == 0:
                d[j] = i

    @lru_cache()
    def primes(x):
        ps = set()
        while x != 1:
            p = d[x]
            ps.add(p)
            x = x // d[x]
        return ps

    b = set()
    f = 0
    g = a[0]
    for i in range(n):
        x = a[i]
        ps = primes(x)
        g = gcd(g, x)
        if b & ps:
            f = 1
            break
        b |= ps
    if f > 0 and gcd(g, reduce(gcd, a[i:])) != 1:
        f = 2

    ans = ["pairwise coprime", "setwise coprime", "not coprime"][f]
    print(ans)


if __name__ == '__main__':
    main()

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

A=max(a)

def min_factor(k):
    d=[]
    for i in range(k+1):
        d.append(i)

    i=2
    while i*i<=k:
        if d[i]==i:
            j=i*i
            while j<=k:
                if d[j]==j:
                    d[j]=i
                j+=i
        i+=1
    
    return d

def prime_factor_set(p):
    s=set()
    while p!=1:
        s.add(d[p])
        p//=d[p]  
    
    return s


d=min_factor(A)
cur=set()
flg=True
for i in range(n):
    tmp = prime_factor_set(a[i])
    if len(cur&tmp)>=1:
        flg=False
        break
    cur |= tmp

import numpy as np

g= np.gcd.reduce(a)

if flg:
    ans='pairwise coprime'
elif not flg and g==1:
    ans='setwise coprime'
else:
    ans='not coprime'

print(ans)

Solution (Python):
def main():
    from math import gcd
    from functools import reduce
    n, *a, = map(int, open(0).read().split())
    m = max(a)

    d = [0] * (m + 1)
    d[1] = 1
    for i in range(2, m + 1):
        for j in range(i, m + 1, i):
            if d[j] == 0:
                d[j] = i

    def primes(x):
        ps = set()
        while x != 1:
            p = d[x]
            ps.add(p)
            x = x // d[x]
        return ps

    b = set()
    f = 0
    for i in a:
        ps = primes(i)
        if b & ps:
            f = 1
            break
        b |= ps
    if f > 0 and reduce(gcd, a) != 1:
        f = 2

    ans = ["pairwise coprime", "setwise coprime", "not coprime"][f]
    print(ans)


if __name__ == '__main__':
    main()