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:
N = int(input())
A = [int(x) for x in input().split()]

# M以下の整数の素因数分解を高速に
# 前処理O(MloglogM)
# 一計算O(logK)
def mae_syori(M):
    D = [0] * (M + 1)
    for i in range(2, M+1):
        if D[i] != 0: continue
    #     print(i, list(range(i*2, M + 1, i)))
        for j in range(i*2, M+1, i):
            if D[j] == 0:
                D[j] = i
    return D

def p_bunkai(K):
    assert 2 <= K <= len(D)-1
    k = K
    ret = []
    while True:
        if k == 1:
            break
        if D[k] == 0:
            ret.append((k, 1))
            break
        else:
            p = D[k]
            count = 0
            while k % p == 0:
                count += 1
                k //= p
            ret.append((p, count))
    return ret
 

# 最大公約数
# ユークリッドの互除法
def my_gcd(a, b):
    if b == 0:
        return a
    else:
        return my_gcd(b, a%b)

c_gcd = A[0]
for a in A:
    c_gcd = my_gcd(c_gcd, a)

if c_gcd == 1:
    max_A = max(A)
    D = mae_syori(max_A)
    yakusu = set()
    ok = True
    for a in A:
        p_bunkai_result = p_bunkai(a)
        p_list = [p[0] for p in p_bunkai_result]
        for p in p_list:
            if p not in yakusu:
                yakusu.add(p)
            else:
                ok = False
        if not ok:
            break
    if ok:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
def gcd(a,b): 
      
    # Everything divides 0  
    if (a == 0): 
        return b 
    if (b == 0): 
        return a 
  
    # base case 
    if (a == b): 
        return a 
  
    # a is greater 
    if (a > b): 
        return gcd(a-b, b) 
    return gcd(a, b-a) 

n = int(input())
a = list(map(int, input().split()))
g = a[0]
f = 0
for i in range(1, n):
    g = gcd(g, a[i])
    if g!=1:
        f = 1
if g!=1:
    print("not coprime")
elif f:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()) )
import math

se = A[0]
for i in range(1,N):
    se = math.gcd(se,A[i])
set_wise = se==1

NMAX = 10**6+2
divisors = [i for i in range(NMAX+1)]
p=2
while p*p <=NMAX:
    if divisors[p]==p:
        for r in range(2*p,NMAX+1,p):
            if divisors[r]==r:
                divisors[r]=p
    p+=1
    
from collections import defaultdict
def soinsu_osak(to_devide):
    d = defaultdict(int)
    while to_devide>1:
        d[divisors[to_devide]]+=1
        to_devide //= divisors[to_devide]
    return list(d.keys())

been=[0]*NMAX
f=False
for aa in A:
    soinsu = soinsu_osak(aa)
    for s in soinsu:
        if been[s]==0:
            been[s]=1
        else:
            pair_wise=False
            f=True
            break
    if f:
        break

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
def main():
    from math import gcd

    N = int(input())
    A = []
    INF = 10 ** 6
    frequency = [0] * INF
    for a in [int(x) for x in input().split()]:
        A.append(a)
        frequency[a] += 1
    
    pairwise = True
    for i in range(2, INF):
        cnt = 0
        for j in range(i, INF, i):
            cnt += frequency[j]
        if cnt > 1:
            pairwise = False
    if pairwise:
        print("pairwise coprime")
        return

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import defaultdict
import sys

read = sys.stdin.buffer.read
INF = 10 ** 6 + 1
is_prime = [1] * INF

def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return

def f(n):
    yakusu = []
    if is_prime[n]:
        yakusu.append(n)
    else:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                yakusu.append(i)
                if i != n //i:
                    yakusu.append(n // i)
                break

    for i in yakusu:
        if i != 1:
            d[i] += 1


eratorasu()
d = defaultdict(int)
N = int(input())
A = np.array(read().split(), np.int64)[1:]

for i in range(N):
    f(A[i])

cnt = 1
for i, v in d.items():
    if v != 1:
        cnt = max(cnt, v)

if cnt == N:
    print('not coprime')
elif cnt == 1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
                                                                                              M = max(a)
biggest_prime = [0] * (M+10)
for i in range(2, M+10):
    if biggest_prime[i] == 0:
        biggest_prime[i] = i
        for j in range(i*i, M+1, i):
            biggest_prime[j] = i

from collections import defaultdict
cntd=defaultdict(int)
for i in range(len(a)):
    num = a[i]
    while num>1:
        p=biggest_prime[num]
        cntd[p]+=1
        while num % p == 0:
            num//=p

flg=False
for c in cntd.values():
    if c==n:
        print("not coprime")
        exit()
    if c>1:
        flg=True
if flg:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import math

def sieve_of_erastosthenes(num):
    print(num)
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num+1)]
    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

N = int(input())
A = [int(i) for i in input().split()]
ans = math.gcd(A[0], A[1])
tmp = math.gcd(A[0], A[1])
for i in range(2, N):
    ans = math.gcd(ans, A[i])
if ans > 1:
    print('not coprime')
    exit()
maxA = max(A)
l = sieve_of_erastosthenes(maxA)
B = [False for i in range(maxA+1)]
for i in range(N):
    B[A[i]] = True
flag = False
for i in range(len(l)):
    # 素数の時
    if l[i]:
        tmp = i
        counter = 0
        while True:

            if B[tmp]:
                counter += 1
            tmp += i
            if tmp > maxA:
                break
        if counter > 1:
            flag = True
            break


if flag:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
from math import gcd
from functools import reduce
from sys import exit

# O(A+N)解
MAX_A = 1000000
lowerst_prime = [0] * (MAX_A + 1) # 最小の素因数をいれる(2以上をみていけばいい)
primes = [] # MAX_A以下の素数の集合
count = [0] * (MAX_A + 1) # 約数として出てくる回数を数える
for i in range(2, MAX_A + 1): # 線形時間で処理してくれる
    if lowerst_prime[i] == 0:
        continue
    lowerst_prime[i] = i
    for p in primes:
        if i * p > MAX_A:
            break
        lowerst_prime[i * p] = p # p がi * p のもっとも小さな素因数となるときのみ更新されるので、線形時間アルゴリズムとなる
# 入力
N = int(input())
A = [*map(int, input().split())]
if reduce(gcd, A) != 1:
    print("not coprime")
    exit(0)
for i in range(N):
    while A[i] > 1:
        divide = lowerst_prime[A[i]]
        if count[divide]:
            # A[x] % i == A[y] % i == 0 となるx != yが存在するので、i | gcd(x, y)となる
            print("setwise coprime")
            exit(0)
        count[divide] += 1
        while A[i] % divide == 0: # 割れるだけ割る
            A[i] //= divide
print("pairwise coprime")

Submission status: Runtime Error

Solution code:
from math import gcd
from functools import reduce

M = 10 ** 6
ret = [0] * M
n = int(input())
nums = list(map(int, input().split()))
flag = 1
for i in nums:
    ret[i] += 1
for i in range(2, M):
    if sum(ret[i::i]) > 1:
        flag = 0
        break
if flag:
    print("pairwise coprime")
elif reduce(gcd, nums) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A_MAX = max(A)

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]]

primecount = {}
primenum = [-1] * (A_MAX+1)
for p in eratosthenes(A_MAX):
    primecount[p] = 0
    for i in range(p, A_MAX+1, p):
        primenum[i] = p
    
for a in A:
    while a > 1:
        p = primenum[a]
        while a % p == 0:
            a //= p
        primecount[p] += 1

cnt = max(primecount.values())
if cnt == 1:    
    print('pairwise coprime')
elif cnt < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* clang-format off */
#define MOD 1000000007
#define INF 1000000000
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
#define __DEBUG__
#ifdef __DEBUG__
#define CH_P(a) cout <<"check_point("<<#a<<")" << "\n";
#define DEBUG(x) cout<<#x<<":"<<x<<"\n"
#define DEBUGS(v) cout << #v << ":";for(auto x:v){cout<<x<<" ";}cout<<"\n"
#endif
#ifndef __DEBUG__
#define CH_P(a) 
#define DEBUG(x) 
#define DEBUGS(v) 
#endif
/* clang-format on */

void is_prime_cal(ll n, vector<bool> &is_prime) {
  // nまでの素数を生成
  // vector<bool> is_prime(n + 1, true);
  vector<bool> tmp(n + 1, true);
  is_prime = tmp;
  for (ll i = 0; i <= n; i++) {
    if (!is_prime.at(i)) continue;
    if (i == 0 || i == 1) is_prime.at(i) = false;
    if (is_prime.at(i)) {
      for (ll j = 2; j * i <= n; j++) {
        is_prime.at(j * i) = false;
      }
    }
  }
}

void prime_gen(ll n, vector<ll> &prime) {
  // nまでの素数を生成
  vector<bool> is_prime(n + 1, true);
  for (ll i = 0; i <= n; i++) {
    if (!is_prime.at(i)) continue;
    if (i == 0 || i == 1) is_prime.at(i) = false;
    if (is_prime.at(i)) {
      for (ll j = 2; j * i <= n; j++) {
        is_prime.at(j * i) = false;
      }
    }
  }
  REP(i, n + 1) {
    if (is_prime[i]) prime.push_back(i);
  }
}

void factorization(ll n, vector<bool> is_prime, set<ll> &f) {
  // 準備:is_prime_genでis_primeを生成しておく
  // factor[i].first = i番目の素数
  // factor[i].second = 指数
  vector<ll> prime;

  ll check_num = (ll)(sqrt(n));
  REP(i, check_num + 1) {
    if (is_prime.at(i)) prime.push_back(i);
  }
  for (auto &p : prime) {
    if (n % p == 0) f.insert(p);
    while (n % p == 0) n /= p;
    if (n == 1) break;
  }
  if (n != 1) {
    f.insert(n);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll n;
  cin >> n;
  vector<ll> a(n);
  REP(i, n) { cin >> a[i]; }

  ll g = a[0];
  REP(i, n) { g = gcd(g, a[i]); }
  if (g != 1) {
    cout << "not coprime" << endl;
    return 0;
  }

  set<ll> fac;
  vector<bool> is_prime;
  is_prime_cal(sqrt(*max_element(ALL(a))), is_prime);
  bool fp = true;
  REP(i, n) {
    set<ll> f;
    factorization(a[i], is_prime, f);
    for (auto x : f) {
      if (fac.count(x)) {
        fp = false;
        break;
      }
      fac.insert(x);
    }
    if (!fp) break;
  }

  if (fp)
    cout << "pairwise coprime" << endl;
  else
    cout << "setwise coprime\n";

  return 0;
}

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <array>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <climits>
#include <utility>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <complex>
#include <numeric>
#include <chrono>
#include <cmath>
#include <bitset>

using namespace std;

#define FOR(it, ar) for(auto &it: ar)
#define loop(i, start, end) for(auto i = (start); i <= (end); i++)
#define loopSkip(i, start, end, skip) for(auto i = (start); i <= (end); i += skip)
#define loopRev(i, start, end) for(int i = (start); i >= (end); i--)
#define FLASH ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define testCases(t) cin >> t; while(t--)
#define PN(n) cout << (n)
#define PN1(n) cout << (n) << " "
#define PN2(a, b) cout << (a) << " " << (b) << " "
#define PN3(a, b, c) cout << (a) << " " << (b) << " " << (c) << " "
#define PNN1(n) cout << (n) << "\n"
#define PNN2(a, b) cout << (a) << " " << (b) << "\n"
#define PNN3(a, b, c) cout << (a) << " " << (b) << " " << (c) << "\n"
#define PrintObject(ar) for(auto var: ar) cout << var << " "; cout << "\n"
#define PrintMap(map) for(auto var: map) PNN2(var.first, var.second)
#define PrintPair(pair) PNN2(pair.first, pair.second)
#define IN1(n) cin >> n
#define IN2(a, b) cin >> a >> b
#define IN3(a, b, c) cin >> a >> b >> c
#define ALL(s) s.begin(), s.end()
#define ENTER PNN1("")
#define llPair std::pair<lli, lli>
#define iiPair std::pair<int, int>

// Math macros
#define M_PI 3.14159265358979323846

typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ld;

template <typename T>
T ii() {
	T a;
	IN1(a);
	return a;
}

struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
      // http://xorshift.di.unimi.it/splitmix64.c
      x += 0x9e3779b97f4a7c15;
      x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
      x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
      return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
      static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
      return splitmix64(x + FIXED_RANDOM);
  }
};

lli gcd(lli a, lli b) {
	return b == 0 ? a : gcd(b, a % b);
}

lli lcm(lli a, lli b) {
	return a * b / gcd(a, b);
}

int main(void){
	FLASH
	#ifndef ONLINE_JUDGE
		freopen("input-stream.txt", "r", stdin);
		freopen("output-stream.txt", "w", stdout);
	#endif

	int n;
	IN1(n);
	vector<lli> ar(n);
	FOR(it, ar) IN1(it);

	lli l = 1, g = 0, mul = 1;
	FOR(it, ar) {
		l = lcm(l, it);
		g = gcd(g, it);
		mul *= it;
	}

	PNN1(l == mul ? "pairwise coprime" : g == 1 ? "setwise coprime" : "not coprime");


	return 0;
}

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <array>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <climits>
#include <utility>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <complex>
#include <numeric>
#include <chrono>
#include <cmath>
#include <bitset>

using namespace std;

#define FOR(it, ar) for(auto &it: ar)
#define loop(i, start, end) for(auto i = (start); i <= (end); i++)
#define loopSkip(i, start, end, skip) for(auto i = (start); i <= (end); i += skip)
#define loopRev(i, start, end) for(int i = (start); i >= (end); i--)
#define FLASH ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define testCases(t) cin >> t; while(t--)
#define PN(n) cout << (n)
#define PN1(n) cout << (n) << " "
#define PN2(a, b) cout << (a) << " " << (b) << " "
#define PN3(a, b, c) cout << (a) << " " << (b) << " " << (c) << " "
#define PNN1(n) cout << (n) << "\n"
#define PNN2(a, b) cout << (a) << " " << (b) << "\n"
#define PNN3(a, b, c) cout << (a) << " " << (b) << " " << (c) << "\n"
#define PrintObject(ar) for(auto var: ar) cout << var << " "; cout << "\n"
#define PrintMap(map) for(auto var: map) PNN2(var.first, var.second)
#define PrintPair(pair) PNN2(pair.first, pair.second)
#define IN1(n) cin >> n
#define IN2(a, b) cin >> a >> b
#define IN3(a, b, c) cin >> a >> b >> c
#define ALL(s) s.begin(), s.end()
#define ENTER PNN1("")
#define llPair std::pair<lli, lli>
#define iiPair std::pair<int, int>

// Math macros
#define M_PI 3.14159265358979323846

typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ld;

template <typename T>
T ii() {
	T a;
	IN1(a);
	return a;
}

struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
      // http://xorshift.di.unimi.it/splitmix64.c
      x += 0x9e3779b97f4a7c15;
      x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
      x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
      return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
      static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
      return splitmix64(x + FIXED_RANDOM);
  }
};

lli gcd(lli a, lli b) {
	return b == 0 ? a : gcd(b, a % b);
}

lli lcm(lli a, lli b) {
	return a * b / gcd(a, b);
}

int main(void){
	FLASH
	#ifndef ONLINE_JUDGE
		freopen("input-stream.txt", "r", stdin);
		freopen("output-stream.txt", "w", stdout);
	#endif

	int n;
	IN1(n);
	vector<lli> ar(n);
	FOR(it, ar) IN1(it);

	const lli MOD = (lli) 1e9 + 7;

	lli l = 1, g = 0, mul = 1;
	FOR(it, ar) {
		l = lcm(l, it) % MOD;
		g = gcd(g, it) % MOD;
		mul = mul * it % MOD;
	}

	PNN1(l == mul ? "pairwise coprime" : g == 1 ? "setwise coprime" : "not coprime");


	return 0;
}

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline


class Osak:
    def __init__(self, max_number=10 ** 6):
        self.max_number = max_number
        self.table = list(range(max_number + 1))
        self.calc_minimum_prime()

    def calc_minimum_prime(self):
        self.table[1] = 0
        for base in range(2, self.max_number + 1):
            if self.table[base] != base:
                continue
            for num in range(base, self.max_number+1, base):
                self.table[num] = base

    def judge_is_prime(self, num):
        return self.table[num] == num

    def get_factors(self, num):
        factors = set()
        while num > 1:
            prime = self.table[num]
            factors.add(prime)
            num //= prime
        return factors

    def factorize(self, num):
        factors = defaultdict(int)
        while num > 1:
            prime = self.table[num]
            factors[prime] += 1
            num //= prime
        return factors


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

    osak = Osak(max(A))
    prime_count = defaultdict(int)
    for a in A:
        factors = osak.get_factors(a)
        for factor in factors:
            prime_count[factor] += 1

    ans = max(prime_count.values())

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
pc="pairwise coprime"
sc="setwise coprime"
nc="not coprime"
a.sort()
tmp=a[0]

for i in range(n):
    tmp=math.gcd(tmp,a[i])
if tmp!=1:
    print(nc)
    exit()

dic=defaultdict(int)
for i in range(n):dic[a[i]]+=1

ans=0
for i in range(a[-1]):
    now=i+1
    cnt=0
    # print(i)
    while now<=a[-1]:
        cnt+=dic[a[i]]
        now+=i+1
    if cnt>1:
        ans=i+1

if ans!=1:
    print(sc)
else:
    print(pc)
# print(ans)

Submission status: Runtime Error

Solution code:
#coding: utf-8

from collections import defaultdict
from functools import reduce
from math import gcd
import sys

N = int(input())
maxA = 0
A = []
for a in (int(x) for x in input().split()):
    if a > maxA:
        maxA = a
    A.append(a)

D = [0] * (maxA + 1)
i = 2
primes = [2]
for i in range(2, maxA+1):
    for p in primes:
        if p * p > i:
            break
        if i % p == 0:
            D[i] = p
            break
    if D[i] == 0:
        primes.append(i)
        D[i] = i

def primeFac(N):
    ret = set()
    i = 2
    while N >= 2:
        ret.add(D[N])
        N //= D[N]
    return ret

numDiv = defaultdict(int) 
for a in A:
    for f in primeFac(a):
        numDiv[f] += 1
if max(numDiv.values()) == 1:
    print("pairwise coprime")
else:
    if (reduce(gcd, A) == 1):
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Runtime Error

Solution code:
n = int(input())
*A, = map(int, input().split())
m = max(A)
C = [0 for a in range(m + 1)]
for a in A:
    C[a] += 1
s = max(sum(C[a::a]) for a in range(2, m + 1))
if s < 2:
    print('pairwise coprime')
elif s < n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>

template<uint32_t N = 10'000'000>
struct Sieve_of_Eratosthenes{
  using u32 = uint32_t;
  std::vector<u32> factor;
  Sieve_of_Eratosthenes(){
    factor.resize(N+1);
    for(u32 p=2;p<=N;++p){
      if(factor[p])continue;
      factor[p] = p;
      for(u32 x=p+p;x<=N;x+=p){
        if(factor[x])continue;
        factor[x] = p;
      }
    }
  }
  std::vector<u32> prime_factor(u32 x){
    std::vector<u32> pf;
    while(factor[x]){
      pf.push_back(factor[x]);
      while(factor[x]==pf.back())x/=factor[x];
    }
    return pf;
  }
};

signed main(){
  using namespace std;
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin>>n;
  vector<int> a(n);
  for(auto& ai:a)cin>>ai;

  constexpr int a_max = 1e6;
  Sieve_of_Eratosthenes ushi;

  map<int,int> mp;
  bool pairwise_coprime = true;
  bool setwise_coprime = accumulate(begin(a),end(a),0,[](auto a,auto b){return gcd(a,b);}) == 1;

  for(auto const& ai:a){
    for(auto const& p:ushi.prime_factor(ai)){
      if(mp.count(p)){
        pairwise_coprime = false;
        goto loopend;
      }
      mp[p]++;
    }
  }
loopend:

  if(pairwise_coprime){
    cout<<"pairwise coprime"<<endl;
  }
  else if(setwise_coprime){
    cout<<"setwise coprime"<<endl;
  }
  else{
    cout<<"not coprime"<<endl;
  }


}

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A_list = list(map(int, input().split()))

    maxa = max(A_list)
    lim = maxa

    primes_table = [True] * lim
    primes_table[0] = primes_table[1] = False
    primes = set()
    for i in range(2,lim):
        if primes_table[i] == False:
            continue
        primes.add(i)
        for j in range(i+i, lim, i):
            primes_table[j] = False

    a_set = [set()] * N
    pr_dict = {r: set() for r in primes}
    for a in A_list:
        for p in primes:
            if a%p== 0:
                pr_dict[p].add(a) 
                
    maxlen = 0
    for d in pr_dict.values():
        maxlen=max(maxlen, len(d))

    if maxlen == 1:
        print("pairwise coprime")
    elif maxlen < N:
        print("setwise coprime")
    else:
        print("not coprime")
if __name__ == "__main__":
    main()

Submission status: Runtime Error

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


class Prime:
    @staticmethod
    def trial_division(x):
        if x % 2 == 0:
            return True
        for p in range(3, int(x**0.5 + 1), 2):
            if x % p == 0:
                return False
        return True

    @staticmethod
    def factorization(x):
        ret = {}
        i = 0
        while True:
            if x % 2:
                break
            x //= 2
            i += 1
        if i:
            ret[2] = i
        for p in range(3, int(x**0.5 + 1), 2):
            i = 0
            while True:
                if x % p:
                    if i:
                        ret[p] = i
                    break
                x //= p
                i += 1
        if x > 1:
            ret[x] = 1
        return ret

    @staticmethod
    def miller_rabin(n):
        def suspect(a, t, n):
            x = pow(a, t, n)
            n1 = n - 1
            while t != n1 and x != 1 and x != n1:
                x = pow(x, 2, n)
                t <<= 1
            return t & 1 or x == n1

        if n == 2:
            return True
        if n < 2 or n % 2 == 0:
            return False
        d = (n - 1) >> 1
        while d & 1 == 0:
            d >>= 1

        if n < 2**32:
            check_list = (2, 7, 61)
        elif n < 2**48:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23)
        else:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)

        for i in check_list:
            if i >= n:
                break
            if not suspect(i, d, n):
                return False
        return True


c = collections.defaultdict(int)
for a in A:
    for p in Prime.factorization(a):
        c[p] += 1
x = max(c.values())
if x == 1:
    print('pairwise coprime')
elif x == N:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Runtime Error

Solution code:
import math

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

soinsuu = []

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(1, n)]
    super_erasuto = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return super_erasuto
        prime.append(p)
        super_erasuto =  [p if e % p == 0 else e for e in super_erasuto]
        data = [e for e in data if e % p != 0]

data = get_sieve_of_eratosthenes(max(a))
data.insert(0, 1)
data.insert(0, 0)

for i in a:
  soinsuu.append(data[i])

if len(set(soinsuu)) == len(soinsuu):
  ans = "pairwise coprime "
else:
  ans = "setwise coprime"  
  
  gcd = a[n-1]
  for i in range(len(a)-1):
    gcd = math.gcd(a[i],gcd)
  if gcd != 1:
    ans = "not coprime"
  
print(ans)

Submission status: Runtime Error

Solution code:
#coding: utf-8

from collections import defaultdict
from functools import reduce
from math import gcd
import sys

N = int(input())
maxA = 0
A = []
for a in (int(x) for x in input().split()):
    if a > maxA:
        maxA = a
    A.append(a)

D = [0] * (maxA + 1)
i = 2
primes = [2]
for i in range(2, maxA+1):
    for p in primes:
        if i % p == 0:
            D[i] = p
            break
    if D[i] == 0:
        primes.append(i)
        D[i] = i

def primeFac(N):
    ret = set()
    i = 2
    while N >= 2:
        ret.add(D[N])
        N //= D[N]
    return ret

numDiv = defaultdict(int) 
for a in A:
    for f in primeFac(a):
        numDiv[f] += 1
#print(numDiv, max(numDiv))
if max(numDiv.values()) == 1:
    print("pairwise coprime")
else:
    if (reduce(gcd, A) == 1):
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Runtime Error

Solution code:
#coding: utf-8

from collections import defaultdict
from functools import reduce
from math import gcd
import sys

N = int(input())
maxA = 0
A = []
for a in (int(x) for x in input().split()):
    if a > maxA:
        maxA = a
    A.append(a)

D = [0] * (maxA + 1)
i = 2
primes = [2]
for i in range(2, maxA+1):
    for p in primes:
        if i % p == 0:
            D[i] = p
            break
    if D[i] == 0:
        primes.append(i)
        D[i] = i

def primeFac(N):
    ret = set()
    i = 2
    while N != 1:
        ret.add(D[N])
        N //= D[N]
    return ret

numDiv = defaultdict(int) 
for a in A:
    for f in primeFac(a):
        numDiv[f] += 1
#print(numDiv, max(numDiv))
if max(numDiv.values()) == 1:
    print("pairwise coprime")
else:
    if (reduce(gcd, A) == 1):
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Runtime Error

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N=I()
  A=LI()
  
  l=[0]*1000100
  pairwise=True
  for i in range(2,1000100):
    cnt=0
    for j in range(i+1,1000100):
      cnt+=A[j]
    if cnt>1:
      pairwise=False

  if pairwise:
    return 'pairwise coprime'

  f1=True
  f2=False
  for x in l:
    if x>1:
      f1=False

  if f1:
    return 'pairwise coprime'

  g=0
  for x in A:
    g=math.gcd(g,x)

  if g==1:
    return 'setwise coprime'

  return 'not coprime'

# main()
print(main())

Submission status: Runtime Error

Solution code:
def main():
    import math
    n = int(input())
    a = sorted(list(map(int,input().split())))
    d = [-1 for i in range(a[-1])]
    d[0] = 1
    for i in range(2,a[-1]):
        for j in range(1,a[-1]//i+1):
            if d[i*j-1] == -1:
                d[i*j-1] = i
    Dic = [0 for i in range(a[-1])]
    flg = 0
    for i in range(n):
        if Dic[d[a[i]-1]] != 0:
            flg = 1
            break
        else:
            Dic[d[a[i]-1]] += 1
    g=a[0]
    for i in range(1,n):
        g = math.gcd(g,a[i])
    if g > 1:
        print('not coprime')
        return
    if flg == 1:
        print('setwise coprime')
        return
    print('pairwise coprime')

if __name__ == "__main__":
    main()