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: Wrong Answer

Solution code:
N = int(input())
A = [0]*(1000001)
for a in list(map(int, input().split())):
    A[a] += 1

# MFPF = Most Frequent Prime Factor
MFPF_n = 0
seen_prime_factor = [0]*(1000001)
for i in range(2, 1000001):
    if seen_prime_factor:
        continue
    n = i
    tmp = 0
    while n < 1000001:
        tmp += A[n]
        seen_prime_factor = 1
        n += i
    MFPF_n = max(MFPF_n, tmp)

if MFPF_n < 2:
    print('pairwise coprime')
elif MFPF_n - A[1] < N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math
 
n = int(input())
a = list(map(int,input().split()))
 
lcm = a[0]
pwise_flag = True
for i in range(1,n):
    gcd = math.gcd(lcm,a[i])
    if gcd != 1:
        pwise_flag = False
        break
    else:
        lcm = lcm*a[i]
        
if pwise_flag:
    print('pairwise coprime')
else:
    g = a[0]
    for i in range(1,n):
        g = math.gcd(g,a[i])
    if g == 1:
        print('not coprime')
    else:
        print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

checker = [0 for _i in range(10**6+1)]
for i in a:
    checker[i] += 1

if any(sum(checker[i::i])>1 for i in range(2, 10**6+1)):
    print('pairwise coprime')
else:
    r = a[0]
    for i in a:
        r = gcd(r, i)
    if r == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

h = True
checker = [0 for _i in range(10**6+1)]
for i in a:
    checker[i] += 1
    if sum(checker[i::i]) > 1:
        h = False
        break

if h == True:
    print('pairwise coprime')
else:
    r = a[0]
    for i in a:
        r = gcd(r, i)
    if r == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
MAX = 10**6+1

is_prime = [1]*MAX
primes = []
pf = {key:[] for key in a}

is_prime[0],is_prime[1] = 0,0

for i in range(2,MAX):
  if is_prime[i]:
    primes.append(i)
    k = i*2
    while k < MAX:
      is_prime[k] = 0
      if pf.get(k,-1) != -1:
        pf[k].append(i)
      k += i
      
primes_counter = {prime:0 for prime in primes}

for i in range(n):
  for p in pf[a[i]]:
    primes_counter[p] += 1

pc_flag = True
sc_flag = True

for p in primes:
  if primes_counter[p]>1:
    pc_flag = False
    if primes_counter[p] == n:
      sc_flag = False

if pc_flag:
  print('pairwise coprime')
elif sc_flag:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

checker = [0 for _i in range(10**6+1)]
h = True
for i in a:
    if i == 1:
        continue
    num = i
    if num%2==0:
        checker[2] += 1
        num //= 2
        if checker[2] >= 2:
            h = False
            break
    
    for j in range(3, int(i**0.5)+1):
        if num%j == 0:
            checker[j] += 1
            if checker[j] >= 2:
                h = False
                break
            num //= j
    if num == i:
        checker[num] += 1
        if checker[num] >= 2:
            h = False
            break
if h == True:
    print('pairwise coprime')
else:
    r = a[0]
    for i in a:
        r = gcd(r, i)
    if r == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

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

checker = [0 for _i in range(10**6+1)]
h = True
for i in a:
    if i == 1:
        continue
    num = i
    if num%2==0:
        checker[2] += 1
        if checker[2] >= 2:
            h = False
            break
    
    for j in range(3, int(i**0.5)+1):
        if num%j == 0:
            checker[j] += 1
            if checker[j] >= 2:
                h = False
                break
            num //= j
    if num == i:
        checker[num] += 1
        if checker[num] >= 2:
            h = False
            break
if h == True:
    print('pairwise coprime')
else:
    r = a[0]
    for i in a:
        r = gcd(r, i)
    if r == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
MAX = 10**6+1

is_prime = [1]*MAX
primes = []
pf = {key:[] for key in a}

is_prime[0],is_prime[1] = 0,0

for i in range(2,MAX):
  if is_prime[i]:
    primes.append(i)
    k = i*2
    while k < MAX:
      is_prime[k] = 0
      if k in pf:
        pf[k].append(i)
      k += i
      
primes_counter = {prime:0 for prime in primes}

for i in range(n):
  for p in pf[a[i]]:
    primes_counter[p] += 1

pc_flag = True
sc_flag = True

for p in primes:
  if primes_counter[p]>1:
    pc_flag = False
    if primes_counter[p] == n:
      sc_flag = False

if pc_flag:
  print('pairwise coprime')
elif sc_flag:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from math import gcd

n=int(input())
a=lnii()

g=a[0]
for i in range(n):
  g=gcd(g,a[i])

def factorization(n):
    p=2
    fcr=set()
    while p*p<=n:
        while n%p==0:
            fcr.add(p)
            n//=p
        p+=1
    if n>1:
        fcr.add(n)
    return fcr

def eratosthenes(lim):
  is_p=[1]*lim

  is_p[0]=0
  is_p[1]=0

  for i in a:
    fcr=factorization(i)
    for j in fcr:
      if is_p[i]:
        for k in range(i,lim,i):
          is_p[k]=0
      else:
        if g==1:
          print('setwise coprime')
        else:
          print('not coprime')
        exit()
  return is_p

lim=10**6+1
is_p=eratosthenes(lim)

print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from math import gcd

n=int(input())
a=lnii()

g=a[0]
for i in range(n):
  g=gcd(g,a[i])

def factorization(n):
    p=2
    fcr=set()
    while p*p<=n:
        while n%p==0:
            fcr.add(p)
            n//=p
        p+=1
    if n>1:
        fcr.add(n)
    return fcr

def eratosthenes(lim):
  is_p=[1]*lim

  is_p[0]=0
  is_p[1]=0

  for i in a:
    fcr=factorization(i)
    for j in fcr:
      if is_p[i]:
        for j in range(i,lim,i):
          is_p[j]=0
      else:
        if g==1:
          print('setwise coprime')
        else:
          print('not coprime')
        exit()
  return is_p

lim=10**6+1
is_p=eratosthenes(lim)

print('pairwise coprime')

Submission status: Wrong Answer

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

from math import gcd

r = a[0]
for i in a:
    r = gcd(r, i)

c = [0 for _i in range(10**6+1)]
h = True
for i in a:
    if i == 1:
        continue
    num = i
    if num%2 == 0:
        c[2] += 1
        if c[2] > 1:
            h = False
    for j in range(3, int(i**0.5)+1, 2):
        if num%j==0:
            c[j] += 1
            num //= j
            if c[j] > 1:
                h = False
    if num == i:
        c[i] += 1
        if c[i] > 1:
            h = False

if h:
    print('pairwise coprime')
elif r == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

def make_prime(n):
    array = set()
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                temp = temp // i
            array.add(i)

    if temp != 1:
        array.add(temp)

    if not array:
        array.add(n)

    return array


N = int(input())
A = list([int(x) for x in input().split()])

result = set()
before = -1
is_pairwise = True
for i in A:
    if is_pairwise:
        i_r = make_prime(i)
        if len(result & i_r) > 0:
            is_pairwise = False
        else:
            result |= i_r

    if before == -1:
        before = i
    else:
        before = gcd(i, before)

if is_pairwise:
    print('pairwise coprime')
    exit()

if before == 1:
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Wrong Answer

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

from math import gcd

r = a[0]
for i in a:
    r = gcd(r, i)

c = [0 for _i in range(10**6+1)]
h = True
for i in a:
    if i==1:
        continue
    num = i
    if num%2==0:
        c[2] += 1
    for j in range(3, int(num**0.5)+1, 2):
        if num%j == 0:
            num //= j
            c[j] += 1
            if c[j] > 1:
                h = False
    c[i] += 1
    if c[i] > 1:
        h = False
    if h == False:
        break

if h == True:
    print('pairwise coprime')
elif r == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

from math import gcd

r = a[0]
for i in a:
    r = gcd(r, i)

c = [0 for _i in range(10**6+1)]

for i in a:
    if i==1:
        continue
    num = i
    if num%2==0:
        c[2] += 1
    for j in range(3, int(num**0.5)+1, 2):
        if num%j == 0:
            num //= j
            c[j] += 1
    c[i] += 1

if all(i<2 for i in c):
    print('pairwise coprime')
elif r == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd

def make_prime(n):
    array = set()
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                temp = temp // i
            array.add(i)

    if temp != 1:
        array.add(temp)

    if not array:
        array.add(n)

    return array


N = int(input())
A = list([int(x) for x in input().split()])

result = set()
before = -1
is_pairwise = True
for i in A:
    i_r = make_prime(i)
    if len(result & i_r) > 0:
        is_pairwise = False
    else:
        result |= i_r

    if before == -1:
        before = i
    else:
        before = gcd(i, before)

if is_pairwise:
    print('pairwise coprime')
    exit()

if before == 1:
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Wrong Answer

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

from math import gcd

r = a[0]
for i in a:
    r = gcd(r, i)

c = [0 for _i in range(10**6+1)]
h = True
for i in a:
    if i==1:
        continue
    num = i
    if num%2==0:
        c[2] += 1
        if c[2] > 1:
            h = False
    for j in range(3, int(num**0.5)+2, 2):
        c[j] += (num%j==0)
        if c[j] > 1:
            h = False

    if num == i:
        if c[num] >= 1:
            h = False
        c[num] += 1

    if h==False:
        break

if h == True:
    print('pairwise coprime')
elif r == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

from math import gcd

r = a[0]
for i in a:
    r = gcd(r, i)

c = [0 for _i in range(10**6+1)]
h = True
for i in a:
    if i==1:
        continue
    num = i
    for j in range(2, int(num**0.5)+2):
        c[j] += (num%j==0)
        if c[j] > 1:
            h = False

    if num == i:
        if c[num] >= 1:
            h = False
        c[num] += 1

    if h==False:
        break

if h == True:
    print('pairwise coprime')
elif r == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd


def make_prime(n):
    array = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt = cnt + 1
                temp = temp // i
            array[i] = cnt

    if temp != 1:
        array[temp] = 1

    if array == {}:
        array[n] = 1

    return array


N = int(input())
A = list([int(x) for x in input().split()])

result = []
before = -1
for i in A:
    result.extend(list(make_prime(i).keys()))
    if before == -1:
        before = i
    else:
        before = gcd(i, before)

if len(set(result)) == len(result):
    print('pairwise coprime')
    exit()

if before == 1:
    print('setwise coprime')
    exit()

print('not coprime')

Submission status: Wrong Answer

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

from math import gcd

r = a[0]
for i in a:
    r = gcd(r, i)

c = [0 for _i in range(10**6+1)]
h = True
for i in a:
    if i==1:
        continue
    num = i
    for j in range(2, int(num**.5)+2):
        if num%j == 0:
            c[j] += 1
            if c[j] >= 2:
                h = False

    if num == i:
        if c[num] >= 1:
            h = False
        else:
            c[num] += 1

    if h==False:
        break

if h == True:
    print('pairwise coprime')
elif r == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


def main():
    from math import gcd
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    max_a = 10 ** 6
    numbers = [0 for _ in range(max_a + 1)]

    for ai in a:
        numbers[ai] += 1

    is_pairwise = True

    for i in range(2, max_a + 1):
        count = 0

        for j in range(i, max_a + 1, i):
            count += numbers[j]

            if count > 1:
                is_pairwise = False

        if is_pairwise:
            print("pairwise coprime")
            exit()

    value_gcd = 0

    for i in range(n):
        value_gcd = gcd(value_gcd, a[i])

        if value_gcd == 1:
            print("setwise coprime")
            exit()

    print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


def main():
    from math import gcd
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    max_a = 10 ** 6
    numbers = [0 for _ in range(max_a + 1)]

    for ai in a:
        numbers[ai] += 1

    is_pairwise = True

    for i in range(2, max_a + 1):
        count = 0

        for j in range(i, max_a + 1, i):
            count += numbers[j]

            if count > 1:
                is_pairwise = False

        if is_pairwise:
            print("pairwise coprime")
            exit()

    value_gcd = 0

    for a1, a2 in zip(a, a[1:]):
        value_gcd = gcd(value_gcd, gcd(a1, a2))

        if value_gcd == 1:
            print("setwise coprime")
            exit()

    print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


def main():
    from math import gcd
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    max_a = 10 ** 6
    n = max_a
    numbers = [0 for _ in range(max_a + 1)]

    for ai in a:
        numbers[ai] += 1

    is_pairwise = True

    for i in range(2, max_a + 1):
        count = 0

        for j in range(i, max_a + 1, i):
            count += numbers[j]

            if count > 1:
                is_pairwise = False

        if is_pairwise:
            print("pairwise coprime")
            exit()

    value_gcd = 0

    for a1, a2 in zip(a, a[1:]):
        value_gcd = gcd(value_gcd, gcd(a1, a2))

        if value_gcd == 1:
            print("setwise coprime")
            exit()

    print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

from math import gcd

r = a[0]
for i in a[1:]:
    r = gcd(r, i)

c = [0 for _i in range(10**6+1)]
h = True
for i in a:
    if i==1:
        continue
    num = i
    for j in range(2, int(num**.5)+1):
        if num%j == 0:
            c[j] += 1
            num //= j
            if c[j] >= 2:
                h = False

    if num == i:
        if c[num] >= 1:
            h = False
        else:
            c[num] += 1
    if h==False:
        break

if h == True:
    print('pairwise coprime')
elif r == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

from math import gcd

r = a[0]
for i in a[1:]:
    r = gcd(r, i)

c = [0 for _i in range(10**6+1)]
h = True
for i in a:
    num = i
    for j in range(2, int(num**.5)+1):
        if num%j == 0:
            c[j] += 1
            while num%j == 0:
                num //= j
            if c[j] >= 2:
                h = False

    if num == i:
        c[num] += 1
        if c[num] >= 2 and num > 1:
            h = False
    if h==False:
        break

if h == True:
    print('pairwise coprime')
elif r == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

from math import gcd

r = a[0]
for i in a[1:]:
    r = gcd(r, i)

c = [0 for _i in range(10**6+1)]
h = True
for i in a:
    num = i
    for j in range(2, int(num**.5)+1):
        if num%j == 0:
            c[j] += 1
            while num%j == 0:
                num //= j
            if c[j] >= 2:
                h = False

    if num == i:
        c[num] += 1
        if c[num] >= 2:
            h = False
    if h==False:
        break

if h == True:
    print('pairwise coprime')
elif r == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

from math import gcd

r = a[0]
for i in a[1:]:
    r = gcd(r, i)

c = [0 for _i in range(10**6+1)]
h = True
for i in a:
    num = i
    for j in range(2, int(num**.5)+1):
        if num%j == 0:
            c[j] += 1
            num //= j
            if c[j] >= 2:
                h = False

    if num == i:
        c[num] += 1
        if c[num] >= 2:
            h = False
    if h==False:
        break

if h == True:
    print('pairwise coprime')
elif r == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

from math import gcd

r = a[0]
for i in a[1:]:
    r = gcd(r, i)

c = [0 for _i in range(10**6+1)]
h = True
for i in a:
    num = i
    for j in range(2, int(num**.5)+1):
        if num%j == 0:
            c[j] += 1
            num //= j
            if c[j] >= 2:
                h = False
                break
    if num == i:
        c[num] += 1
        if c[num] >= 2:
            h = False
            break 

if h == True:
    print('pairwise coprime')
elif r == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

from math import gcd

r = a[0]
for i in a[1:]:
    r = gcd(r, i)

c = [0 for _i in range(10**6+1)]
h = True
for i in a:
    num = i
    for j in range(2, int(num**.5)+1):
        if num%j == 0:
            c[j] += 1
            if c[j] >= 2:
                h = False
                break
    if num == i:
        c[num] += 1
        if c[num] >= 2:
            h = False
            break 

if h == True:
    print('pairwise coprime')
elif r == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

from math import gcd

r = a[0]
for i in a[1:]:
    r = gcd(r, i)

c = [0 for _i in range(10**6+1)]
h = True
for i in a:
    num = i
    for j in range(2, int(num**.5)+1):
        if num%j == 0:
            c[j] += 1
            if c[j] >= 2:
                h = False
                break
            else:
                num //= j
        if num == i:
            c[num] += 1
            if c[num] >= 2:
                h = False
                break 
if h == True:
    print('pairwise coprime')
elif r == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

from math import gcd

r = a[0]
for i in a[1:]:
    r = gcd(r, i)

c = [0 for _i in range(10**6+1)]
h = True
for i in a:
    num = i
    for j in range(2, int(num**.5)+1):
        if num%j == 0:
            c[j] += 1
            if c[j] >= 2:
                h = False
                break
            else:
                num //= j
        if num == i:
            c[num] += 1
            if c[num] >= 2:
                h = False
                break 
if h == True:
    print('pairwise cprime')
elif r == 1:
    print('setwise coprime')
else:
    print('no coprime')

Submission status: Wrong Answer

Solution code:
from functools import lru_cache


@lru_cache(maxsize=None)
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:
                d[j] += 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()

Submission status: Wrong Answer

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()
    mm =m
    for i in pri_num:
        
        if i >mm:
            break
        elif mm %i==0:
            pf.add(i)
            mm //=i
    if mm ==m:
        pf.add(m)
    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()))
intersect =set()
pair_w =set()

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

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

#pairwise coprimeの判定
else:
    for a in A:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            pair_w.add(0)
            break #共通要素があったらpair_wではない→set_w
        else:
            pair_w.add(1)
        intersect |=aa

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

Submission status: Wrong Answer

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()
    mm =m
    for i in pri_num:
        
        if i >mm:
            break
        elif mm %i==0:
            pf.add(i)
            mm //i
    if mm ==m:
        pf.add(m)
    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()))
intersect =set()
pair_w =set()

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

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

#pairwise coprimeの判定
else:
    for a in A:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            pair_w.add(0)
            break #共通要素があったらpair_wではない→set_w
        else:
            pair_w.add(1)
        intersect |=aa

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

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
num_lis = list(map(int, input().split()))
c1 = False
c2 = False

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

hoge = 0
for i in num_lis:
  hoge = gcd(hoge, i)
if hoge == 1:
  c1 = True

if c1:
  d_lis = osa_k(max(num_lis))
  tmp = set()
  for i in num_lis:
    num = i
    new_tmp = set()
    while num > 1:
      d = d_lis[num]
      new_tmp.add(d)
      num //= d
    for j in new_tmp:
      if j in tmp:
        break
      else:
        tmp.add(j)
        c2 = True
    else:
      continue
    break

if c2:
  print("pairwise coprime")
elif c1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True
c2 = True

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

hoge = 0
for i in num_lis:
  hoge = gcd(hoge, i)
if hoge > 1:
  c1 = False

if c1:
  d_lis = osa_k(max(num_lis))
  tmp = set()
  for i in num_lis:
    num = i
    new_tmp = set()
    while num > 1:
      d = d_lis[num]
      new_tmp.add(d)
      num //= d
    print(new_tmp)
    for j in new_tmp:
      if j in tmp:
        c2 = False
        break
      else:
        tmp.add(j)
    else:
      continue
    break
else:
  c2 = False

if c2:
  print("pairwise coprime")
elif c1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True #setwise
c2 = True #pairwise

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

hoge = 0
for i in num_lis:
  hoge = gcd(hoge, i)
if hoge > 1:
  c1 = False

if c1:
  d_lis = osa_k(max(num_lis))
  tmp = set()
  for i in num_lis:
    num = i
    new_tmp = set()
    while num > 1:
      d = d_lis[num]
      new_tmp.add(d)
      num //= d
    for j in new_tmp:
      if j in tmp:
        c2 = False
        break
      tmp.add(j)

if c2:
  print("pairwise coprime")
elif c1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True #setwise
c2 = True #pairwise

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

hoge = 0
for i in num_lis:
  hoge = gcd(hoge, i)
if hoge > 1:
  c1 = False

if c1:
  d_lis = osa_k(max(num_lis))
  tmp = set()
  for i in num_lis:
    num = i
    new_tmp = set()
    while num > 1:
      d = d_lis[num]
      new_tmp.add(d)
      num //= d
    for j in new_tmp:
      if j in tmp:
        c2 = False
        break
      tmp.add(j)
    else:
      continue
    break

if c2:
  print("pairwise coprime")
elif c1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True #setwise
c2 = True #pairwise

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

hoge = 0
for i in num_lis:
  hoge = gcd(hoge, i)
if hoge > 1:
  c1 = False

if c1:
  d_lis = osa_k(10**6+10)
  tmp = set()
  for i in num_lis:
    num = i
    new_tmp = set()
    while num > 1:
      d = d_lis[num]
      new_tmp.add(d)
      num //= d
    for j in new_tmp:
      if j in tmp:
        c2 = False
        break
      tmp.add(j)
    else:
      continue
    break

if c2:
  print("pairwise coprime")
elif c1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd

N = int(input())
num_lis = list(map(int, input().split()))
c1 = True #setwise
c2 = True #pairwise

def osa_k(max_num):
  lis = [i for i in range(max_num+1)]
  p = 2
  while p**2 <= max_num:
    if lis[p] == p:
      for q in range(2*p, max_num+1, p):
        if lis[q] == q:
          lis[q] = p
    p += 1
  return lis

hoge = 0
for i in num_lis:
  hoge = gcd(hoge, i)
if hoge > 1:
  c1 = False

if c1:
  d_lis = osa_k(10**6+10)
  tmp = set()
  for i in num_lis:
    num = i
    new_tmp = set()
    while num > 1:
      d = d_lis[num]
      new_tmp.add(d)
      num //= d
    for j in new_tmp:
      if j in tmp:
        c2 = False
        break
      else:
        tmp.add(j)
    else:
      continue
    break

if c2:
  print("pairwise coprime")
elif not c2 and c1:
  print("setwise coprime")
else:
  print("not coprime")