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: Runtime Error

Solution code:
import sys
import math
from io import StringIO
import unittest


def resolve():
    N, = map(int, input().split())
    As = list(map(int, input().split()))
    # allprimes = []
    common_primes = None
    all_primes = set()
    all_uniq_primes_n = 0
    d = get_d(1000000)
    for i, a in enumerate(As):

        primes = get_primes_fast(a, d, set())
        # print(f'a {a} primes:{primes}')
        all_uniq_primes_n += len(primes)
        all_primes = all_primes | primes
        if i == 0:
            common_primes = primes
        else:
            # print(f'bef {common_primes} primes:{primes}')
            common_primes = primes & common_primes
            # print(f'aft {common_primes}')
        
    if len(common_primes) > 0:

        print('not coprime')

    elif all_uniq_primes_n == len(all_primes):
        print('pairwise coprime')
    else:
        print('setwise coprime')


def get_primes_fast(a, d, primes):
    is_div = False
    if d[a] != a:
        is_div = True
        primes.add(d[a])
        get_primes_fast(int(a / d[a]), d, primes)
    if not is_div:
        primes.add(a)
    return primes


def get_primes(a, start_n, primes):
    is_div = False
    for i in range(start_n, math.floor(math.sqrt(a) + 1)):
        if a % i == 0:
            is_div = True
            primes.add(i)
            get_primes(int(a / i), i, primes)
    if not is_div:
        primes.add(a)
    return primes


def get_d(A):
    d = [0] * (A + 1)
    for i in range(2, A + 1):
        for k in range(1, int(A / i)):
            if d[i * k] == 0:
                d[i * k] = i
    return d


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(output, out)

    def test_入力例_1(self):
        input = """3
3 4 5"""
        output = """pairwise coprime"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
6 10 15"""
        output = """setwise coprime"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """3
6 10 16"""
        output = """not coprime"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()
    # unittest.main()

Submission status: Runtime Error

Solution code:
def get_sieve_of_eratosthenes(n):
    table = [i if i % 2 else 2 for i in range(n + 1)]
    prime = [2]
    limit = int(n ** 0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return table, prime + data
        prime.append(p)
        next_data = []
        for e in data:
            if e % p != 0:
                next_data.append(e)
            else:
                table[e] = p
        data = next_data


N = int(input())
A = [int(i) for i in input().split()]
A.sort()
M = A[-1]
table, primes = get_sieve_of_eratosthenes(M)
Divisor = [0 for i in range(M + 1)]

#print(table)
#print(primes)
for a in A:
    aa = a
    while True:
        Divisor[table[aa]] += 1
        div = table[aa]
        while not aa % div:
            aa = aa // div
        if aa == 1:
            break

Max_div = max(Divisor)
#print(Max_div)
if Max_div == 1:
    print("pairwise coprime")
elif Max_div == N:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Runtime Error

Solution code:
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000

# 約数　倍数
def gcb(a, b):
    if b == 0:
        return a
    else:
        return gcb(b, a % b)

def lcm(a, b):
    d = gcb(a, b)
    return int(a / d * b)

def divisorList(a):
    l = []
    for i in range(1, int(a**0.5)+1):
        if a % i == 0:
            l.append(i)
            ii = a / i
            if i != ii:
                l.append(ii)
    return sorted(l)

def primeNumList(a):
    if a <= 1:
        return []
    else:
        multiple_list = [2]
        serial_number_list = [r for r in range(2, a + 1) if r % 2 != 0]

        # 5. 連番リストの先頭が、入力値の平方根以上で終了
        while len(serial_number_list) > 0:
            multiple_list.append(serial_number_list[0])
            for serial_number in range(serial_number_list[0], serial_number_list[- 1] + 1, serial_number_list[0]):
                if serial_number in serial_number_list:
                    serial_number_list.remove(serial_number)

        return multiple_list

def main():
    # ------ 入力 ------#
    n = int(input())    # 数字
    aList = list(map(int, input().split()))     # スペース区切り連続数字

    # ------ 処理 ------#
    amax = max(aList)
    pl = primeNumList(amax)
    countList = [0] * len(pl)
    for a in aList:
        for i in range(len(pl)):
            if a % pl[i] == 0:
                countList[i] += 1

    # ------ 出力 ------#
    m = max(countList)
    if m == len(aList):
        print("not coprime")
    elif m >= 2:
        print("setwise coprime")
    else:
        print("pairwise coprime")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
//#pragma GCC target("avx2,avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
constexpr char ln = '\n';
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
struct Fast_ios {Fast_ios() {cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20);};} fast_ios;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

struct Osa_k {
    int N;
    vector<int> table;

    Osa_k() {}
    Osa_k(int N) : N(N), table(N+1) {
        iota(table.begin(),table.end(),0);
        for (int i = 2; i*i <= N; i++) {
            if (table[i] == i) {
                for (int j = i; j <= N; j += i) {
                    if (table[j]==j) table[j] = i;
                }
            }
        }
    }

    int operator[](int i) const {return table[i];}

    vector<pair<int, int>> prime_factor(int x) {
        assert(1 <= x and x <= N);
        vector<pair<int, int>> ret;
        while (x != 1) {
            if (ret.empty() or ret.back().first != table[x]) {
                ret.emplace_back(table[x],1);
            } else {
                ret.back().second++;
            }
            x /= table[x];
        }

        return ret;
    }
};

////////////////////////////////////////////////////////////////////////////////////////////////////////////

void ABC177E() {
    int N; cin >> N;
    vector<int> A(N);
    rep(i,N) cin >> A[i];
    
    const int MAX = 1e6;
    Osa_k Os(MAX);
    vector<bool> seen(MAX+1);
    bool pc = true;
    int g = 0;
    rep(i,N) {
        auto a = Os.prime_factor(A[i]);
        for (auto j : a) {
            if (seen[j.first]) pc = false;
            else seen[j.first] = 1;
        }
        g = gcd(g,A[i]);
    }

    if (pc) {
        cout << "pairwise coprime" << ln;
    } else {
        cout << (g == 1 ? "setwise coprime" : "not coprime") << ln;
    }
}

int main() {
    ABC177E();
}

Submission status: Runtime Error

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


def f2(n, D):
    s = set()
    x = n
    while x > 1:
        p = D[x]
        s.add(p)
        x = x // p
    return s


from math import gcd


def is_nc(n, al):
    g = al[0]
    for i, a in enumerate(al):
        if i == 0:
            continue
        else:
            g = gcd(g, a)
            if g == 1:
                return False
    return True


def is_sc(n, al):
    D, pl = f1(max(al))
    count = {p: 0 for p in pl}
    for a in al:
        p_s = f2(a, D)
        for p in p_s:
            if count[p] == 1:
                return True
            else:
                count[p] += 1
    return False


n = int(input())
al = list(map(int, input().split()))
if is_nc(n, al):
    print('not coprime')
elif is_sc(n, al):
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

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


def f2(n, D):
    if n == 1:
        return {1}
    s = set()
    x = n
    while x > 1:
        p = D[x]
        s.add(p)
        x = x // p
    return s


from math import gcd


def is_nc(n, al):
    g = al[0]
    for i, a in enumerate(al):
        if i == 0:
            continue
        else:
            g = gcd(g, a)
            if g == 1:
                return False
    return True


def is_sc(n, al):
    D, pl = f1(max(al))
    count = {p: 0 for p in pl}
    for a in al:
        p_s = f2(a, D)
        for p in p_s:
            if count[p] == 1:
                return True
            else:
                count[p] += 1
    return False


n = int(input())
al = list(map(int, input().split()))
if is_nc(n, al):
    print('not coprime')
elif is_sc(n, al):
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

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


def f2(n, D):
    s = set()
    x = n
    while x > 1:
        p = D[x]
        s.add(p)
        x = x // p
    return s


from math import gcd
from collections import defaultdict


def is_nc(n, al):
    g = al[0]
    for i, a in enumerate(al):
        if i == 0:
            continue
        else:
            g = gcd(g, a)
            if g == 1:
                return False
    return True


def is_sc(n, al):
    D, pl = get_prime(max(al))
    count = {p: 0 for p in pl}
    for a in al:
        p_s = f2(a, D)
        for p in p_s:
            if count[p] == 1:
                return True
            else:
                count[p] += 1
    return False


n = int(input())
al = list(map(int, input().split()))
if is_nc(n, al):
    print('not coprime')
elif is_sc(n, al):
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
from math import gcd

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

# 解説AC(a*loga)
ans = 0
cnt = [0] * (max(a) + 1)
for ai in a:
    ans = gcd(ans, ai)
    cnt[ai] += 1

if ans != 1:
    print('not coprime')
elif any(sum(cnt[i::i]) > 1 for i in range(max(a) + 1)):
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
n=int(input())
m=list(map(int,input().split()))
a=max(m)
s=[-1]*(a+1)
for i in range(2,a+1):
    if s[i]==-1:
        for j in range(i,a+1,i):
            s[j]=i
import math
if a==1:
    print("pairwise coprime")
else:
    g=math.gcd(m[0],m[1])
    for i in range(2,n):
        g=math.gcd(g,m[i])
        if g==1:
            break
    if g>1:
        print("not coprime")
    else:
        f=set()
        for i in range(n):
            
            if m[i]>1:
                r=1
                while m[i]>1:
                    k=s[m[i]]
                    if k in f:
                        r=0
                        break
                    while m[i]%k==0:
                        m[i]//=k
                    f.add(k)
            if r==0:
                print("setwise coprime")
                break
        else:
            print("pairwise coprime")

Submission status: Runtime Error

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)
sosu[0] = sosu[1] = False
for i in range(2, 10**6):
    if not sosu[i]:
        continue
    for j in range(i*i, 10**6, i):
        sosu[j] = False

used = [False]*(10**6)
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(1000) 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: Runtime Error

Solution code:
def gcd(U,Q):
  if Q==0:
    return U
  return gcd(Q,U%Q)
def lcm(U,Q):
  return U/gcd(U,Q)*Q
N=input()
N=int(N)
a=list(map(int,input().split()))
b,c,d=0,1,1
for i in range(N):
  b=gcd(a[i],b)
  c=lcm(a[i],c)
  d*=a[i]
if b!=1:
  print("not coprime")
elif c!=d:
  print("setwise coprime")
else:
  print("pairwise coprime")

Submission status: Runtime Error

Solution code:
def gcd(U,Q):
  if Q==0:
    return U
  return gcd(Q,U//Q)

def lcm(U,Q):
  return U/gcd(U,Q)*Q

N=input()
a=list(map(int,input().split()))
b,c,d=0,0,1
for i in range(1,N):
  b=gcd(a[i],b)
  c=lcm(a[i],c)
  d*=a[i]

if b!=1:
  print("not coprime")
elif c!=d:
  print("setwise coprime")
else:
  print("pairwise coprime")

Submission status: Runtime Error

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_sqrt+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")

Submission status: Runtime Error

Solution code:
import math
# エラトステネスの古いで高速化してるけど、O(AloglolgA + NlogA)なので、
# 普通に計算してもO(NlogA)で計算できいるので門d内ないのでは？

# sエラトステネスの篩は頭の中に出てきたけど、一定の値までの素数を列挙するという問題だったので、活用できないと思ってしまsった。

N = int(input())
TOP = 10**6+1
D = [i for i in range(100)]


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        tmp = []
        for e in data:
            if e % p != 0:
                tmp.append(e)
            else:
                D[e] = p
        data = tmp


get_sieve_of_eratosthenes(100)
for i in range(len(D)):
    d = D[i]
    if d % 2 == 0:
        D[i] = 2


def retrive_prime(x):
    res = {}
    while True:
        d = D[x]
        if d in res:
            res[d] += 1
        else:
            res[d] = 1
        if d == x:
            break
        x //= d
    return res


B = [int(x) for x in input().split()]
A = [retrive_prime(x) for x in B]
ifPairwise = True
ifSetwier = True
data = [0 for _ in range(10**6+1)]
pair = math.gcd(B[0], B[1])
for i in range(N-1):
    a = A[i]
    pair = math.gcd(pair, B[i])
    for x in a.keys():
        if data[x-1] == 1:
            ifPairwise = False
        else:
            data[x-1] = 1
pair = math.gcd(pair, B[-1])
for a in A[-1].keys():
    if data[a-1] == 1:
        ifPairwise = False
    else:
        data[a-1] = 1

if not pair == 1:
    ifSetwier = False

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

Submission status: Runtime Error

Solution code:
import math
import collections
import copy
import sys

n = int(input())

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

sCheck = math.gcd(a[0],a[1])
if n == 2:
    if sCheck == 1:
        print("pairwise coprime")
    else:
        print("not coprime")
    sys.exit()
else:
    for i in range(2,n):
        sCheck = math.gcd(sCheck,a[i])


beforeQ = collections.deque([int(i) for i in range(3,(10**6 + 1))])
D = dict()
p = 2
D[2] = 2
D[1] = 1

while p < math.sqrt(10**6):
    afterQ = collections.deque()
    while len(beforeQ) > 0:        
        k = beforeQ.popleft()
        if k % p != 0:
            afterQ.append(k)
        else:
            D[k] = p
    beforeQ = copy.copy(afterQ)
    p = beforeQ.popleft()
    D[p] = p
    
ansSet = set()
count = 0

for i in a:
    k = i
    kSet = set()
    while k != 1:
        if D[k] in ansSet:
            if not(D[k] in kSet):
                count = 1
                break
        else:
            ansSet.add(D[k])
            kSet.add(D[k])
        k = int(k // D[k])
    if count == 1:
        break

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

Submission status: Runtime Error

Solution code:
import math
import collections
import copy
import sys

n = int(input())

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

sCheck = math.gcd(a[0],a[1])
if n == 2:
    if sCheck == 1:
        print("pairwise coprime")
    else:
        print("not coprime")
    sys.exit()
else:
    for i in range(2,n):
        sCheck = math.gcd(sCheck,a[i])


beforeQ = collections.deque([i for i in range(3,(10**6 + 1))])
D = dict()
p = 2
D[2] = 2
D[1] = 1

while p < math.sqrt(10**6):
    afterQ = collections.deque()
    while len(beforeQ) > 0:        
        k = beforeQ.popleft()
        if k % p != 0:
            afterQ.append(k)
        else:
            D[k] = p
    beforeQ = copy.copy(afterQ)
    p = beforeQ.popleft()
    D[p] = p
    
ansSet = set()
count = 0

for i in a:
    k = int(i)
    kSet = set()
    while k != 1:
        if D[k] in ansSet:
            if not(D[k] in kSet):
                count = 1
                break
        else:
            ansSet.add(D[k])
            kSet.add(D[k])
        k = int(k // D[k])

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

Submission status: Runtime Error

Solution code:
import math
import collections
import copy
import sys

n = int(input())

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

sCheck = math.gcd(a[0],a[1])
if n == 2:
    if sCheck == 1:
        print("pairwise coprime")
    else:
        print("not coprime")
    sys.exit()
else:
    for i in range(2,n):
        sCheck = math.gcd(sCheck,a[i])


beforeQ = collections.deque([i for i in range(3,(10**6 + 1))])
D = dict()
p = 2
D[2] = 2
D[1] = 1

while p < math.sqrt(10**6):
    afterQ = collections.deque()
    while len(beforeQ) > 0:        
        k = beforeQ.popleft()
        if k % p != 0:
            afterQ.append(k)
        else:
            D[k] = p
    beforeQ = copy.copy(afterQ)
    p = beforeQ.popleft()
    D[p] = p
    
ansSet = set()
count = 0

for i in a:
    k = i
    kSet = set()
    while k != 1:
        if D[k] in ansSet:
            if not(D[k] in kSet):
                count = 1
                break
        else:
            ansSet.add(D[k])
            kSet.add(D[k])
        k = k // D[k]

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

Submission status: Runtime Error

Solution code:
import math
import collections
import copy
import sys

n = int(input())

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

sCheck = math.gcd(a[0],a[1])
if n == 2:
    if sCheck == 1:
        print("pairwise coprime")
    else:
        print("not coprime")
    sys.exit()
else:
    for i in range(2,n):
        sCheck = math.gcd(sCheck,a[i])


beforeQ = collections.deque([i for i in range(2,10**6 + 1)])
D = dict()
p = 2
D[2] = 2
D[1] = 1

while p < math.sqrt(10**6):
    afterQ = collections.deque()
    while len(beforeQ) > 0:        
        k = beforeQ.popleft()
        if k % p != 0:
            afterQ.append(k)
        else:
            D[k] = p
    beforeQ = copy.copy(afterQ)
    p = beforeQ.popleft()
    D[p] = p
    
ansSet = set()
count = 0

for i in a:
    k = i
    kSet = set()
    while k != 1:
        if D[k] in ansSet:
            if not(D[k] in kSet):
                count = 1
                break
        else:
            ansSet.add(D[k])
            kSet.add(D[k])
        k = k // D[k]

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

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
A=list(map(int,input().split()))
flag=0
if np.gcd.reduce(A)!=1:
  flag=1
  print("not comprime")
if flag=0:
  flag1=0
  for i in range (N):
    for j in range (N):
      if i!=j and np.gcd(A[i],A[j])!=1:
        flag1=1
      if flag1:
        break
    if flag1:
      break
if flag==0 and flag1==0:
  print("pairwise coprime")
elif flag==0:
  print("setwise coprime")

Submission status: Runtime Error

Solution code:
import math
import collections
import copy

n = int(input())

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




beforeQ = collections.deque([i for i in range(2,10**6 + 1)])
D = dict()
p = 2
D[2] = 2
D[1] = 1

while p < math.sqrt(10**6):
    afterQ = collections.deque()
    while len(beforeQ) > 0:        
        k = beforeQ.popleft()
        if k % p != 0:
            afterQ.append(k)
        else:
            D[k] = p
    beforeQ = copy.copy(afterQ)
    p = beforeQ.popleft()
    D[p] = p
    

ansSet = set()
ansDict = dict()
count = 0

for i in a:
    k = i
    kSet = set()
    while k != 1:
        if D[k] in ansSet:
            if not(D[k] in kSet):
                ansDict[D[k]] += 1
                kSet.add(D[k])
                if ansDict[D[k]] > count:
                    count = ansDict[D[k]]
        else:
            ansSet.add(D[k])
            kSet.add(D[k])
            ansDict[D[k]] = 1
        k = k // D[k]

if count == 0:
    print("pairwise coprime")
elif count == len(a):
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Runtime Error

Solution code:
import math
import fractions

def get_prime(number):
    prime_list = []
    search_list = list(range(2,number + 1))
    i = 0
    while search_list[i] <= math.sqrt(number):
        head_num = search_list[i]
        search_list = [(num if num % head_num != 0 else head_num) for num in search_list]
        i += 1
    return search_list

def factrization_prime(number,D):
    factor = set()
    p = 1
    while(number != 1):
        old_p = p
        p = D[number-2]
        number = number // p
        if p != old_p:
            factor.add(p)
    return factor

N = int(input())
a = list(map(int,input().split()))
D = get_prime(max(a))
fact_p_set = set()
fact_p_set_old = set()
valid = 1
for i in range(N):
    fact_p_set_old = fact_p_set
    fact_p_set_new = factrization_prime(a[i],D)
    fact_p_set = fact_p_set.union(fact_p_set_new)
    if len(fact_p_set_old) + len(fact_p_set_new) != len(fact_p_set):
        valid = 0
        break

ans = a[0]
for i in range(1, N):
    ans = fractions.gcd(ans, a[i])

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

Submission status: Runtime Error

Solution code:
import math
import fractions

def get_prime(number):
    prime_list = []
    search_list = list(range(2,number + 1))
    i = 0
    while search_list[i] <= math.sqrt(number):
        head_num = search_list[i]
        search_list = [(num if num % head_num != 0 else head_num) for num in search_list]
        i += 1
    return search_list

def factrization_prime(number,D):
    factor = []
    p = 1
    while(number != 1):
        old_p = p
        p = D[number-2]
        number = number // p
        if p != old_p:
            factor.append(p)
    return factor

N = int(input())
a = list(map(int,input().split()))
D = get_prime(max(a))
fact_p_list = []
valid = 1
for i in range(N):
    fact_p_list += factrization_prime(a[i],D)
    if len(fact_p_list) != len(set(fact_p_list)):
        valid = 0
        break

ans = a[0]
for i in range(1, N):
    ans = fractions.gcd(ans, a[i])

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

Submission status: Runtime Error

Solution code:
import math
import fractions

def get_prime(number):
    prime_list = []
    search_list = list(range(2,number + 1))
    i = 0
    while search_list[i] <= math.sqrt(number):
        head_num = search_list[i]
        search_list = [(num if num % head_num != 0 else head_num) for num in search_list]
        i += 1
    return search_list

def factrization_prime(number,D):
    factor = []
    p = 1
    while(number != 1):
        old_p = p
        p = D[number-2]
        number = number // p
        if p != old_p:
            factor.append(p)
    return factor

N = int(input())
a = list(map(int,input().split()))
D = get_prime(max(a))
fact_p_list = []
for i in range(N):
    fact_p_list += factrization_prime(a[i],D)

ans = a[0]
for i in range(1, N):
    ans = fractions.gcd(ans, a[i])

if len(fact_p_list) == len(set(fact_p_list)):
    print("pairwise coprime")
elif ans == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import math
import fractions

def get_prime(number):
    prime_list = []
    search_list = list(range(2,number + 1))
    i = 0
    while search_list[i] <= math.sqrt(number):
        head_num = search_list[i]
        search_list = [(num if num % head_num != 0 else head_num) for num in search_list]
        i += 1
    return search_list

def factrization_prime(number,D):
    factor = []
    p = 1
    while(number != 1):
        old_p = p
        p = D[number-2]
        number = number // p
        if p != old_p:
            factor.append(p)
    return factor

N = int(input())
a = list(map(int,input().split()))
D = get_prime(max(a))
fact_p_list = []
for i in range(N):
    fact_p_list += factrization_prime(a[i],D)

ans = a[0]
for i in range(1, N):
    ans = fractions.gcd(ans, a[i])

if len(fact_p_list) == len(set(fact_p_list)):
    print("pairwise coprime")
else if ans == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import numpy as np
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = np.sqrt(num)

    for serial in range(3, num, 2):
    
        if serial > sqrt:
            return input_list

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

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

D = getD(max(A))

flag = True

d_set = set()
for a in A:
    while a > 1:
        d = D[a]
        if d in d_set:
            flag = False
            break
        d_set.add(d)
        while a > 1 & a % d == 0:
            a = a // d

    if not(flag):
        break


if flag:
    print('pairwise coprime')
    exit()

if reduce(math.gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
import numpy as np
import math
from functools import reduce

def getD(num):
    input_list = [2 if i % 2 == 0 else i for i in range(num+1)]
    bool_list = [False if i % 2 == 0 else True for i in range(num+1)]
    sqrt = np.sqrt(num)

    for serial in range(3, num, 2):
    
        if serial >= sqrt:
            return input_list

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

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

D = getD(max(A))

flag = True

d_set = set()
for i, a in enumerate(A):
    while a > 1:
        d = D[a]
        if d in d_set:
            flag = False
            break
        d_set.add(d)
        while a > 1 & a % d == 0:
            a = a // d

if flag:
    print('pairwise coprime')
    exit()

if reduce(math.gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')