Problem:


Score : 500 points

Problem Statement

We have N integers. The i-th number is A_i.

\{A_i\} is said to be pairwise coprime when GCD(A_i,A_j)=1 holds for every pair (i, j) such that 1\leq i < j \leq N.

\{A_i\} is said to be setwise coprime when \{A_i\} is not pairwise coprime but GCD(A_1,\ldots,A_N)=1.

Determine if \{A_i\} is pairwise coprime, setwise coprime, or neither.

Here, GCD(\ldots) denotes greatest common divisor.

Constraints

2 \leq N \leq 10^6

1 \leq A_i\leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

If \{A_i\} is pairwise coprime, print pairwise coprime; if \{A_i\} is setwise coprime, print setwise coprime; if neither, print not coprime.

Sample Input 1

3
3 4 5

Sample Output 1

pairwise coprime

GCD(3,4)=GCD(3,5)=GCD(4,5)=1, so they are pairwise coprime.

Sample Input 2

3
6 10 15

Sample Output 2

setwise coprime

Since GCD(6,10)=2, they are not pairwise coprime. However, since GCD(6,10,15)=1, they are setwise coprime.

Sample Input 3

3
6 10 16

Sample Output 3

not coprime

GCD(6,10,16)=2, so they are neither pairwise coprime nor setwise coprime.



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Runtime Error

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

"""
エラトステネスの篩

1. 探索リストに2からxまでの整数を昇順で入れる。
2. 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。
3. 上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
4. 探索リストに残った数を素数リストに移動して処理終了。
"""
A_max = max(A)
P = []
arr = list(range(2, A_max + 1))
while len(arr) > 0:
    i = arr.pop(0)
    P.append(i)
    arr = [j for j in arr if j % i != 0]
    if i > A_max ** 0.5:
        P.extend(arr)
        break

"""
素因数分解
"""


facts = [[A_i % p == 0 for p in P] for A_i in A]

for i in range(len(P)):
    if sum(facts[:][i]) >= 2:
        break
    if i == len(P)-1:
        print('pairwise coprime')

for i in range(len(P)):
    if all(facts[:][i]):
        break
    if i == len(P)-1:
        print('setwise coprime')

print('not coprime')

Submission status: Runtime Error

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

"""
エラトステネスの篩

1. 探索リストに2からxまでの整数を昇順で入れる。
2. 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。
3. 上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
4. 探索リストに残った数を素数リストに移動して処理終了。
"""
A_max = max(A)
P = []
arr = list(range(2, A_max + 1))
while len(arr) > 0:
    i = arr.pop(0)
    P.append(i)
    arr = [j for j in arr if j % i != 0]
    if i > A_max ** 0.5:
        P.extend(arr)
        break

"""
素因数分解
"""


facts = [[A_i % p == 0 for p in P] for A_i in A]

if all(sum(facts[:][i]) < 2 for i in range(len(P))):
    print('pairwise coprime')
    exit()

if all(not all(facts[:][i]) for i in range(len(P))):
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Runtime Error

Solution code:
from functools import reduce
from math import gcd

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

c=max(A)+1
D=[0]*c
div=[0]*c
P=[]

for i in range(2,c):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>=c  or j>D[i] :
           break
        D[i*j]=j

for i in A:
    if i==1:
        continue
    temp=i
    while temp!=1:
        div[D[temp]]+=1
        temp2=D[temp]
        while temp%temp2==0 and temp>=temp2:
            temp=temp//temp2


if max(div)<=1:
    print('pairwise coprime')
    hoge

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
from functools import reduce
from math import gcd

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

c=max(A)+1
D=[0]*c
div=[0]*c
P=[]

for i in range(2,c):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>=c  or j>D[i] :
           break
        D[i*j]=j

for i in A:
    if i==1:
        continue
    temp=i
    pt=[]
    while temp!=1:
        if D[temp] not in pt:
            div[D[temp]]+=1
        pt.append(D[temp])
        temp=temp//D[temp]

#print(div)

if max(div)==1:
    print('pairwise coprime')
    hoge

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Runtime Error

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

maxn =  105
prime = [0 for _ in range(maxn)]

for i in range(2, maxn):
    if prime[i] == 0:
        for j in range(i, maxn, i):
            prime[j] = i #最大質因數

st = set() #目前出現過的所有質因數，一開始為A[0]的所有質因數
a = A[0]
while prime[a]:
    st.add(prime[a])
    x = prime[a]
    while (a % x == 0):
        a //= x

pairwise = True
st2 = st #所有數共有的質因數，一開始為A[0]的所有質因數
for a in A[1:]:
    tmp = set()
    for j in st2:
        if a % j == 0:
            tmp.add(j)

    st2 = tmp
    if pairwise:
        while prime[a]:
            if prime[a] in st:
                pairwise = False
            st.add(prime[a])
            x = prime[a]
            while (a % x == 0):
                a //= x

if pairwise:
    print("pairwise coprime")
elif len(st2) == 0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
from functools import reduce
from math import gcd

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

c=max(A)+1
D=[0]*c
div=[0]*c
P=[]

for i in range(2,c):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>=c  or j>D[i] :
           break
        D[i*j]=j
g=c
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]
    if f==1:
        break

if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')
    hoge

Submission status: Runtime Error

Solution code:
from functools import reduce
from math import gcd

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

c=max(A)+1
D=[0]*c
div=[0]*c
P=[]

for i in range(2,c):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>=c  or j>D[i] :
           break
        D[i*j]=j
g=c
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]
    if f==1:
        break

if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')
    hoge

else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
from functools import reduce
from math import gcd

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

c=10**4+1
D=[0]*c
div=[0]*c
P=[]

for i in range(2,c):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>c-1  or j>D[i] :
           break
        D[i*j]=j
g=A[0]
f=0
for i in A:
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        continue
    while temp!=D[temp]:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp=temp//D[temp]
    if f==1:
        break

if f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Runtime Error

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

A_max = max(A)
P = []
arr = list(range(2, A_max + 1))
while True:
    i = arr.pop(0)
    P.append(i)
    arr = [j for j in arr if j % i != 0]
    if i > A_max ** 0.5:
        P.extend(arr)
        break


def factorize(x):
    f = []
    for p in P:
        rest = x
        cnt = 0
        while True:
            if rest % p != 0:
                break
            rest = rest // p
            cnt += 1
        f.append(cnt)
    return f


facts = [factorize(A_i) for A_i in A]

if all(sum([facts[j][i] > 0 for j in range(N)]) < 2 for i in range(len(P))):
    print('pairwise coprime')
    exit()

if all(not all([facts[j][i] > 0 for j in range(N)]) for i in range(len(P))):
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Runtime Error

Solution code:
import math

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

"""
エラトステネスの篩

1. 探索リストに2からxまでの整数を昇順で入れる。
2. 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。
3. 上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
4. 探索リストに残った数を素数リストに移動して処理終了。
"""
A_max = max(A)
P = []
arr = list(range(2, A_max+1))
while True:
    i = arr.pop(0)
    P.append(i)
    arr = [j for j in arr if j % i != 0]
    if i > A_max**0.5:
        P.extend(arr)
        break

# print(P)

"""
素因数分解
"""
def factorize(x):
    f = []
    for p in P:
        rest = x
        cnt = 0
        while True:
            if rest % p != 0:
                break
            rest = rest // p
            cnt += 1
        f.append(cnt)
    return f

facts = [factorize(A_i) for A_i in A]

# for i in range(len(P)):
#     print([facts[j][i] > 0 for j in range(N)])
#
# for i in range(len(P)):
#     print(sum([facts[j][i] > 0 for j in range(N)]))

if all(sum([facts[j][i] > 0 for j in range(N)]) < 2 for i in range(len(P))):
    print('pairwise coprime')
    exit()

if all(not all([facts[j][i] > 0 for j in range(N)]) for i in range(len(P))):
    print('setwise coprime')
    exit()

print('not coprime')

# for i in range(len(P)):
#     print(any([facts[j][i] > 0 for j in range(N)]))
#
# for fact in facts:
#     print(fact)

Submission status: Runtime Error

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

maxV = (10 ** 6 + 1)

sieve = [i for i in range(maxV)]
p = 2

while p*p < maxV:
    if sieve[p] == p:
        for q in range(p*2, maxV, p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1

from math import gcd

g = 0
primes = set()
for a in A:
    g = gcd(g, A)

    v = a
    while a > 1:
        prime = sieve[a]
        if prime in primes:
            print('')
        primes.add(prime)
        a = a // prime


if g > 1:
    print('not coprime')

for a in A:
    while a > 1:
        prime = sieve[a]
        if prime in primes:
            print('pairwise coprime')
            exit()
        primes.add(prime)
        a = a // prime

print('setwise coprime')

Submission status: Runtime Error

Solution code:
from math import gcd

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

c=max(A)
D=[0]*(c+1)
div=[0]*(c+1)
P=[]

for i in range(2,c+1):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>c and i>D[j]:
           break
        D[i*j]=j

for i in A:
    c=gcd(c,i)
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        div[temp]+=1
        continue
    while temp!=D[temp]:
        div[D[temp]]+=1
        temp=temp//D[temp]

if max(div)<=1:
    print('pairwise coprime')

elif c==1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Runtime Error

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

c=max(A)
D=[0]*(c+1)
div=[0]*(c+1)
P=[]

for i in range(2,c+1):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>c and i>D[j]:
           break
        D[i*j]=j

for i in A:
    c=gcd(c,i)
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        div[temp]+=1
        continue
    while temp!=D[temp]:
        div[D[temp]]+=1
        temp=temp//D[temp]

if max(div)<=1:
    print('pairwise coprime')

elif c==1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
from math import gcd

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

c=max(A)
D=[0]*(c+1)
div=[0]*(c+1)
P=[]

for i in range(2,c+1):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>c:
           break
        D[i*j]=j

for i in A:
    c=gcd(c,i)
    temp=i
    if temp==D[temp]:
        div[temp]+=1
        continue
    while temp!=D[temp]:
        div[D[temp]]+=1
        temp=temp//D[temp]

if max(div)<=1:
    print('pairwise coprime')

elif c==1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
from math import gcd

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

c=max(A)
g=max(A)
D=[0]*(c+1)
yak=[0]*(c+1)
P=[]

for i in range(2,c+1):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>c:
           break
        D[i*j]=j 

for i in A:
    g=gcd(g,i)
    temp=i
    while temp!=D[temp]:
        yak[D[temp]]+=1
        temp=temp//D[temp]

if max(yak)<=1:
    print('pairwise coprime')

elif g==1:
    print('setwise coprime')

else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
from math import gcd

"""
pairwise coprimeであるための条件は、全てのAに関して素因数に重複がないことである。
したがって、各Aに関して素因数分解を行う⇒各数の素因数の種類数をカウントし総和する。⇒全体の素因数の種類数をカウントし、先ほどの総和と比較する。
"""
N = int(input())
A = list(map(int,input().split()))
primes = set()
cnt = 0
for i in range(N):
    a = A[i]
    d = 2
    ceil = int(a**0.5)+1
    for d in range(2,ceil)
        if a % d == 0:
            cnt += 1
            primes.add(d)
            for _ in range(100):
                if a % d==0:
                    a //= d
                else:
                    break
        d += 1

if cnt == len(primes):
    print('pairwise coprime')
    exit()
g = A[0]
for i in range(1,N):
    g = gcd(g,A[i])
if g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define soort(v) sort(v.begin(),v.end())
#define foor(i,n) for(int i=0; i<n; i++)
#define vecprint(v){for(int i=0; i<v.size(); i++)cout << v[i] << " ";}
#define arrprint(v, n){for(int i=0; i<n; i++)cout << v[i] << " ";}
long long int gcd(long long int a, long long int b){if(a%b==0)return b;return gcd(b, a%b);}
long long int lcm(long long int a, long long int b){return (a*b)/gcd(a, b);}

int arr[1000007];
bool flag1 = false;


vector<long long> primes;
void SieveOfEratosthenes(int n=1000000)
{

   vector <bool>prime(n+1,true);

   for (int p=2; p*p<=n; p++)
   {

       if (prime[p] == true)
       {

           for (int i=p*p; i<=n; i += p)
               prime[i] = false;
       }
   }


   for (int p=2; p<=n; p++)
      if (prime[p])
        primes.push_back(p);
}


void trial_division4(long long n) {
    vector<long long> factorization;
    map <int,int> mp;
    for (long long d : primes) {
        if (d * d > n)
            break;
        while (n % d == 0) {
            // factorization.push_back(d);
            // cout << d;
            if(mp[d]==0){
              if(arr[d]==1){
                flag1 = true;
                break;
              }
              arr[d] = 1;
              mp[d] = 1;
            }
            n /= d;
        }
    }
    if (n > 1){
      if(mp[n]==0){
        if(arr[n]==1){
          flag1 = true;
        }
        arr[n] = 1;
        mp[n] = 1;
      }
    }
    // return factorization;
}


int main(){
  long long n, m;
  bool flag = false;
  cin >> n;
  SieveOfEratosthenes();
  vector<long long> v;
  v.resize(n);

  for(auto &it: v)
    cin >> it;

  m = __gcd(v[0], v[1]);

  trial_division4(v[0]);
  // cout << flag1 << v[0] << endl;
  // arrprint(arr,17);
  trial_division4(v[1]);

  if(m > 1)
    flag = true;

  for(int i=2; i<n; i++){
    trial_division4(v[i]);
    m = __gcd(m, v[i]);
    if(m > 1)
      flag = true;
  }
  if(!flag1)
    cout << "pairwise coprime" << endl;
  else if (m > 1){
    cout << "not coprime" << endl;
  }
  else
      cout << "setwise coprime" << endl;
  // else
    // cout << ""

    return 0;
}