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:
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(false);  cin.tie(NULL); cout.tie(NULL);
#define scan(a,n) for(long int index=0;index<n;index++) cin>>a[index];
#define print(a,n) for(long int index=0;index<n;index++) cout<<a[index]<<" ";cout<<endl;
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ss second
#define ff first
#define vli vector<long long int>
#define vlli vector<pair<long long int,long long int>>
#define vsi vector<string>
#define vci vector<char>
#define all(n) (n.begin(),n.end())


 
int main() {
   #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    fast;
    ll n;
    cin>>n;
    ll a[n],i;
    scan(a,n);
    map<ll,bool> m;
    ll mu=1,lc=1,gc=__gcd(a[0],a[1]),f=0,x,j;
    for(i=0;i<n;i++){
        if(i>1)
             gc=__gcd(a[i],gc);

            if(f==0){
                if(m[2]==1 && a[i]%2==0){
                        f=1;
                        break;
                    }
                 while(a[i]%2==0){
                   
                    a[i]/=2;
                    
                     m[2]=1;
                 }
                 x=a[i];
                 for(j=3;j<=sqrt(x);j+=2){
                    if( a[i]%j==0){
                        if(m[j]==1 ){
                        f=1;
                        break;}
                    }
                      while(a[i]%j==0){
                        
                        m[j]=1;

                    a[i]/=j;
                      }
                 }
                 m[a[i]]=1;

               
            }
            // cout<<f<<endl;
        

    }
    for(i=0;i<n;i++){
        if(i>1)
             gc=__gcd(a[i],gc);
     }
    if(f==0){
        cout<<"pairwise coprime";
        return 0;
    }
    // cout<<gc<<endl; 
    if(gc==1) cout<<"setwise coprime";
    else cout<<"not coprime";


return 0;    
 }

Submission status: Runtime Error

Solution code:
check_list = [0]*1000010
conf = False

def get_prime(m):
    global check_list
    global conf
    pf = {}
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
            if pf[i] == 1:
                if check_list[i] >= 1:
                    conf = True
                    check_list[i] += 1
                elif check_list[i] == 0:
                    check_list[i] = 1
    if m>1:
        pf[m]=1
        if check_list[i] >= 1:
            conf = True
            check_list[i] += 1
        elif check_list[i] == 0:
            check_list[i] = 1
    return pf

def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(len(A)):
        get_prime(A[i])
    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=list(map(int, input().split()))
A=sorted(A)
import math
import bisect
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, cnt])

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

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

    return arr
if A==[1]*N:
  print('pairwise coprime')
  exit()
a=A[0]
d=a
if A[0]!=1:
  D={}
  x=0
  for i in range(N):
    if d!=1:
      d=math.gcd(d,A[i])
    c=A[i]
    if x==0:
      F=factorization(A[i])
      for a,b in F:
        if a not in D:
          D[a]=1
        else:
          x=1
        #互いに素じゃない二組がある  
    if x==1 and d==1:
      break

  if x==1 and d==1:
    print('setwise coprime')
  elif x==0 and d==1:
    print('pairwise coprime')
  else:
    print('not coprime')
else:
  l=bisect.bisect_right(A,1)
  A=A[l:]
  D={}
  x=0
  for i in range(N):
    F=factorization(A[i])
    for a,b in F:
      if a not in D:
        D[a]=1
      else:
        x=1
    if x==1:
      break
    
  if x==1:
    print('setwise coprime')
  else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
n=int(input())
p=list(map(int,input().split()))
List=[0 for _ in range(max(p)+1)]

def L(N):
    i=1
    while i*i<=N:
        if N%i==0:
            List[i]+=1
            if i!=N//i:
                List[N//i]+=1
        i+=1
for i in range(n):
    L(p[i])

List=List[2:]
ans='pairwise coprime'
for i in range(int(len(List)**0.5)+1):
    if List[i]==n:
        ans='not coprime'
        break
    if List[i]>1:
        ans='setwise coprime'       
print(ans)

Submission status: Runtime Error

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

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

sa = set(A)
if len(sa) < N:
    print('setwise coprime')
    exit()

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
small_primes = []
while p*p <= MAXN:
    if sieve[p]:
        small_primes.append(p)
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1

st = set()
for a in A:
    for p in small_primes:
       found = False
        while a%p==0:
            a //= p
            found = True
        if found:
            if p in st:
                print('setwise coprime')
                exit()
            st.add(p)
        if a==1: break
    else:
        if a in st:
            print('setwise coprime')
            exit()
        st.add(a)

print('pairwise coprime')

Submission status: Runtime Error

Solution code:

#input routine
n = int(input())
line = [int(x) for x in input().split()]

#euclidean algo
def gcd(a,b):
    if (a == 0):
        return b
    else:
        return (gcd(b%a, a))

#get product
prod = 1
for i in range(0, len(line)):
    prod *= line[i]

#get lcm
lcm = 1
for i in range(0, len(line)):
    g = gcd(lcm, line[i])
    lcm = g* (lcm/g)* (line[i]/g)

if prod == lcm:
    print("pairwise coprime")
else:
    #get set gcd
    g = line[0]
    for i in range(1, len(line)):
        g = gcd(g, line[i])

    if (g == 1):
        print ("setwise coprime")
    else:
        print ("not coprime")

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
n = A.count(1)
B = [x for x in A if x != 1]
x = yes
for i in range(0,N-n-1):
  for j in range(i+1,N-n):
    for k in range(2,B[i]+1):
      if B[i]%k == 0 and B[j]%k == 0:
        x = no
if x == yes:
  print("pairwise coprime")
y = yes      
for m in range(2,B[0]+1):
  for l in range(0,N-n):
    if B[l]%m != 0:
      y = no
  if y == yes:
    print("not coprime")
    break
    
print("setwise coprime")

Submission status: Runtime Error

Solution code:
import math

n = input()
lis = [int(a) for a in input().split(" ")]
lis_len = len(lis)
p_flag = True
s_flag = True

sqrt_max = int(math.sqrt(max(lis)))
for i in range(2, sqrt_max+1):
  mod_lis = [a % i for a in lis]
  non_zero_mod_lis = filter(lambda x:x!=0, mod_lis)
  if len(non_zero_mod_lis) <= lis_len-2:
	p_flag = False
  if len(non_zero_mod_lis) == 0:
    s_flag = False
    break
    
    
if p_flag:
  print("pairwise coprime")
elif s_flag:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Runtime Error

Solution code:
import java.util.*;
import java.io.*;
import java.math.BigInteger;
import java.text.*;
public class Main {
    static int mod = 1000_000_007;
    static long lim = (long)1e9 + 6;
    static long mod1 = 998244353;
    static boolean fileIO = false;
    static FastScanner f;
    static int inf = 2000_000_000;
    static PrintWriter pw = new PrintWriter(System.out);
    static Scanner S = new Scanner(System.in);
    static long x0; static long y0;
    static long iinf = (long)(1e18);
    static double eps = (double)1e-4;
    static int MAXN = 1000001; 
    static int[] spf = new int[MAXN]; 
    static int[] hash1 = new int[MAXN]; 
    static void sieve() { 
        spf[1] = 1; 
        for (int i = 2; i < MAXN; i++) spf[i] = i;
        for (int i = 4; i < MAXN; i += 2) spf[i] = 2; 
        for (int i = 3; i * i < MAXN; i++) { 
            if (spf[i] == i) { 
                for (int j = i * i; j < MAXN; j += i) 
                    if (spf[j] == j) spf[j] = i; 
            } 
        } 
    } 
 
    static void getFactorization(int x) { 
        int temp; 
        while (x != 1) { 
            temp = spf[x]; 
            if (x % temp == 0) { 
                hash1[spf[x]]++; 
                x = x / spf[x]; 
            } 
            while (x % temp == 0) 
                x = x / temp; 
        } 
    } 
    static boolean check(int x) { 
        int temp; 
        while (x != 1)  { 
            temp = spf[x]; 
        if (x % temp == 0 && hash1[temp] > 1) 
            return false; 
        while (x % temp == 0) 
            x = x / temp; 
        } 
        return true; 
    } 
    static void solve()throws IOException {
        int n = f.ni();
        int arr[] = new int[n];
        for (int i = 0; i < n; ++i) arr[i] = f.ni();
        sieve(); 
        boolean ok = false;
        for (int i = 0; i < n; i++) getFactorization(arr[i]); 
        int g = 0;
        for (int i = 0; i < n; i++) {
            ok |= check(arr[i]);
            g = gcd(g , arr[i]);
        }
        if (ok) pn("pairwise coprime");
        else {
            if (g == 1) pn("setwise coprime");
            else pn("not coprime");
        }
    }          
    public static void main(String[] args)throws IOException {
        init();
        int t = 1;
        int tt = 1;
        //fw = new FileWriter("!out.txt");
        while(t --> 0) {
            //fw.write("Case #" + (tt++) + ": ");
            //fw.write("\n");
            solve();
        }
        pw.flush(); 
        pw.close();
        //fw.close();  
    }
        
/******************************END OF MAIN PROGRAM*******************************************/
    public static void init()throws IOException{f=new FastScanner(System.in);}
    public static class FastScanner {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastScanner.SpaceCharFilter filter;
 
        public FastScanner(InputStream stream) {
            this.stream = stream;
        }
 
        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
 
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
 
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
 
        public int ni() {
            int c = read();
 
            while (isSpaceChar(c))
                c = read();
 
            int sgn = 1;
 
            if (c == '-') {
                sgn = -1;
                c = read();
            }
 
            int res = 0;
            do {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
 
            return res * sgn;
        }
 
        public long nl() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
 
            do {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public String next() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            }
            while (!isSpaceChar(c));
            return res.toString();
        }
 
        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
    public static void pn(Object o){pw.println(o);}
    public static void pi(Object o){pw.print(o);pw.flush();}
    public static void p(Object o){pw.print(o);}
    public static void pni(Object o){pw.println(o);pw.flush();}
    static int gcd(int a,int b){if(b==0)return a;else{return gcd(b,a%b);}}
    static long gcd(long a,long b){if(b==0l)return a;else{return gcd(b,a%b);}}
    static long lcm(long a,long b){return (a*b/gcd(a,b));}
    static long exgcd(long a,long b){if(b==0){x0=1;y0=0;return a;}long temp=exgcd(b,a%b);long t=x0;x0=y0;y0=t-a/b*y0;return temp;}
    static long pow(long a,long b){long res=1;while(b>0){if((b&1)==1)res=res*a;b>>=1;a=a*a;}return res;}
    static long mpow(long a,long b, long m){long res=1;while(b>0){if((b&1)==1)res=((res%m)*(a%m))%m;b>>=1;a=((a%m)*(a%m))%m;}return res;}
    static long mul(long a , long b){return ((a%mod)*(b%mod)%mod);}
    static long adp(long a , long b){return ((a%mod)+(b%mod)%mod);}
    static boolean isPrime(long n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(long i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
    static boolean isPrime(int n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
    static HashSet<Long> factors(long n){HashSet<Long> hs=new HashSet<Long>();for(long i=1;i<=(long)Math.sqrt(n);i++){if(n%i==0){hs.add(i);hs.add(n/i);}}return hs;}
    static HashSet<Integer> factors(int n){HashSet<Integer> hs=new HashSet<Integer>();for(int i=1;i<=(int)Math.sqrt(n);i++){if(n%i==0){hs.add(i);hs.add(n/i);}}return hs;}
    static HashSet<Long> pf(long n){HashSet<Long> ff=factors(n);HashSet<Long> ans=new HashSet<Long>();for(Long i:ff)if(isPrime(i))ans.add(i);return ans;}
    static HashSet<Integer> pf(int n){HashSet<Integer> ff=factors(n);HashSet<Integer> ans=new HashSet<Integer>();for(Integer i:ff)if(isPrime(i))ans.add(i);return ans;}
    static int[] inpint(int n){int arr[]=new int[n+1];for(int i=1;i<=n;++i){arr[i]=f.ni();}return arr;}
    static long[] inplong(int n){long arr[] = new long[n+1];for(int i=1;i<=n;++i){arr[i]=f.nl();}return arr;}
    static boolean ise(int x){return ((x&1)==0);}static boolean ise(long x){return ((x&1)==0);}
    static int gnv(char c){return Character.getNumericValue(c);}
    static int log(long x){return x==1?0:(1+log(x/2));} static int log(int x){return x==1?0:(1+log(x/2));}
    static void sort(int[] a){ArrayList<Integer> l=new ArrayList<>();for(int i:a)l.add(i);Collections.sort(l);for(int i=0;i<a.length;++i)a[i]=l.get(i);}
    static void sort(long[] a){ArrayList<Long> l=new ArrayList<>();for(long i:a)l.add(i);Collections.sort(l);for(int i=0;i<a.length;++i)a[i]=l.get(i);}
    static void sort(ArrayList<Integer> a){Collections.sort(a);}
}

Submission status: Runtime Error

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

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

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

def gcd(a, b):
	if (a == 0 or b == 0): 
		return False
	if (a == b): 
		return a
	if (a > b): 
		return gcd(a-b, b)

	return gcd(a, b-a)

def coprime(a, b):
	return (gcd(a, b) == 1) 

def numOfPairs(arr, n) : 
	count = 0

	for i in range(0, n-1) : 
		for j in range(i+1, n) :

			if (coprime(arr[i], arr[j])):
				count = count + 1

	return count 

if numOfPairs(a,n) == n:
	print('pairwise coprime')
elif gcd_list(a) == 1:
	print('setwise coprime')
else:
	print('not coprime')

Submission status: Runtime Error

Solution code:
import math

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

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    tmp = b
    b = a
    a = tmp 
while a % b != 0:
    a, b = b, a % b

for i in range(2, n):
    a = als[i]
    if a < b:
        tmp = b
        b = a
        a = tmp 
    while a % b != 0:
        a, b = b, a % b
    if b == 1:
        ans = "setwise coprime"
        break

existeven = False

failed = False

for i in range(n):
    if als[i] >= 2 and als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

if not failed:
    for i in range(3, int(math.sqrt(maxa))+1, 2):
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        ans = "pairwise coprime"

print(ans)

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:
# -*- 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 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())
als = list(map(int, input().split()))

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    tmp = b
    b = a
    a = tmp 
while a % b != 0:
    a, b = b, a % b

for i in range(2, n):
    a = als[i]
    if a < b:
        tmp = b
        b = a
        a = tmp 
    while a % b != 0:
        a, b = b, a % b
    if b == 1:
        ans = "setwise coprime"
        break

existeven = False

failed = False

for i in range(n):
    if als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

if not failed:
    for i in range(3, int(math.sqrt(maxa))+1, 2):
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        ans = "pairwise coprime"

print(ans)

Submission status: Runtime Error

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

pc = "pairwise coprime"
sc = "setwise coprime"
nc = "not coprime"

maxi=max(A)
sumi=set()

for i in range(2,maxi+1):
    if i in sumi:
        pass
    else:
        tmp=maxi//i
        for j in range(2,tmp+1):
            sumi.add(j*i)

            cnt=0
for num in A:
    if num in sumi:
        cnt +=1
if cnt<=1:
    ans=pc
else:
    tmp2=A[0]
    for q in range(1,N):
        tmp2 = gcd(tmp2,A[q])
    if tmp2==1:
        ans=sc
    else:
        ans=nc

print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(false);  cin.tie(NULL); cout.tie(NULL);
#define scan(a,n) for(long int index=0;index<n;index++) cin>>a[index];
#define print(a,n) for(long int index=0;index<n;index++) cout<<a[index]<<" ";cout<<endl;
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ss second
#define ff first
#define vli vector<long long int>
#define vlli vector<pair<long long int,long long int>>
#define vsi vector<string>
#define vci vector<char>
#define all(n) (n.begin(),n.end())


 
int main() {
   #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    fast;
    ll n;
    cin>>n;
    ll a[n],i;
    scan(a,n);
    map<ll,int> m;
    ll mu=1,lc=1,gc=__gcd(a[0],a[1]),f=0,x,j;
    for(i=0;i<n;i++){
        if(i>1)
             gc=__gcd(a[i],gc);

            if(f==0){
                if(m[2]==1 && a[i]%2==0){
                        f=1;
                        break;
                    }
                 while(a[i]%2==0){
                   
                    a[i]/=2;
                    
                     m[2]++;
                 }
                 x=a[i];
                 for(j=3;j<=sqrt(x);j+=2){
                    if(m[j]==1 && a[i]%j==0){
                        f=1;
                        break;
                    }
                      while(a[i]%j==0){
                        
                        m[j]++;

                    a[i]/=j;
                      }
                 }
                 m[a[i]]++;

               
            }
            // cout<<f<<endl;
        

    }
    for(i=0;i<n;i++){
        if(i>1)
             gc=__gcd(a[i],gc);
     }
    if(f==0){
        cout<<"pairwise coprime";
        return 0;
    }
    // cout<<gc<<endl; 
    if(gc==1) cout<<"setwise coprime";
    else cout<<"not coprime";


return 0;    
 }

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 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 sys
import cmath

input = sys.stdin.readline


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

GCD = p[0]
LCM = p[0]
mul = p[0]

done = False

for i in range(1, n):
    GCD = cmath.gcd(GCD, p[i])

    if not done:
        LCM = cmath.lcm(LCM, p[i])
        mul *= p[i]

    if LCM != mul:
        done = True

if not done:
    print("pairwise coprime")
elif done and GCD == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import math

N = int(input())
A_L = [int(x) for x in input().split()]
A_L.sort()


def get_sieve_of_eratosthenes(n):
    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]


f_l = get_sieve_of_eratosthenes(A_L[-2])

flag = False
for f in f_l:
    _len = len([e for e in A_L if e % f == 0])
    if _len == N:
        print("not coprime")
        exit(0)
    elif _len > 1:
        flag = True
if flag:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Runtime Error

Solution code:
def prime_factors(n, used):
    i = 2
    factors = []
    fackinds = set()
    while i**2 <= n:
        if n % i != 0:
            i += 1
        else:
            if i not in fackinds:
                used[i] += 1
            fackinds.add(i)
            factors.append(i)
            n = n // i
    if n > 1:
        if n not in fackinds:
            used[n] += 1
        fackinds.add(n)
        factors.append(n)
    return fackinds, factors

import math
def primes(n):
    max = math.sqrt(n)
    candidates = [i for i in range(2, n+1)]
    primes = []
    while candidates[0] <= max:
        primes.append(candidates[0])
        candidates = [candidates[i] for i in range(len(candidates)) if candidates[i] % candidates[0] != 0]
    primes.extend(candidates)
    return primes

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    used = [0 for i in range(10**5)]
    for a in A:
        fackinds, factors = prime_factors(a, used)
    prims = primes(10**5)
    two_over = False
    n_over = False
    for p in prims:
        if used[p] >= 2:
            two_over = True
        if used[p] == N:
            n_over = True
    
    if two_over:
        if n_over:
            print("not coprime")
        else:
            print("setwise coprime")
    else:
        print("pairwise coprime")
    #print(used)

if '__main__' == __name__:
    resolve()

Submission status: Runtime Error

Solution code:
from math import gcd
from functools import reduce

def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        result.append((p, e))
    return result


def f():
    s = set()
    for i in range(N - 1, -1. -1):
        t = prime_factorize(A[i])
        for p, _ in t:
            if p in s:
                return False
            s.add(p)
    return True


N, *A = map(int, open(0).read().split())

prime_table = make_prime_table(10 ** 6)
if f():
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

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())) 
c=0
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)
  if f==1:
      c=c+1
if c==3:
    print('pairwise  coprime')
z=0
else:
    f=l[0]
    y=l[1]
    a=max(f,y)
    b=min(f,y)
    r=gcd(a,b)
    for w in range(2,len(l)):
        r=gcd(r,l[w])
    	if r==1:
        	continue
    	else:
        	print('not coprime')
            z=1
            break
if z==0:
  print('setwise coprime')

Submission status: Runtime Error

Solution code:

import numpy as np


def main():
    n, m = map(int, input().split())
    friends_mat = np.zeros((n, n), dtype=int)
    for i in range(m):
        a, b = map(int, input().split())
        friends_mat[a - 1][b - 1] = 1
        friends_mat[b - 1][a - 1] = 1
    print(friends_mat)
    print(max(friends_mat.sum(axis=0)+1))


if __name__ == "__main__":
    main()