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:
from math import sqrt
from collections import Counter

def factorize(n):
    rt = int(sqrt(n)+1)
    facts = []
    for i in range(2, rt+1):
        if n % i == 0:
            facts.append(i)
            while n % i == 0:
                n //= i
    if n != 1:
        facts.append(n)
    return facts

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

P = Counter()
6 
for a in A:
    p = Counter(factorize(a))
    P += p
p_max = max(P.values())
if  p_max == 1:
    print('pairwise coprime')
elif  p_max <  n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
import math
m=int(input())
a,b,c=map(int,input().split())
a1=math.gcd(a,b)
a2=math.gcd(a,c)
a3=math.gcd(b,c)
if a1==1 and a2==1 and a3==1:
    print("pairwise coprime")
elif a1==2 and a2==2 and a3==2:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = LIST()
lim = 10#**6+1
g = [[] for _ in range(lim+1)]
g[1].append(1)
for i in range(2, lim+1):
	if g[i] == []:
		for j in range(1, lim//i + 1):
			g[i*j].append(i)

num = [0]*(lim+1)

for a in A:
	for x in g[a]:
		if num[x]:
			break
		num[x] = 1

	else:
		continue
	break
else:
	print("pairwise coprime")
	exit()


#素因数分解
def factorization(n):
	arr = []
	tmp = n
	for i in range(2, int(-(-n**0.5//1))+1):
		if tmp%i == 0:
			cnt = 0
			while tmp%i == 0:
				cnt += 1
				tmp //= i
			arr.append([i, cnt])
	if tmp != 1:
		arr.append([tmp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr
	
dic = defaultdict(int)
for x, y in factorization(A[0]):
	dic[x]=y

for a in A[1:]:
	for x, y in dic.items():
		if a%x:
			dic[x] = 0
		else:
			dic[x] = min(y, a//x)

for x, y in dic.items():
	if x != 1 and y != 0:
		print("not coprime")
		break
else:
	print("setwise coprime")

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
lim = 200000
inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def COMinit(max=lim, mod=MOD):
    factrial[0] = factrial_inv[0] = 1
    factrial[1] = factrial_inv[1] = 1
    inv_t[0] = inv_t[1] = 1
    for i in range(2, max):
        factrial[i] = factrial[i-1]*i % mod
        inv_t[i] = -inv_t[mod % i]*(mod//i) % mod
        factrial_inv[i] = factrial_inv[i-1]*inv_t[i] % mod


def comb(a, b, mod=MOD):
    if a < b:
        return 0
    if factrial[0] == -1:
        COMinit()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % mod


def prime_factor(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr


n = int(input())
a = [int(_) for _ in input().split()]
p = [2]

for i in range(3, 10**3+100):
    for P in p:
        if i % P == 0:
            break
    else:
        p.append(i)

dic = {}
for P in p:
    dic[P] = 0

for i in range(n):
    if a[i] == 1:
        print("pairwise coprime")
        exit(0)
    temp = a[i]
    f = True
    for P in p:
        if temp % P == 0:
            dic[P] += 1
            f = False
            while temp % P == 0:
                temp //= P
        if temp == 1:
            break
    if temp != 1:
        if temp in dic.values():
            dic[temp] += 1
        else:
            dic[P] = 1
# print(ans[0:10])

ans = dic.values()
# print(ans)

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

Submission status: Runtime Error

Solution code:
import math
def main():

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

    A = [v for v in A if v != 1]
    if len(set(A)) < len(A): return "not coprime"
    A = list(set(A))

    def eratosthenes(limit):
        B = [i for i in range(2, limit+1)]
        primes = []
        while True:
            prime = min(B)
            if prime > math.sqrt(limit):
                break
            primes.append(prime)
            i = 0
            while i < len(B):
                if B[i] % prime == 0:
                    B.pop(i)
                    continue
                i += 1
        for a in B:
            primes.append(a)
        return primes

    primes = eratosthenes(max(A))

    d = dict()
    ispair = True
    isset = True

    for v in A:
        for p in primes:
            if p <= v:
                if v % p == 0:
                    d[p] = d.get(p, 0) + 1
            else:
                break
    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"
    return "not coprime"

if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))

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


data = get_sieve_of_eratosthenes(max(a))
lst=[0]*(len(data))
for num in a:
    for i,datum in enumerate(data):
        if datum>num:
            break
        if num%datum==0:
            lst[i]+=1
            num//=datum

pair=True
st=True

for i in lst:
    if i>=2:
        pair=False
    if i==n:
        st=False

if pair:
    print("pairwise coprime")
elif st:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
from fractions import gcd
from collections import Counter

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

a = 1
result = []
for x in arr:
    y = gcd(a, x)
    result.append(y)
    a = a * x // y

if result.count(1) == len(arr):
    print("pairwise coprime")
    sys.exit()

if len(Counter(result[1:])) == 1:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Runtime Error

Solution code:
def make_divisors(n):
    divisors = []
    # 試し割りで、かつ積でnを作るときの相方も同時に追加してる
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
from math import gcd
import sys
n = int(input())
a_ls = list(map(int, input().split()))
now = a_ls[0]
for i in range(1,n):
    now = gcd(now,a_ls[i])
if now != 1:
    print('not coprime')
    sys.exit()
else:
    a_ls.sort()
    Max = a_ls[-1]
    count_in_a = [0] * (Max+1)
    for a in a_ls:
        count_in_a[a] += 1

    res = 'pairwise coprime'
    
    lim = int(Max**0.5)+2
    isdone = [0] * (Max+1)
    # baseは共通の素因数の候補
    for base in range(2,lim+1):
        if isdone[base]:
            continue
        now = base
        time_inA = 0
        while now <= Max:
            isdone[now] = 1
            if count_in_a[now] > 0:
                time_inA += count_in_a[now]
                if time_inA >= 2:
                    res = 'setwise coprime'
                    break
            now += base
    print(res)

Submission status: Runtime Error

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

import math 

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

if ans!=1:
    #print(ans)
    print("not coprime")
    exit()
else:
    checked=[0]*(int(max(a)))
    #print(checked)
    for item in a:
        for j in range(1,int(item**0.5)+1):
            if item%j==0 and j*j<=item:
                if checked[j]==0:
                    if j!=1:
                        checked[j]+=1
                        if checked[item//j]==0:
                            checked[item//j]+=1
                        else:
                            #print(item,j,checked)
                            print("setwise coprime")
                            exit() 
                else:
                    #print(item,j,checked)
                    print("setwise coprime")
                    exit()
print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import math

N = int(input())

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

gcdAll = A[0]
isPairwise = True

for j in range(1, N):
    gcdAll = math.gcd(gcdAll, A[j])
    if not isPairwise:
        continue
    for i in range(0, j):
        gcdNow = math.gcd(A[i], A[j])
        if gcdNow != 1:
            isPairwise = False
            break

if isPairwise:
    print('pairwise coprime')
elif gcdAll == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD=1000000007;
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
const int mmax=1000009;

int main(void){
    int n;
    cin>>n;
    vector<int> A(n);
    rep(i,n) cin>>A[i];
    vector<int> seen(mmax,-1);
    bool pairwise=true;
    rep(i,n){
        for(int j=A[i];j>1;--j){
            if(A[i]%j!=0) continue;
            if(seen[j]!=-1){
                pairwise=false;
            }
            seen[j]++;
        }
    }
    if(pairwise) puts("pairwise coprime");
    else{
        bool setwise=true;
        rep(i,mmax){
            //cout<<i<<" "<<seen[i]<<endl;
            if(seen[i]==n-1){
                setwise=false;
                //break;
            }
        }
        if(setwise) puts("setwise coprime");
        else puts("not coprime");
    }
    return 0;
}

Submission status: Runtime Error

Solution code:
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)
n=int(input())
l=list(map(int,input().split())) 
for i in range(0,n):
  t=l[i%n]
  y=l[(i+1)%n]
  s=min(t,y)
  p=max(t,y
  f=gcd(p,s)

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
lim = 200000
inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def COMinit(max=lim, mod=MOD):
    factrial[0] = factrial_inv[0] = 1
    factrial[1] = factrial_inv[1] = 1
    inv_t[0] = inv_t[1] = 1
    for i in range(2, max):
        factrial[i] = factrial[i-1]*i % mod
        inv_t[i] = -inv_t[mod % i]*(mod//i) % mod
        factrial_inv[i] = factrial_inv[i-1]*inv_t[i] % mod


def comb(a, b, mod=MOD):
    if a < b:
        return 0
    if factrial[0] == -1:
        COMinit()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % mod


def prime_factor(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr


n = int(input())
a = [int(_) for _ in input().split()]
p = [2]

for i in range(3, 10**3+100):
    for P in p:
        if i % P == 0:
            break
    else:
        p.append(i)

dic = {}
for P in p:
    dic[P] = 0

for i in range(n):
    temp = a[i]
    f = True
    for P in p:
        if temp % P == 0:
            dic[P] += 1
            f = False
            while temp % P == 0:
                temp //= P
    if temp != 1:
        if temp in dic.values():
            dic[temp] += 1
        else:
            dic[P] = 1
# print(ans[0:10])

ans = dic.values()
# print(ans)
if max(ans) == n:
    print("not coprime")
elif max(ans) == 1:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Runtime Error

Solution code:
import math

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

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

if ans!=1:
    print('not coprime')

else:
    for i in range(min(1000,n-1)):
        for k in range(i+1,min(n,1000)):
            if math.gcd(a[i],a[j])!=1:
                print('setwise coprime')
                exit()
        for j in range(max((n-1000),i+1),n):
            if math.gcd(a[i],a[j])!=1:
                print('setwise coprime')
                exit()
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
N = int(input())

if N<=10**5:
    def eratosthenes(n):
        prime = []
        limit = n**0.5
        numbers = [i for i in range(2,n+1)]
        while True:
            p = numbers[0]
            if limit <= p:
                return prime + numbers
            prime.append(p)
            numbers = [i for i in numbers if i%p != 0]
        return prime

    def prime_decomposition(n):
      i = 2
      d = {}
      while i * i <= n:
        while n % i == 0:
          n //= i
          if i not in d:
              d[i] = 0
          d[i] += 1
        i += 1
      if n > 1:
        if n not in d:
            d[n] = 1
      return d

    pl = eratosthenes(10**6)
    pd = {}
    for p in pl:
        pd[p] = 0

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

    A.sort()



    d = {}
    ans = 0
    for i in range(N):
        if A[i] not in pd:
            primes = prime_decomposition(A[i])
            for p in primes:
                if p not in d:
                    d[p] = 0
                else:
                    ans = 1
                    break
        else:
            if A[i] in d:
                ans = 1
                break
            d[A[i]] = 0

    if ans == 0:
        print('pairwise coprime')
    else:
        def gcd(a, b):
        	while b:
        		a, b = b, a % b
        	return a
        a = A[0]
        for i in range(N):
            a = gcd(a,A[i])
        if a==1:
            print('setwise coprime')
        else:
            print('not coprime')
else:
    def eratosthenes(n):
        prime = []
        limit = n**0.5
        numbers = [i for i in range(2,n+1)]
        while True:
            p = numbers[0]
            if limit <= p:
                return prime + numbers
            prime.append(p)
            numbers = [i for i in numbers if i%p != 0]
        return prime

    def prime_decomposition(n):
      i = 2
      d = {}
      while i * i <= n:
        while n % i == 0:
          n //= i
          if i not in d:
              d[i] = 0
          d[i] += 1
        i += 1
      if n > 1:
        if n not in d:
            d[n] = 1
      return d

    pl = eratosthenes(10**6)
    pd = {}
    for p in pl:
        pd[p] = 0

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


    A.sort()

    d = {}
    ans = 0
    if len(set(A)) != N:
        ans = 1
    for i in range(N):
        if A[i] in d:
            ans = 1
            break
        if A[i] not in pd:
            primes = prime_decomposition(A[i])
            for p in primes:
                if p not in d:
                    for j in range(1,(10**6)//p+1):
                        d[j*p] = 0
                else:
                    ans = 1
                    break




    if ans == 0:
        print('pairwise coprime')
    else:
        def gcd(a, b):
        	while b:
        		a, b = b, a % b
        	return a
        a = A[0]
        for i in range(N):
            a = gcd(a,A[i])
        if a==1:
            print('setwise coprime')
        else:
            print('not coprime')

Submission status: Runtime Error

Solution code:
import math
m=int(input())
a,b,c=map(int,input().split())
if math.gcd(a,b) and math.gcd(a,c) and math.gcd(b,c)==1:
    print("pairwise coprime")
elif math.gcd(a,b) and math.gcd(a,c) and math.gcd(b,c)==2:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Runtime Error

Solution code:
import sys,os
import math
from fractions import Fraction 
from collections import defaultdict
from random import randint

# sys.stderr=open('err.txt','w')
# sys.stdout=open('output.txt','w')
# sys.stdin=open('input.txt','r')

def linput():
    return list(minput())

def minput():
    return map(int, sys.stdin.readline().strip().split())

###############################################################

def gdc(a,b):
    if a==0:
        return b
    if b==0:
        return a
    if a==b:
        return a
    if a>b:
        return gdc(a-b,b)
    else:
        return gdc(b,a)

n=int(input())
a=linput()
flg=0
for i in range(len(a)-1):
    if gdc(a[i],a[i+1])!=1:
        flg=1
        break
if flg==0:
    print("pairwise coprime")
else:
    g=gdc(a[0],a[1])
    for i in range(2,len(a)):
        g=gdc(g,a[i])
    if g==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def get_prime_factors(x):
    out = set()
    if x < 1:
        return out
    while not x%2:
        out.add(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.add(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.add(x)
    return out


def main():
    n = int(input())
    a = list(map(int, input().split()))
    df = defaultdict(lambda : 0)
    for ai in a:
        primes = get_prime_factors(ai)
        for prime in primes:
            df[prime] += 1
    val = max(df.values())
    if val == 1:
        print("pairwise coprime")
    elif val == n:
        print("not coprime")
    else:
        print("setwise coprime")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math

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

def gcd_n(xs):
    if len(xs) == 1:
        return xs[0]
    return math.gcd(xs[0], gcd_n(xs[1:]))


if gcd_n(A) != 1:
    print("not coprime")
    exit()

for i in range(2, 10**3):
    cnt = 0
    for j in range(N):
        if A[j] % i == 0:
            cnt += 1
            if cnt >= 2:
                print("setwise coprime")
                exit()

print("pairwise coprime")

Submission status: Runtime Error

Solution code:
def make_divisors(n):
    divisors = []
    # 試し割りで、かつ積でnを作るときの相方も同時に追加してる
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
from math import gcd
import sys
n = int(input())
a_ls = list(map(int, input().split()))
now = a_ls[0]
for i in range(1,n):
    now = gcd(now,a_ls[i])
if now != 1:
    print('not coprime')
    sys.exit()
else:
    a_ls.sort()
    Max = a_ls[-1]
    is_in_a = [0] * (Max+1)
    for a in a_ls:
        is_in_a[a] = 1

    res = 'pairwise coprime'
    
    lim = int(Max**0.5)+2
    isdone = [0] * (Max+1)
    # baseは共通の素因数の候補
    for base in range(2,lim+1):
        if isdone[base]:
            continue
        now = base*2
        time_inA = 0
        while now <= Max:
            isdone[now] = 1
            if is_in_a[now]:
                time_inA += 1
                if time_inA >= 2:
                    res = 'setwise coprime'
            now += base
    print(res)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

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

flg = True
for i in range(n-1):
    for j in range(i+1, n):
        if math.gcd(a[i], a[j]) != 1:
            if i != 0:
                a = a[i-1:]
            flg = False
            break
    if flg:
        print('pairwise coprime')
        exit()

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

Submission status: Runtime Error

Solution code:
from math import gcd
N = int(input())
A = [int(i) for i in input().split()]
st=set()
s=0
pn = [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]

for a in A:
  if a == 1:
    continue
  ary=[]
  d={}
  while a % 2 == 0:
    if 2 in d:
      d[2] += 1
    else:
      d[2] = 1
    a//=2
  i=1
  n = 3
  while n * n <= a:
    if a % n == 0:
      a //= n
      if n in d:
        d[n] += 1
      else:
        d[n] = 1
    else:
      i += 1
      n=pn[i]
  if a > 1:
    ary.append(a)
    if a in d:
      d[a]=1

  for k in d.keys():
    if k in st:
      break
    else:
      st.add(k)
  else:
    continue

  n=gcd(A[0],A[1])
  for a in A[2:]:
    n=gcd(n,a)
  if n == 1:
    print("setwise coprime")
  else:
    print("not coprime")
  exit()
 
print("pairwise coprime")

Submission status: Runtime Error

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

pc = True
gg = False
cnt = Counter()

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
    while search_list[0] <= math.sqrt(number):
      #search_listの先頭の値が√nの値を超えたら終了
      #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        search_list = [num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list

plimes = get_primenumber(max(A))

def factorization(n):
    arr = []
    temp = n
    for p in plimes:
        if temp%p==0:
            while temp%p==0:
                temp //= p
            arr.append(p)
        if p > temp:
            break
    """
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)
    """
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

for a in factorization(A[0]):
    if a > 1:
        cnt[a] = 1

for i in range(1, N):
    for a in factorization(A[i]):
        if cnt[a] >= 1:
            pc = False
        if a > 1:
            cnt[a] += 1

if pc:
    print("pairwise coprime")
elif cnt.most_common(1)[0][1] < N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import os
import heapq
import sys,threading
import math as mt
import bisect
import operator
from collections import defaultdict
sys.setrecursionlimit(10**5)
from io import BytesIO, IOBase
def gcd(a,b):
    if b==0:

        return a
    else:
        return gcd(b,a%b)
def power(x, p,m):
    res = 1
    while p:
        if p & 1:
            res = (res * x) % m
        x = (x * x) % m
        p >>= 1
    return res
def inar():
    return [int(k) for k in input().split()]
dic={}
def lcm(num1,num2):
    return (num1*num2)//gcd(num1,num2)

# Python3 program to find prime factorization
# of a number n in O(Log n) time with
# precomputation allowed.


MAXN = 100001

# stores smallest prime factor for
# every number
spf = [0 for i in range(MAXN)]


# Calculating SPF (Smallest Prime Factor)
# for every number till MAXN.
# Time Complexity : O(nloglogn)
def sieve():
    spf[1] = 1
    for i in range(2, MAXN):
        spf[i] = i

    # separately marking spf for
    # every even number as 2
    for i in range(4, MAXN, 2):
        spf[i] = 2

    for i in range(3, mt.ceil(mt.sqrt(MAXN))):

        # checking if i is prime
        if (spf[i] == i):

            # marking SPF for all numbers
            # divisible by i
            for j in range(i * i, MAXN, i):
                if (spf[j] == j):
                    spf[j] = i

                # A O(log n) function returning prime


# factorization by dividing by smallest
# prime factor at every step
def getFactorization(x):
    ret = defaultdict(int)
    while (x != 1):
        ret[spf[x]]+=1
        x = x // spf[x]

    return ret

#
# # Driver code
#
# # precalculating Smallest Prime Factor
#
# x = 12246
# print("prime factorization for", x, ": ",
#       end="")
#
# # calling getFactorization function
# p = getFactorization(x)
#
# for i in range(len(p)):
#     print(p[i], end=" ")


# This code is contributed
# by Mohit kumar 29


def main():
    #t=int(input())
    global dic
    t=1
    for _ in range(t):
        n=int(input())
        arr=inar()
        sieve()
        coprime=True
        dic=defaultdict(int)
        for i in range(n):
            take=getFactorization(arr[i])
            for key in take.keys():
                dic[key]+=1
                if dic[key]>1:
                    coprime=False
                    break
            if coprime==False:
                break
        if coprime:
            print("pairwise coprime")
        else:
            gc=arr[0]
            for i in range(n):
                gc=gcd(arr[i],gc)
            if gc==1:
                print("setwise coprime")
            else:
                print("not coprime")





BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()
    #threadin.Thread(target=main).start()

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
m=max(a)+1
g=a[0]
d=dict()
for i in a:
    g=math.gcd(g,i)
    if i in d:
        d[i]+=1
    else:
        d[i]=1
if g>1:
    print("not coprime")
else:
    p=[0]*(m)
    ch=0
    for i in range (2,m):
        if p[i]==1:
            continue
        p[i]=1
        ans=0
        for j in range (i,m,i):
            ans+=d[j]
        if ans>1:
            ch=1
            break
    if ch==1:
        print("setwise coprime")
    else:
        print("pairwise coprime")