# 【題解】AtCoder ABC 177E – Coprime

#include <iostream>
#include <set>
using namespace std;

const int maxn = 1000005;
int n, a, prime[maxn];
set <int> st, st2, tmp;

int main() {
cin >> n;
for (int i = 2; i < maxn; i++){
if (!prime[i]){
for (int j = i; j < maxn; j += i){
prime[j] = i;
}
}
}
cin >> a;
while (prime[a]){
st.insert(prime[a]);
int x = prime[a];
while (a % x == 0) a /= x;
}
st2 = st;
bool pairwise = true;
for (int i = 1; i < n; i++){
cin >> a;
tmp.clear();
for (auto j:st2){
if (a % j == 0) tmp.insert(j);
}
st2 = tmp;
if (pairwise){
while (prime[a]){
if (st.count(prime[a])) pairwise = false;
st.insert(prime[a]);
int x = prime[a];
while (a % x == 0) a /= x;
}
}
}
if (pairwise) cout << "pairwise coprime\n";
else if (!st2.size()) cout << "setwise coprime\n";
else cout << "not coprime\n";
}

Python code (credit: Amy Chou, 9/5/2020)

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

maxn =  1000005
prime = [0 for _ in range(maxn)]

for i in range(2, maxn):
if prime[i] == 0:
for j in range(i, maxn, i):
prime[j] = i #最大質因數

st = set() #目前出現過的所有質因數，一開始為A[0]的所有質因數
a = A[0]
while prime[a]:
x = prime[a]
while (a % x == 0):
a //= x

pairwise = True
st2 = st #所有數共有的質因數，一開始為A[0]的所有質因數
for a in A[1:]:
tmp = set()
for j in st2:
if a % j == 0:

st2 = tmp
if pairwise:
while prime[a]:
if prime[a] in st:
pairwise = False