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 functools import reduce


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


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


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    if gcd_list(a) != 1:
        print("not coprime")
    else:
        a=set(a)
        asn=False
        for i in range(2,10**3+1):
            checked=False
            for j in range(i,10**6+1,i):
                if j in a:
                    if checked=True:
                        ans=True
                    else: checked=True
        print('setwise coprime' if ans else 'pairwise coprime')
        


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def factorization(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)

    if temp!=1:
        arr.append(temp)

    return arr

N=int(input())
A=list(map(int, input().split()))
p=1
A=sorted(A)
num1=A.count(1)
B=list(set(A))
if len(B)<len(A)-num1+1:
    p=0
S=set(factorization(B[0]))
T=set(factorization(B[0]))
flg=0
for i in range(1,len(B)):
    prime=set(factorization(B[i])
    if T&prime!=set():
        flg=1
    S=S&prime
    T=T|prime    #print(S,T)
if S!=1:
    print('not coprime')
elif flg==1 or p=0:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
import numpy as np


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)
        data = [e for e in data if e % p != 0]

    return data


N = int(input())
A = np.array(list(map(int, input().split())), dtype=np.int64)
A = np.sort(A)

P = get_sieve_of_eratosthenes(int(A[-1] + 1))

ans = "pairwise coprime"
for p in P:
    q = [A % p == 0]
    s = np.sum(q)
    if s > 1:
        ans = "setwise coprime"

    if s == N:
        ans = "not coprime"
        break

print(ans)

Submission status: Runtime Error

Solution code:
conf = False
 
#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

p = primes(1000)

def test_prime(m, check_list):
    global conf
    for i in p:
        if m % i == 0:
            if check_list[i] >= 1:
                conf = True
            check_list[i] += 1
    return check_list
 
def main():
    N = int(input())
    A = list(map(int, input().split()))
    check_list = [0]*(max(A))
    for i in range(len(A)):
        check_list = test_prime(A[i], check_list)
    if max(check_list) == len(A):
        return "not coprime"
    else:
        if conf:
            return "setwise coprime"
        else:
            return "pairwise coprime"
 
if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:
n=int(input())
A=set(map(int,input().split()))
ma=max(A)
data=[i for i in range(2,ma)]

pco=True
sco=True
while True:
  d=data[0]
  if d>ma**0.5:break
  one=d in A
  new=[]
  if one:k=1
  else:k=0
  for e in data[1:]:
    if e%d==0:
      k+=1
      if e in A:
        if one:pco=False
        else:one=True
    else:
      new.append(e)
  if k==n:
	sco=False
    break
if pco:
  print('pairwise coprime')
elif sco:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Runtime Error

Solution code:
import math

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

    pairwise_flag=0
    setwise_flag=1

    gcd_list=[]
    g=A[N-1]
    for i in range(N-1,0,-1):
        g=math.gcd(g,A[i-1])
        gcd_list.append(g)

    for i in range(N-1,0,-1):
        g=gcd_list[i]
        if i==0 and g==1:
            setwise_flag=0

        if g!=1:
            pairwise_flag=1
            break

    if pairwise_flag==0:
        print("pairwise coprime")
    elif setwise_flag==0:
        print("setwise coprime")
    else:
        print("not coprime")

if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split()))

    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


    def prime_factor_table(n):
        table = [0] * (n + 1)
        for i in range(2, n + 1):
            if table[i] == 0:
                for j in range(i + i, n + 1, i):
                    table[j] = i
        return table

    def prime_factor(n, prime_factor_table):
        prime_count = collections.Counter()

        while prime_factor_table[n] != 0:
            prime_count[prime_factor_table[n]] += 1
            n //= prime_factor_table[n]
        prime_count[n] += 1

        return prime_count
    tabel = prime_factor_table(N)

    numset = set()
    for i in A:
        thedic = prime_factor(i, tabel)
        for l in thedic.keys():
            flag = True
            if l in numset:
                flag = False
                break
        if flag:
            numset.add(thedic.keys())
        else:
            break
    if flag:
        print('pairwise coprime')
    else:
        theset = set(prime_factor(A[0], table).keys())
        for i in A[1:]:
            thedic = prime_factor(i, tabel)
            theset = theset & set(thedic.keys())
            if len(theset) == 0:
                print('setwise coprime')
                flag = False
                    break
    if flag:
        print('setwise coprime')









if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

setwise = A[0]

A = sorted(A,reverse = True)
prime = [0] * (10**6+1)
judge = True

for a in A:
  setwise = gcd(setwise,a)
  if prime[a]:
    continue
  else:
    prime[a] += 1
    if a%2==0:
      if prime[2]:
        judge = False
      prime[2] += 1
      a//=2
      if (a!=2)and(prime[a]):
        judge = False
      prime[a] += 1
    
    for i in range(3,int((a)**(1/2))+1,2):
      if a%i==0:
        if prime[i]:
          judge = False
        prime[i] += 1
        
if judge:
  print(ans)
  
elif setwise==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Runtime Error

Solution code:
import sympy
import bisect


def fprimes(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]]


n = int(input())
A = list(map(int, input().split()))
A.sort()
ue = 10**6+10
check = [False]*ue
yakusuu = [False]*ue
index = bisect.bisect(A, 1)
A = A[index:]


primes = fprimes(10**3+10)
na = len(A)
B = set(A)
nb = len(B)
if na != nb:
    print("not coprime")
    exit()

for a in A:
    check[a] = True
sc = 0
pc = 1
ll = sympy.divisors(A[0])
for l in primes:
    count = 0
    for a in A:
        if a % l == 0:
            count += 1
    boo = all([a % l == 0 for a in A])
    if boo == True and sc == 0:
        sc = 1
    if count >= 2 and pc == 1:
        pc = 0
if pc == 1:
    print("pairwise coprime")
    exit()


if sc == 1:
    print("not coprime")

    exit()

print("setwise coprime")

Submission status: Runtime Error

Solution code:
import math

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

g = [math.gcd(A[i], A[j]) i for in range(N-1) j for in range(i, N)]

n = 0
for i in g:
  if i!=1:
    break
  n += 1
if n==len(g):
  print("pairwise coprime")

Submission status: Runtime Error

Solution code:
//////// Coprime 
// https://atcoder.jp/contests/abc177/tasks/abc177_e
// date: 2020-08-29T21:00:28.779732
// memo: 
    
//<editor-fold desc="my macro">

#include<bits/stdc++.h>
#ifdef LOCAL
    #include<my/dump.h>
#else
    #define dump(...) 42 
    #define dumpi(x) 42 
#endif

typedef long long ll;
using namespace std;

#define repe(x, a) for(auto& (x) : (a))
#define _overload3(_1, _2, _3, name, ...) name
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rep3(i, a, b) for(ll i=a, i##_len=(b);i<i##_len;i++)
#define _rep2(i, n) _rep3(i,0,n)
#define repd(...) _overload3(__VA_ARGS__,_repd3,_repd2,)(__VA_ARGS__)
#define _repd3(i, a, b) for(ll i=b-1, i##_len=(a);i>=i##_len;i--)
#define _repd2(i, n) _repd3(i,0,n)
#define loop(...) _overload3(__VA_ARGS__,,_loop2,_loop1)(__VA_ARGS__)
#define _loop2(i, a) for(ll i=a;; i++)
#define _loop1(i) _loop2(i,0)

#define all(x) x.begin(),x.end()
#define SIZE(x) ((ll)(x).size())

#define F first
#define S second
#define vec vector
#define umap unordered_map
#define uset unordered_set

ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define inrange(x,start,stop) ((start) <= (x) && (x) < (stop))
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template <typename Cont, typename Func>
Cont fmap(const Cont &container, Func functor) {
    Cont result(container.size());
    std::transform(container.begin(), container.end(), result.begin(), functor);// [](int x){return x * 2;}
    return result;
}
template <typename Cont, typename Pred>
Cont filter(const Cont &container, Pred predicate) {
    Cont result;
    std::copy_if(container.begin(), container.end(), std::back_inserter(result), predicate);// [](int x){return x == 2;}
    return result;
}   

template<typename T, typename ...Args>
void ci(T& first, Args&... args) {
    ((cin >> first), ..., (cin >> args)); //C++17
}

template<char Sep, typename T, typename ...Args>
void print_seq(const T& first, const Args&... args) {
    ((cout << first), ..., (cout << Sep << args)); //C++17
}

void co(){ cout << endl; }
template<typename... Words>
void co(Words... words) {
    print_seq<' '>(words...);
    cout << endl;
}
#define coi(x) cout<<(x)<<" "

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define sankou(n,a,b) cout << ((n) ? (a) : (b) ) << endl

#define asrt(expr...) assert((expr))
//</editor-fold>

#define INF 1e19
#define MOD 1e9+7
#define MAXR 1e5

int solve() {
    int n;
    ci(n);
    vec<int> a;
    rep(i,n) {
        int buf;
        ci(buf);
        a.push_back(buf);
    }
    dump(n);
    dump(a);

    uset<int> seki;
    uset<int> kyotuu;

    bool setwise = false;
    bool flags[1010];
    rep(i,1005) flags[i] = true;

    rep(i,n) {
        rep(j,1005) {
            dump(i,j);
            if (fmod(a[i] ,(int)j) == 0) {
                if(seki.count((int)j)) {
                    setwise = true;
                } else {
                    flags[i] = false;
                    seki.insert((int)j);
                }
            }
        }
    }

    rep(i,1005) {
        if(flags[i] == true) {
            co("not coprime");
            return 0;
        }
    }
    if(setwise) {
        co("setwise coprime");
    } else {
        co("pairwise coprime");
    }

    return 0;
}

int main(){
    //入力の高速化用のコード
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    
    solve();
    return 0;
}

Submission status: Runtime Error

Solution code:
d = {}
N = int(input())
A = list(map(int,input().split()))
for ai in A:
	for prime in factorization(ai):
    	if prime[0] in d.keys():
        	d[prime[0]] += 1
    	else:
        	d[prime[0]] = 1
if max(d.values()) == N:
	print("not coprime")
elif max(d.values()) == 1:
	print("pairwise coprime")
else:
	print("setwise coprime")

Submission status: Runtime Error

Solution code:

import sys
input = sys.stdin.readline

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def sieve_optimized(limit):
    # Preprocessing step takes O(N log log N) time complexity.
    n = limit
    # Filimitd all primes upto n  (including n)
    sievebound = (n-1)//2
    sieve = [-1]*(sievebound + 1)
    # sieve[0] = True
    crosslimit = (int(sievebound**0.5) - 1)
    for i in range(1, crosslimit + 1):
        if sieve[i] == -1:
            for j in range(2*i*(i+1), sievebound + 1, 2*i+1):
                sieve[j] = 2*i + 1
    return sieve

def factorization(n, sieve):
    # Factorisaton query takes O(log N) time after preprocessing.
    divs = [1]
    while n!=1:
        if n&1:
            div = sieve[(n-1)//2]
            if div == -1:
                divs.append(n)
                break
            else:
                n //= div
                divs.append(div)
        else:
            n >>= 1
            divs.append(2)

    return divs

maxnum = 10**6
sieve = sieve_optimized(maxnum)
n = int(input())
nums = list(map(int, input().split()))

seen = dict()
for i in nums:
    factors = factorization(i, sieve)
    for f in set(factors[1:]):
        if f in seen:
            seen[f] += 1
        else:
            seen[f] = 1

maxval = max(seen.values())

if maxval == n:
    print('not coprime')

elif 1 < maxval < n:
    print('setwise coprime')

else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
import numpy as np


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)
        data = [e for e in data if e % p != 0]

    return data


N = int(input())
A = np.array(list(map(int, input().split())), dtype=np.int)
A = np.sort(A)

P = get_sieve_of_eratosthenes(int(A[-1] + 1))

ans = "pairwise coprime"
for p in P:
    q = [A % p == 0]
    s = np.sum(q)
    if s > 1:
        ans = "setwise coprime"

    if s == N:
        ans = "not coprime"
        break

print(ans)

Submission status: Runtime Error

Solution code:
import math
import copy

n=int(input())
a=list(map(int,input().split()))
ch5=0
if M in a:
  if M==1:
    ch5+=1
    a.remove(M)
if ch5>0:
  a.append(1)
B=copy.deepcopy(a)


dp=[0 for _ in range(1000000+1)]

sosuu = [2]
A = 1000
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.append(L)
        

if len(a)>80000:
  g=a[0]
  for h in range(1,n):
    g=math.gcd(g,a[h])
    
  if g==1:
    print('setwise coprime')
    
  else:
    print('not coprime')
  
  

else:
  ch1=0
  ch3=0
  for w in sosuu:
    ch2=0
    for q in range(n):
      if B[q]%w==0:
        ch2+=1
        S=B[q]
        while S%w==0:
          S=S//w
        B[q]=S
    if ch2>1:
      ch3+=1
  d={}
  ch4=0
  for u in B:
      if u>1000:
        if u not in d:
          d[u]=0
        else:
          ch4+=1
  if ch3==0 and ch4==0:
    print('pairwise coprime')
    
      
  
  
    
  else:
    g=a[0]
    for h in range(1,n):
      g=math.gcd(g,a[h])
    
    if g==1:
      print('setwise coprime')
    
    else:
      print('not coprime')

Submission status: Runtime Error

Solution code:
import math
N = int( input() )
A = sorted( list(map(int, input().split())))
ans = A[0]
L = []
mod = 10 ** 7 + 9

cnt = 0
for i in range(1, N):
    ans = math.gcd(ans, A[i])
    if ans == 1:
      break
    else:
      cnt += 1
if ans != 1:
  ret = "not coprime"
else:
  if cnt > 0:
    ret = "setwise coprime"
  else:
    for a in A:
      product = ( product * a ) % mod
    ret = "pairwise coprime"
    for a in A:
      ans = math.gcd(a, product // a)
      if a != 1:
        ret = "setwise coprime"
        break
print( ret )

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
m = A[0]
R = int(A[-1]**0.5)

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(R+2)
l = 0
for i in range(2, R+2):
    if checked[i]:
        continue
    
    while A[l] < i:
        l += 1
    
    if l == N-1:
        break
    
    tmp = 0
    for j in range(l, N):
        if A[j]%i == 0:
            tmp += 1

    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    
    if is_setwise_coprime == False:
        break
    
    n = i
    while n < R+2:
        checked[n] = 1
        n += i
    # print(checked, l)
if is_pairwise_coprime:
    print('pairwise coprime')
elif is_setwise_coprime:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

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

def erat():
    tmp = [False if i == 0 or i == 1 else True for i in range(10 ** 3)]
    for i in range(2, 10 ** 3):
        if tmp[i]:
            for j in range(2 * i, 10 ** 3, i):
                tmp[j] = False
            yield i

a = {}
for i in erat():
    for j in range(N):
        if A[j] % i == 0:
            while not A[j] % i:
                A[j] //= i
            if i in a:
                a[i] += 1
            else:
                a[i] = 1

for i in iter(filter(lambda x: x != 1, A)):
    if A[i] in a:
        a[A[i]] += 1
    else:
        a[A[i]] = 1

if max(a.values()) == 1:
    print('pairwise coprime')
elif max(a.values()) != N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
input=sys.stdin.readline
from random import randint
##import numpy as np
##sys.setrecursionlimit(10**7)
mo=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
##def gcd(a,b): 
##    if a == 0: 
##        return b 
##    return gcd(b % a, a)
prime1=[]
def SieveOfEratosthenes(n): #list of primes upto n
    global prime1
    prime1 = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime1[p] == True): 
            for i in range(p * p, n+1, p): 
                prime1[i] = False
        p += 1
    f=[]
    for p in range(2, n): 
        if prime1[p]: 
            f.append(p)
    return f

def lcm(a,b): 
    return (a*b) // math.gcd(a,b) 
for _ in range(1):
    n=inin()
    l=ain()
    f1,f2=0,0
    gc=l[0]
    d=dd(int)

    for i in range(1,n):
        gc=math.gcd(gc,l[i])
    if(gc!=1):print("not coprime")
    else:
        lp=SieveOfEratosthenes(int(max(l)**(0.5))+2)
        for i in l:
          	if(i!=1):
              for j in lp:
                  if(i%j==0):
                      if(d[j]==1):
                          f1=1
                          break
                      d[j]=1
              if(f1):break
        if(f1):
            print("setwise coprime")
        else:
            print("pairwise coprime")
        
        
    
    
    

 
    
    
    
    
        
        
    
    
    
    


    




##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_right

import math
from functools import reduce

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

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

def primes(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]]

P = primes(10**6)

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

check = [0]*(10**6)
flag = 0
for a in A:
    temp = 0
    for i in range(bisect_right(P, int(a**0.5+10))):
        if a%P[i] == 0:
            if check[P[i]] == 1:
                flag = 1
            else:
                check[P[i]] = 1
            temp = 1
    if check[a] == 1:
        flag = 1
    if not temp:
        check[a] = 1
    if flag:
        break

if gcd_list(A) > 1:
    print("not coprime")
elif flag:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Runtime Error

Solution code:
import math
n=int(input())
l=list(map(int,input().split()))
e=0
e1=0
e2=0
e3=0
c=l[0]
for i in range(1,n):
    c=math.gcd(l[i],c)
for i in range(n):
    if(l[i]%2==0):
        e+=1
    if(l[i]%3==0):
        e1+=1
    if(l[i]%5==0):
        e2+=1
    if(l[i]%7==0):
        e3+=1
l.sort()
aa=0
for i in range(n//2):
    for j in range(2,100):
        if(l[i]*j in l):
            aa=1
            break
    
if(e<=1 and e1<=1 and e2<=1 and e3<=1 and aa=0 and c==1):
    print("pairwise coprime")
elif(c==1):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
ans1 = A[0]
ans2 = 0
f = True
for i in range(1, N):
    ans1 = math.gcd(ans1, A[i])
    for j in range(i+1, N):
        ans2 = math.gcd(A[i-1],A[j-1])
        if (ans2 > 1):
            f = False
            break
    if f==False and ans !=1:
        break


if f:
    print('pairwise coprime')
else:
    if ans1==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)
is_prime = [True] * (m + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, m + 1):
    for j in range(i * 2, m + 1, i):
        is_prime[j] = False
primes = [i for i in range(m + 1) if is_prime[i]]

Amap = {a: 0 for a in range(1, m + 1)}
for a in A:
    Amap[a] += 1

# Pmap[p]はAにでてくるpの倍数の数
Pmap = {p: 0 for p in primes}
for p in primes:
    for a in range(p, m + 1, p):
        Pmap[p] += Amap[a]

score = max(Pmap.values())

if score == 1:
    print('pairwise coprime')
elif score != n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    sosus = set(get_primes(max(A)+1))
    dvd = set()



    val = A[0]
    for i in A:
        val = math.gcd(i,val)

    if val ==1:
        pass
    else:
        print('not coprime')
        return

    for i in A:
        tmp=[]
        for j in sosus:
            if j>i:
                break
            if i % j ==0:
                tmp.append(j)
                while i % j ==0:
                    i //=j
            if i ==1:
                break
        sosus.difference_update(tmp)
        
        if i != 1:
            break
    else:
        print('pairwise coprime')
        return

    print('setwise coprime')

resolve()

Submission status: Runtime Error

Solution code:
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)
def lcm(a,b):
    return int(a*b/gcd(a,b))


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

for i in range(n-1):
    d=a[i];e=a[i+1];f=c[n-i-1]
    if gcd(d,f)==1:
        continue
    else:
        res1=False
        b=gcd(b,e)

if res1:
    print("pairwise coprime")
elif b==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

from math import gcd


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

lc = [0]
for aa in a:
    lc.append(gcd(lc[-1], aa))

if lc[-1] != 1:
    print('not coprime')
    exit()

def eratosthenes(limit):
    import math
    if not isinstance(limit, int):
        raise TypeError('n is int type.')
    if limit < 2:
        raise ValueError('n is more than 2')
    prime = []
    sqrt_limit = math.sqrt(limit)
    prime_numbers_list = [i + 1 for i in range(1, limit)]
    while True:
        p = prime_numbers_list[0]
        if sqrt_limit <= p:
            return prime + prime_numbers_list
        prime.append(p)
        prime_numbers_list = [e for e in prime_numbers_list if e % p != 0]
    return prime_numbers_list

prime_numbers_list = eratosthenes(int((a[-1])**0.5))

count = [0]*len(prime_numbers_list)


for aa in a:
    for i, prime in enumerate(prime_numbers_list):
        if aa % prime ==0:
            count[i] += 1
            break

if max(count)>=2:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
prime = sieve_of_eratosthenes(2*10**5+1)
g = gcd_list(A)
if g != 1: print('not coprime');exit();

for p in prime:
  cnt = 0
  for a in A:
    if a%p == 0: cnt += 1
    if cnt == 2:
      print('setwise coprime')
      exit()
print('pairwise coprime')

Submission status: Runtime Error

Solution code:
rom math import gcd
def MinimumGCD(arr, n): 
    g = 0 
    for i in range(n): 
        g = gcd(g, arr[i]) 
    return g 
def isPrime(k):
    if (k == 1):
        return 0
    else:
        i=2
        while(i*i<k):
            if(k%i==0):
                return 1
            i+=1
        return 0
n=int(input())
a=list(map(int,input().split()))
primecount=0
for i in range(n):
    primecount+=(isPrime(a[i]))
if(primecount<=1):
    print('pairwise coprime')
else:
    if(MinimumGCD(a,n)==1):
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Runtime Error

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

pc = True
if N != len(A):
    pc = False
    N = len(A)

gg = False
cnt = Counter()

def factorization(n):
    arr = []
    temp = n
    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:
def PrimeFactorization(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            yield i
            n //= i
            while n % i == 0:
                n //= i
    if n > 1:
        yield n


def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    pairwise = True
    d = {}
    for i in a[:-1]:
        for j in PrimeFactorization(i):
            if j in d:
                j[d] += 1
                if pairwise:
                    pairwise = False
            else:
                d[j] = 1
    for j in PrimeFactorization(a[-1]):
        if j in d:
            if d[j] == n - 1:
                print("not coprime")
                return
            if pairwise:
                pairwise = False
    if pairwise:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    resolve()