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:
# coding: utf-8
from math import gcd

def getPrime(x):
    num_list=[i for i in range(2,x+1)]
    prime_list=[]
    D=[x+1 for i in range(x+1)]
    
    while num_list[0]<x**(1/2):
        p=num_list.pop(0)
        prime_list.append(p)
        for i in range(len(num_list)):
            if num_list[i]%p==0:
                if D[num_list[i]]>p:
                    D[num_list[i]]=p
        num_list = [e for e in num_list if e % p != 0]
    
    prime_list = prime_list + num_list
    for i in range(len(prime_list)):
        D[prime_list[i]] = prime_list[i]
    D[0]=1
    D[1]=1
    return D

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

pc_flg = True

x = A[0]
for i in range(N):
    x = gcd(x,A[i])

prime_flg=[False for i in range(10**6+1)]

for i in range(N):
    num = A[i]
    primes = []
    while True:
        p = D[num]
        num = num//p
        primes.append(p)
        if num == 1:
            break
        for j in set(primes):
            if not(prime_flg[j]):
                prime_flg[j] = True
            else:
                pc_flg = False

if pc_flg:
    print("pairwise coprime")
elif x==1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
# 自然数m以下の素数を返す（SETでRETURN）
import math
def prime_numbers(m):
    # 素数を保持するset
    primes = []

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.append(n)
        n += 1
    return primes

#素因数分解（10**6まで）
def soinsu_bunkai(m):
    pf=set()

    for i in pri_num:
        if i >m:
            break
        elif m%i==0:
            pf.add(i)

    return pf

    # 初期入力
import sys
from collections import Counter
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
pri_num =prime_numbers(sq_pri +10)

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    intersect =set()
    used =set()
    pair_w =set()
    set_w =set()
    for a in A:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            pair_w.add(0)
        else:
            pair_w.add(1)
        intersect |=aa

if 1 in pair_w and 0 not in pair_w:
    ans ="pairwise coprime"
else:
    ans ="setwise coprime"
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
def Ii():return int(sys.stdin.readline().rstrip())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))
n = Ii()
a = Li()
sc = 0
g = math.gcd(a[0],a[1])
for i in range(n-2):
  g = math.gcd(g,a[i+2])
  if(g == 1):
    sc = 1
    break
    
if(sc == 0):
  print('not coprime')
  exit(0)

isPrim = [0]*(max(a)+1)

def div(x,d):
  if(x%d == 0):
    x /= d
    isPrim[d] += 1
  return x

def prim(x):
  x = div(x,2)
  if(isPrim[2] > 1): return 1
  x = div(x,3)
  if(isPrim[3] > 1): return 1    
  itr = int(math.sqrt(x))
  for i in range(5,itr,6):
    x = div(x,i)
    if(isPrim[i] > 1): return 1
    x = div(x,i+2)
    if(isPrim[i+2] > 1): return 1
  return 0

    
for i in range(n):
  if(prim(a[i])):
    print('setwise coprime')
    exit(0)  
  
print('pairwise coprime')

Submission status: Runtime Error

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

# 入力前処理
# 1はいくつあっても関係ないので除く
A = [x for x in A if x > 1]
N = len(A)

R = max(A)
prime_factor_counter = [0]*(R+1)

# D[x]にxを割り切れる最初の素数を格納
# 次に行う素因数分解で試し割りのムダを削減するための前準備
D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i

# 素因数分解し、素因子をカウント
# ex: 12 => 2と3のカウントを+1する
for a in A:
    tmp = a
    while tmp > 1:
        prime_factor = D[tmp]
        prime_factor_counter[prime_factor] += 1
        while tmp%prime_factor == 0:
            tmp //= prime_factor

# 回答出力
if max(prime_factor_counter) < 2:
    print('pairwise coprime')
elif max(prime_factor_counter) < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

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

number_list = [0]*1000000
for a in A:
    number_list[a] += 1
    
flag1 = True
flag2 = True

for i in range(2,1000000):
    count = 0
    for j in range(1,1000000):
        if i*j > 1000000:
            break
        tmp = i*j
        count += number_list[tmp]
    if count > 1:
        flag1 = False
    if count == N:
        flag2 = False
        
if flag2 == False and flag1 == False:
    print("not coprime")
elif flag2 == True and flag1 == False:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Runtime Error

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

number_list = [0]*100010
for a in A:
    number_list[a] += 1
    
flag1 = True
flag2 = True

for i in range(2,100010):
    count = 0
    for j in range(1,100010):
        if i*j > 100000:
            break
        tmp = i*j
        count += number_list[tmp]
    if count > 1:
        flag1 = False
    if count == N:
        flag2 = False
        
if flag2 == False and flag1 == False:
    print("not coprime")
elif flag2 == True and flag1 == False:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Runtime Error

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

number_list = [0]*100001
for a in A:
    number_list[a] += 1
    
flag1 = True
flag2 = True

for i in range(2,100001):
    count = 0
    for j in range(1,100001):
        if i*j > 100000:
            break
        tmp = i*j
        count += number_list[tmp]
    if count > 1:
        flag1 = False
    if count == N:
        flag2 = False
        
if flag2 == False and flag1 == False:
    print("not coprime")
elif flag2 == True and flag1 == False:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Runtime Error

Solution code:
from math import gcd

def seachPrimeNum(N):
  max = int(N**0.5)
  seachList = [i for i in range(2,N+1)]
  primeNum = list(range(N+1))
  while seachList[0] <= max:
    tmp = seachList[0]
    tmp2 = list(seachList)
    for i in tmp2:
      if i%tmp == 0:
          primeNum[i]=tmp
          seachList.remove(i)
  return primeNum

def prime_factorize(n, f):
    a = []
    while n % f == 0:
        a.append(f)
        n //= f
    
    if f == 2:
      f=3
    else:
      f+=2
      
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
  
n = int(input())
a = list(map(int, input().split()))
d = seachPrimeNum(max(a))
dic = {}
g = a[0]

Submission status: Runtime Error

Solution code:
from math import gcd

def seachPrimeNum(N):
  max = int(N**0.5)
  seachList = [i for i in range(2,N+1)]
  primeNum = list(range(N+1))
  while seachList[0] <= max:
    tmp = seachList[0]
    tmp2 = list(seachList)
    for i in tmp2:
      if i%tmp == 0:
          primeNum[i]=tmp
          seachList.remove(i)
  return primeNum

def prime_factorize(n, f):
    a = []
    while n % f == 0:
        a.append(f)
        n //= f
    
    if f == 2:
      f=3
    else:
      f+=2
      
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
  
n = int(input())
a = list(map(int, input().split()))
d = seachPrimeNum(max(a))
dic = {}
g = a[0]
flg = True
for i in range(n):
  g = gcd(g, a[i])
  if flg:
    tmp = prime_factorize(a[i], d[a[i]])
    for j in set(tmp):
      if j in dic:
        flg = False
      else:
        dic[j]=1
        
if flg:
  print("pairwise coprime")
elif g == 1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Runtime Error

Solution code:
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
 
#define ll long long int
#define fast ios_base::sync_with_stdio(false)
#define fast_input cin.tie(NULL)
#define fast_output cout.tie(NULL)
#define vi vector<long long int> 
#define pb push_back
#define pa pair<long long int ,long long int> 
#define f(a,x,b) for(int a=x;a<b;a++)
#define fr(a,x,b) for(int a=x;a>=b;a--)
#define sort(x) sort(x.begin(),x.end());
#define siz(a) (int)a.size()
#define mod 1000000007
#define F first
#define S second
#define um unordered_map<ll,ll>
#define ordered_set tree<pa, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
vector<ll> spf(1000001,-1);
ll isprime[1000001];
void solve()
{
	ll n;
	cin>>n;
	vi v(n);
	ll gcc;
	f(i,0,n)
	{
		cin>>v[i];
		if(i==0)
		{
			gcc=v[i];
		}
		gcc=__gcd(gcc,v[i]);
	}
    if(gcc!=1)
	{
		cout<<"not coprime"<<endl;
		return;
	}
	isprime[0]=1;
	isprime[1]=1;
	for(int j=2;j*j<=1000000;j++)
	{
	  if(isprime[j]==0)
	  {
      for(int i=j*j;i<=1000000;i+=j)
	  {
		  spf[i]=j;
		  isprime[i]=1;
	  }
	  }
	}
	ll cnt[1000001]={0};
	f(i,0,n)
	{
		vi re;
		ll sp=spf[v[i]];
		while(sp!=-1)
		{
			re.pb(sp);
			cnt[sp]++;
			while(v[i]%sp==0)
			{
				v[i]/=sp;
			}
			sp=spf[v[i]];
			if(sp==-1&&v[i]>1)
			{
             cnt[v[i]]++;
			}
		}
		// for(ll d:re)
		// {
		// 	cout<<d<<" ";
		// }
		// cout<<endl;
	}
	ll fl=0;
	f(i,2,1000001)
	{
		if(isprime[i]==0&&cnt[i]>1)
		{
			fl=1;
		}
	}
	if(fl)
	{
		cout<<"setwise coprime"<<endl;
	}
	else
	{
		cout<<"pairwise coprime"<<endl;
	}
}
int main() {
	fast;
	fast_input;
	fast_output;
	// ll t;
	// cin>>t;
	// f(i,0,t)
	// {
        //  cout<<"Case #"<<i+1<<":"<<" ";
	     solve();
	// }
	return 0;
}

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
k=10**6+1
def judge(n,a):
  c=[0]**k
  for x in a:
    c[x]=+1
  t=any(sum(c[i::i])>1 for i in range(2,k))
  t+=reduce(gcd,a)>1
  return ['pairwise','setwise','not'][t]+' coprime'
n=int(input())
a=list(map(int,input().split()))
print(judge(n,a))

Submission status: Runtime Error

Solution code:
import math,sys

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


ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n=int(math.sqrt(10**6))+20
count=[False for _ in range(max_n)]

def fac(x):
    i=2
    flag=True
    while x>1:
        ind=0
        while x%i == 0:
            ind+=1
            x=int(x/i)
        if ind>0:
            if count[i]:
                flag=False
            else:
                count[i]=True
        i+=1
    if flag:
        return True
    else:
        return False

flag=True
for each in Ns:
    flag_2=fac(each)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
    sys.exit()

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

if gcd_ans==1:
    print(ans_s)
else:
    print(ans_n)

Submission status: Runtime Error

Solution code:
import math,sys

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


ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n=int(math.sqrt(10**6))+1
count=[0 for _ in range(max_n)]

def fac(x,T):
    for i in range(2,math.sqrt(x)+1):
        if x%i ==0:
            if count[i]==1:
                return False
            else:
                count[i]+=1
    return True

flag=True
for each in Ns:
    flag_2=fac(each,count)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
    sys.exit()

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

if gcd_ans==1:
    print(ans_s)
else:
    print(ans_n)

Submission status: Runtime Error

Solution code:
import math,sys

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


ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n=int(math.sqrt(10**7))+1
count=[0 for _ in range(max_n)]

def fac(x,T):
    i=2
    while x>1:
        ind=0
        while x%i == 0:
            ind+=1
            x=int(x/i)
        if ind>0:
            T[i]+=1
            if T[i]>1:
                return False
        i+=1
    return True

flag=True
for each in Ns:
    flag_2=fac(each,count)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
    sys.exit()

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

if gcd_ans==1:
    print(ans_s)
else:
    print(ans_n)

Submission status: Runtime Error

Solution code:
import math,sys

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


ans_p="pairwise coprime"
ans_s="setwise coprime"
ans_n="not coprime"

max_n=int(math.sqrt(10**6))+1
count=[0 for _ in range(max_n)]

def fac(x,T):
    i=2
    while x>1:
        ind=0
        while x%i == 0:
            ind+=1
            x=int(x/i)
        if ind>0:
            T[i]+=1
            if T[i]>1:
                return False
        i+=1
    return True

flag=True
for each in Ns:
    flag_2=fac(each,count)
    if not flag_2:
        flag=False
        break

if flag:
    print(ans_p)
    sys.exit()

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

if gcd_ans==1:
    print(ans_s)
else:
    print(ans_n)

Submission status: Runtime Error

Solution code:
# region header
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
# endregion
# region input function


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])

# endregion


class osa_k():
    def __init__(self, n):
        """高速素因数分解

        Args:
            n (int): n以下全ての値について素因数分解できるようにする
        """
        self.n = n
        self.minFactor = list(range(0, n + 1 + 1))
        self.prime = []

    def factorize(self, i):
        if not self.prime:
            self.get_sieve_of_eratosthenes()
        factor = []
        while i != 1:
            p = self.minFactor[i]
            factor.append(p)
            i //= p
        return factor

    def get_sieve_of_eratosthenes(self):
        """エラトステネスの篩

        Raises:
            TypeError: 型エラー
            ValueError: n>=2限定

        Returns:
            list(int): 素数の配列
        """
        if not isinstance(self.n, int):
            raise TypeError('n is int type.')
        if self.n < 2:
            raise ValueError('n is more than 2')
        prime = []
        limit = math.sqrt(self.n)
        data = [i + 1 for i in range(1, self.n)]
        while True:
            p = data[0]
            self.minFactor[p] = p
            if limit <= p:
                self.prime = prime + data
                return self.prime
            prime.append(p)
            new_data = []
            for i in data:
                if i % p != 0:
                    new_data.append(i)
                elif self.minFactor[i] == i:
                    self.minFactor[i] = p
            data = copy.deepcopy(new_data)


n = inp()
a = inpl()
factorizer = osa_k(max(a))
tmp = collections.defaultdict(int)
for i in a:
    p = set(factorizer.factorize(i))
    for j in p:
        tmp[j] += 1
max_val = max(tmp.values())
if max_val == 1:
    print("pairwise coprime")
elif max_val == n:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(x) for x in input().split()]

m = max(a)
primes = [1] * (m + 1)
primes[0], primes[1] = 0, 0
primes[2] = 2

for i in range(2, int(m ** 0.5)+1):
    if primes[i] == 0: continue
    for j in range(i, m+1, i):
        if primes[j] == 1:
            primes[j] = i

for i in range(m+1):
    if primes[i] == 1: primes[i] = i

b = [0] * (m + 1)
def factorization(n):
    aset = set()
    temp = n
    while temp != 1:
        aset.add(primes[temp])
        temp = temp // primes[temp]
    for i in aset:
        b[i] += 1

for aa in a:
    factorization(aa)
if max(b) == 1: print('pairwise coprime')
elif max(b) < n: print('setwise coprime')
else: print('not coprime')

Submission status: Runtime Error

Solution code:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase
 
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")
 
# ------------------- fast io --------------------
from math import gcd, ceil
 
def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi
 
 
def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans
 
def lcm(a, b): return a * b // gcd(a, b)
 
 
def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y



n = int(input())
a = list(map(int, input().split()))
primes = [2, 3, 5, 7, 11, 13]
for i in range(17, 1000, 2):
    ok = True
    j = 0
    while primes[j] * primes[j] <= i:
        j+=1
        if ok:
            primes += [i]

import collections
cnt = collections.defaultdict(int)
for val in a:
    tmp = val
    j = 0
    while primes[j] * primes[j] <= tmp:
       if tmp % primes[j] == 0:
            cnt[primes[j]]+=1
       while tmp % primes[j] == 0:
            tmp = tmp // primes[j]
       j+=1
    if tmp != 1:
        cnt[tmp]+=1

la = max(cnt.values())
if la <= 1:
    print("pairwise coprime")
    sys.exit(0)
print("setwise coprime" if la < n else "not coprime")

Submission status: Runtime Error

Solution code:
import math
import sys
from functools import lru_cache
sys.setrecursionlimit(10000000)

N = int(input())
A_list = [int(e) for e in input().split()]

#pairwise coprime …… 素因数分解したとき、共通のものが1個もない
#setwise coprime　…… 素因数分解したとき、全てで共通のものがない

#試し割の結果の辞書を求める
def make_trial_division_dict(n):
    #import math
    td_dict = dict()
    for i in range(2,n+1):
        if i not in td_dict:
            td_dict[i] = i
            for j in range(2,1+n//i):
                if j*i not in td_dict:
                    td_dict[j*i] = i
    td_dict[1] = 1
    return td_dict

#試し割結果の辞書を利用して素因数分解する
#@lru_cache(maxsize=None)
#def high_speed_prime_factorization(n):
#    pf_list = list()
#    pf_list.append(td_dict[n])
#    
#    if n//td_dict[n] == 1:
#        if n!=1:
#            pf_list.append(1)
#        return pf_list
#    else:
#        pf_list.extend(high_speed_prime_factorization(n//td_dict[n]))
#        return pf_list

td_dict = make_trial_division_dict(max(A_list))

all_pf = set()    #含まれる素因数がすべて集約される
common_pf = set() #共通する素因数が集約される
all_pf |= set(td_dict[A_list[0]])
common_pf |= set(td_dict[A_list[0]])
is_pairwise = True

#print(A_list[0],set(high_speed_prime_factorization(A_list[0])))

for i in range(1,len(A_list)):
    A_pf = set(td_dict[A_list[i]])
    common_pf &= A_pf 
    
    #print(A_list[i],set(high_speed_prime_factorization(A_list[i])))
    
    if is_pairwise and len(all_pf&A_pf)!=1: #1は共通で含まれる
        is_pairwise = False
    else:
        all_pf |= A_pf

if is_pairwise:
    print("pairwise coprime")
elif len(common_pf) == 1: #1は共通で含まれる
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
import java.util.*;
/**
 *
 * @author ujjwal abhishek
 */
public class E 
{
    static int gcd(int a, int b) 
    { 
        if (a == 0) 
            return b; 
        return gcd(b % a, a); 
    } 
    static int max = (int)(1e6+1);
    static int[] spf = new int[max];
    static void solve()
    {
        spf[1] = 1;
        for(int i=2;i<max;i++)
        {
            spf[i] = i;
        }
        for(int i=4;i<max;i+=2)
        {
            spf[i] = 2;
        }
        for(int i=3;i*i<max;i++)
        {
            if(spf[i]==i)
            {
                for(int j=i*i;j<max;j+=i)
                {
                    if(spf[j]==j)
                        spf[j] = i;
                }
            }
        }
    }
    public static boolean isPairwise(int[] arr,int n)
    {
        Set<Integer> set = new HashSet<>();
        for(int x:arr)
        {
            Set<Integer> list = new HashSet<>(factors(x));
            for(int y:list)
            {
                if(set.contains(y))
                    return false;
                else
                    set.add(y);
            }
        }
        return true;
    }
    public static List<Integer> factors(int x)
    {
        List<Integer> res = new ArrayList<>();
        while(x!=1)
        {
            res.add(spf[x]);
            x/=spf[x];
        }
        return res;
    }
    public static void main(String []args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for (int i=0;i<n;i++) arr[i]=sc.nextInt();
        int gcd=gcd(arr[0],arr[1]);
        for (int i=1;i<n;i++) gcd(gcd,arr[i]);
        if (gcd==1)
        {
            solve();
            if (isPairwise(arr,n))
                System.out.println("pairwise coprime");
            else
                System.out.println("setwise coprime");
        }
        else
            System.out.println("not coprime");
    }
}

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def prime_factors(n):
    arr = []
    temp = n
    R = int(-(-n**0.5//1))
    furui = [0]*(R+1)
    for i in range(2, R+1):
        if furui[i]:
            continue
        if temp%i == 0:
            while temp%i == 0:
                temp //= i
            arr.append(i)
        m = i
        while m < R+1:
            furui[m] = 1
            m += i

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

    return arr

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

nums = defaultdict(int)

for a in A:
    for x in prime_factors(a):
        nums[x] += 1

y = max(nums.values())

if y < 2:
    print('pairwise coprime')
elif y < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

    return arr

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

nums = defaultdict(int)

for a in A:
    for x in prime_factors(a):
        nums[x] += 1

y = max(nums.values())

if y < 2:
    print('pairwise coprime')
elif y < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

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


def sieve_of_eratosthenes(n): #エラトステネスのふるい
    if n==2:
        return [2]
    else:
        candidate = list(range(2, n+1)) #候補
        prime = []
        limit = n**0.5 + 1 #+1がないと平方数を素数にしてしまう
    
        while True:
            p = candidate[0] 
            if limit <= p:
                prime.extend(candidate) #この時点での残っているのは素数
                break
            prime.append(p) #pを素数リストに登録
    
            candidate = [i for i in candidate if i % p != 0]
    
            # i = 0
            # while True:
                # if i >= len(candidate): #iはcandidateの長さ分
                    # break
                # elif candidate[i] % p == 0: #余りがゼロなら
                    # candidate.pop(i) #素数ではないのでpop(取り除く)する
                # i += 1
    
        return prime



maxA=max(A)

prime = sieve_of_eratosthenes(maxA)

X=[0]*(maxA+1)
for i in range(N):
    X[A[i]]+=1

check=0
for i in prime:
    count=0
    for j in range(1,int(maxA/i)+1):
        count+=X[j*i]
    if count==N:
        print('not coprime')
        sys.exit()
    elif count>1:
        check=1
        
if check==1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

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


def sieve_of_eratosthenes(n): #エラトステネスのふるい
    candidate = list(range(2, n+1)) #候補
    prime = []
    limit = n**0.5 + 1 #+1がないと平方数を素数にしてしまう

    while True:
        p = candidate[0] 
        if limit <= p:
            prime.extend(candidate) #この時点での残っているのは素数
            break
        prime.append(p) #pを素数リストに登録

        candidate = [i for i in candidate if i % p != 0]

        # i = 0
        # while True:
            # if i >= len(candidate): #iはcandidateの長さ分
                # break
            # elif candidate[i] % p == 0: #余りがゼロなら
                # candidate.pop(i) #素数ではないのでpop(取り除く)する
            # i += 1

    return prime



maxA=max(A)

prime = sieve_of_eratosthenes(maxA)

X=[0]*(maxA+1)
for i in range(N):
    X[A[i]]+=1

check=0
for i in prime:
    count=0
    for j in range(1,int(maxA/i)+1):
        count+=X[j*i]
    if count==N:
        print('not coprime')
        sys.exit()
    elif count>1:
        check=1
        
if check==1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
import math
import sys
from functools import lru_cache
sys.setrecursionlimit(10000000)

N = int(input())
A_list = [int(e) for e in input().split()]

#pairwise coprime …… 素因数分解したとき、共通のものが1個もない
#setwise coprime　…… 素因数分解したとき、全てで共通のものがない

#試し割の結果の辞書を求める
def make_trial_division_dict(n):
    #import math
    td_dict = dict()
    for i in range(2,n+1):
        if i not in td_dict:
            td_dict[i] = i
            for j in range(2,1+n//i):
                if j*i not in td_dict:
                    td_dict[j*i] = i
    td_dict[1] = 1
    return td_dict

#試し割結果の辞書を利用して素因数分解する
@lru_cache(maxsize=None)
def high_speed_prime_factorization(n):
    pf_list = list()
    pf_list.append(td_dict[n])
    
    if n//td_dict[n] == 1:
        if n!=1:
            pf_list.append(1)
        return pf_list
    else:
        pf_list.extend(high_speed_prime_factorization(n//td_dict[n]))
        return pf_list

def main():
    td_dict = make_trial_division_dict(max(A_list))

    all_pf = set()    #含まれる素因数がすべて集約される
    common_pf = set() #共通する素因数が集約される
    all_pf |= set(high_speed_prime_factorization(A_list[0]))
    common_pf |= set(high_speed_prime_factorization(A_list[0]))
    is_pairwise = True

    #print(A_list[0],set(high_speed_prime_factorization(A_list[0])))

    for i in range(1,len(A_list)):
        A_pf = set(high_speed_prime_factorization(A_list[i]))
        common_pf &= A_pf 
        
        #print(A_list[i],set(high_speed_prime_factorization(A_list[i])))
        
        if is_pairwise and len(all_pf&A_pf)!=1: #1は共通で含まれる
            is_pairwise = False
        else:
            all_pf |= A_pf

    if is_pairwise:
        print("pairwise coprime")
    elif len(common_pf) == 1: #1は共通で含まれる
        print("setwise coprime")
    else:
        print("not coprime")

main()

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
max_A = max(A)
sqrt_max_A = max_A ** 0.5
sieve = list(range(2, max_A+1))
prime = list(range(max_A+1))
while True:
    p = sieve[0]
    prime[p]= p
    if p > sqrt_max_A:
        break
    new_sieve = []
    for s in sieve:
        if s % p == 0:
            prime[s] = p
        else:
            new_sieve.append(s)
    sieve = new_sieve
factors = {}
pairwise = True
for a in A:
    while prime[a] != a:
        if prime[a] in factors:
            pairwise = False
            break
        factors[prime[a]] = True
        p = prime[a]
        while a % p == 0:
            a //= p
    if a in factors:
        pairwise = False
    else:
        factors[a] = True
    if not pairwise:
        break
if pairwise:
    print('pairwise coprime')
else:
    gcd = reduce(math.gcd, A)
    if gcd == 1:
        print('setwise coprime')
    else:
        print('not coprime')