Problem:


Score : 500 points

Problem Statement

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

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

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

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

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

Constraints

2 \leq N \leq 10^6

1 \leq A_i\leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

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

Sample Input 1

3
3 4 5

Sample Output 1

pairwise coprime

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

Sample Input 2

3
6 10 15

Sample Output 2

setwise coprime

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

Sample Input 3

3
6 10 16

Sample Output 3

not coprime

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



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Runtime Error

Solution code:
import collections
N = int(input())
A = [int(_) for _ in input().split()]


def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a


d = collections.defaultdict(int)
for a in A:
    for x in prime_factorize(a):
        d[x] += 1
e = max(d.values())
if e == 1:
    ans = 'pairwise coprime'
elif e == N:
    ans = 'not coprime'
else:
    ans = 'setwise coprime'
print(ans)

Submission status: Runtime Error

Solution code:
import collections
N = int(input())
A = [int(_) for _ in input().split()]


class Prime:
    # https://qiita.com/daikw/items/f48d6ac374255763463d
    seed_primes = [
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
        71, 73, 79, 83, 89, 97
    ]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

        :param n:
        :return: boolean
        """
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed + 1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes


d = collections.defaultdict(int)
for a in A:
    factors = Prime().find_factors(a).keys()
    for x in factors:
        d[x] += 1
e = max(d.values())
if e == 1:
    ans = 'pairwise coprime'
elif e == N:
    ans = 'not coprime'
else:
    ans = 'setwise coprime'
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np


def get_primes(a=10 ** 6):
    table = np.ones(a + 1)
    table[:2] = False
    for i in range(2, a):
        table[i + i::i] = False
    primes = np.where(table == True)[0]
    return primes


def main():
    n = int(input())
    A = np.array(input().split(), dtype=np.int64)
    primes = get_primes(A.max())

    if A.max() == 1:
        print("pairwise coprime")

    fact_counts = A.reshape([-1, 1]) % primes.reshape([1, -1]) == 0
    count = fact_counts.sum(axis=0).max()

    if count == 1:
        print("pairwise coprime")
    elif count != n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np


def get_primes(a=10**6):
    table = np.ones(a+1)
    table[:2] = False
    for i in range(2, a):
        table[i+i::i] = False
    primes = np.where(table==True)[0]
    return primes


def main():
    n = int(input())
    A = np.array(input().split(), dtype=np.int64)
    primes = get_primes(A.max())
    
    if A.max() == 1:
        print("pairwise coprime")

    fact_counts = A.reshape([1, -1]) % primes.reshape([-1, 1]) == 0
    count = fact_counts.sum(axis=1).max()

    if count == 1:
        print("pairwise coprime")
    elif count != n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import math


N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


def eatosthenes(N):
    prime = []
    D = [1] * (N + 1)

    for i in range(2, N + 1):
        if D[i] != 1:
            continue
        for j in range(N // i + 1):
            if D[i * j] == 1:
                D[i * j] = i
        prime.append(i)

def main():
    N = int(sys.stdin.readline().rstrip())
    A = [int(x) for x in sys.stdin.readline().rstrip().split()]

    maxA = max(A)
    primelist = eatosthenes(maxA)

    # 1 <= a <= maxA までの、要素の登場回数
    C = [0] * (maxA + 1)
    for a in A:
        C[a] += 1

    pc = True

    # p の倍数である個数をカウントする
    for p in primelist:
        cnt = 0
        for k in range(maxA // p + 1):
            cnt += C[k * p]

        # k*p となるような要素が2個以上あったら、pairwise coprime ではない
        if cnt > 1:
            pc = False

    if pc:
        print("pairwise coprime")
        return

    GCD = A[0]
    for i in range(1, N):
        GCD = math.gcd(GCD, A[i])

    if GCD == 1:
        print("setwise coprime")
        return

    print("not coprime")


main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def get_primes(a=10**6):
    table = np.ones(a+1)
    table[:2] = False
    for i in range(2, a):
        table[i+i::i] = False
    primes = np.where(table==True)[0]
    return primes


def main():
    n = int(input())
    A = np.array(input().split(), dtype=np.int64)
    primes = get_primes(A.max())

    if A.max() == 1:
        print("pairwise coprime")

    fact_counts = (A.reshape([1, -1]) % primes.reshape([-1, 1])) == 0
    print(1)
    return
    if count == 1:
        print("pairwise coprime")
    elif count != n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def get_primes(a=10**6):
    table = np.ones(a+1)
    table[:2] = False
    for i in range(2, a):
        table[i+i::i] = False
    primes = np.where(table==True)[0]
    return primes


def main():
    n = int(input())
    A = np.array(input().split(), dtype=np.int64)
    primes = get_primes(A.max())

    if A.max() == 1:
        print("pairwise coprime")

    fact_counts = (A.reshape([1, -1]) % primes.reshape([-1, 1])) == 0

    if count == 1:
        print("pairwise coprime")
    elif count != n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def get_primes(a=10**6):
    table = np.ones(a+1)
    table[:2] = False
    for i in range(2, a):
        table[i+i::i] = False
    primes = np.where(table==True)[0]
    return primes


def main():
    n = int(input())
    A = np.array(input().split(), dtype=np.int64)
    primes = get_primes(A.max())
    
    if A.max() == 1:
        print("pairwise coprime")

    fact_counts = (A.reshape([1, -1]) % primes.reshape([-1, 1])) == 0
    count = fact_counts.sum(axis=1).max()

    if count == 1:
        print("pairwise coprime")
    elif count != n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def get_primes(a=10**6):
    table = np.ones(a+1)
    table[:2] = False
    for i in range(2, a):
        table[i+i::i] = False
    primes = np.where(table==True)[0]
    return primes


def main():
    n = int(input())
    A = np.array(input().split(), dtype=np.int64)
    primes = get_primes(A.max())

    fact_counts = A.reshape([1, -1]) % primes.reshape([-1, 1]) == 0
    count = fact_counts.sum(axis=1).max()

    if count == 1:
        print("pairwise coprime")
    elif count != n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
aa=list(map(int,input().split()))
a=[x for x in aa if x!=1]
n=len(a)
# 素因数分解
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
tmp=[i for i,j in factorization(min(a))]
not_flg=False
for t in tmp:
  flg=True
  for x in a:
    if x%t==0:
      pass
    else:
      flg=False
      break
  if flg:
    not_flg=flg
    break
if not_flg:
  print('not coprime')
  exit()
#if n>78499:
if n>99999:
  print('setwise coprime')
  exit()
ary=set(())
for x in a:
  tmp={i for i,j in factorization(x)}
  for t in tmp:
    if t in ary:
      print('setwise coprime')
      exit()
    else:
      ary.add(t)
print('pairwise coprime')

Submission status: Runtime Error

Solution code:
import math
NOTCOM = "not coprime"
SETWISE = "setwise coprime"
PAIRWISE = "pairwise coprime"
MAX_A = 100

def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = [0] * MAX_A
    for a in A:
        c[a] += 1
    pairwse = True
    for i in range(2, MAX_A):
        cnt = 0
        for j in range(i, MAX_A, i):
            cnt += c[j]
        if cnt > 1: pairwse = False
    if pairwse:
        return PAIRWISE
    
    allgcd = A[0]
    for a in A:
        allgcd = math.gcd(allgcd, a)
    if allgcd == 1: return SETWISE
    return NOTCOM

print(main())

Submission status: Runtime Error

Solution code:
n=int(input())
aa=list(map(int,input().split()))
a=[x for x in aa if x!=1]
n=len(a)
# 素因数分解
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
tmp=[i for i,j in factorization(min(a))]
not_flg=False
for t in tmp:
  flg=True
  for x in a:
    if x%t==0:
      pass
    else:
      flg=False
      break
  if flg:
    not_flg=flg
    break
if not_flg:
  print('not coprime')
  exit()
if n>78498:
  print('setwise coprime')
  exit()
ary=set(())
for x in a:
  tmp={i for i,j in factorization(x)}
  for t in tmp:
    if t in ary:
      print('setwise coprime')
      exit()
    else:
      ary.add(t)
print('pairwise coprime')

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append(i)

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

    return arr


def main():
    n = int(input())
    A = list(map(int, input().split()))
    fact_dict = defaultdict(int)
    for a in A:
        facts = factorization(a)
        for fact in facts:
            fact_dict[fact] += 1

    count = max(fact_dict.values())
    if count == 1:
        print("pairwise coprime")
    elif count != n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys,math
n=int(input())
a=list(map(int,input().split()))
numbers={}
flag=0
for i in range(n):
  if a[i] in numbers:
    numbers[a[i]]+=1
  else:
    numbers[a[i]]=1
while pointer in range(2,10**6+1):
  count=0
  pointer2=pointer
  while pointer2<10**6+1:
    if pointer2 in numbers:
      count+=numbers[pointer2]
    pointer2+=pointer
  if count>=2:
    flag=1
    break
if flag==0:
  print('pairwise coprime')
  sys.exit()
ans=a[0]
for i in range(1,n):
  ans=math.gcd(a[i],ans)
if ans==1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from numba import njit, b1, i4, i8, f8

@njit(cache = True)
def get_prime_factors(x):
    return [2, 3]

@njit
def main():
    df = {"2":0, "3":0}
    
    
    for ai in a:
        primes = get_prime_factors(ai)
        for prime in primes:
            df[prime] += 1
    if df.values():
        val = max(df.values())
        if val == 1:
            print("pairwise coprime")
        elif val == n:
            print("not coprime")
        else:
            print("setwise coprime")
    else:
        print("pairwise coprime")

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from numba import njit, b1, i4, i8, f8

@njit(cache = True)
def get_prime_factors(x):
    return [2, 3]

@njit
def main():
    df = defaultdict(lambda : 0)
    
    
    for ai in a:
        primes = get_prime_factors(ai)
        for prime in primes:
            df[prime] += 1
    if df.values():
        val = max(df.values())
        if val == 1:
            print("pairwise coprime")
        elif val == n:
            print("not coprime")
        else:
            print("setwise coprime")
    else:
        print("pairwise coprime")

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from numba import njit, b1, i4, i8, f8

@njit(cache = True)
def get_prime_factors(x):
    out = set()
    if x < 1:
        return out
    while not x%2:
        out.add(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.add(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.add(x)
    return out

@njit
def main():
    df = defaultdict(lambda : 0)
    
    
    for ai in a:
        primes = get_prime_factors(ai)
        for prime in primes:
            df[prime] += 1
    if df.values():
        val = max(df.values())
        if val == 1:
            print("pairwise coprime")
        elif val == n:
            print("not coprime")
        else:
            print("setwise coprime")
    else:
        print("pairwise coprime")

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from numba import njit, b1, i4, i8, f8
import numpy as np

@njit
def get_prime_factors(x):
    out = set()
    if x < 1:
        return out
    while not x%2:
        out.add(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.add(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.add(x)
    return out

@njit
def main():
    n = int(input())
    a = list(map(int, input().split()))
    df = defaultdict(lambda : 0)
    
    
    for ai in a:
        primes = get_prime_factors(ai)
        for prime in primes:
            df[prime] += 1
    if df.values():
        val = max(df.values())
        if val == 1:
            print("pairwise coprime")
        elif val == n:
            print("not coprime")
        else:
            print("setwise coprime")
    else:
        print("pairwise coprime")


main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from numba import njit

@njit
def get_prime_factors(x):
    out = set()
    if x < 1:
        return out
    while not x%2:
        out.add(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.add(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.add(x)
    return out

@njit
def main():
    n = int(input())
    a = list(map(int, input().split()))
    df = defaultdict(lambda : 0)
    
    
    for ai in a:
        primes = get_prime_factors(ai)
        for prime in primes:
            df[prime] += 1
    if df.values():
        val = max(df.values())
        if val == 1:
            print("pairwise coprime")
        elif val == n:
            print("not coprime")
        else:
            print("setwise coprime")
    else:
        print("pairwise coprime")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from numba import njit, b1, i4, i8, f8

@njit((i8, i8[:]), cache=True)
def get_prime_factors(x):
    out = set()
    if x < 1:
        return out
    while not x%2:
        out.add(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.add(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.add(x)
    return out

@njit((i8, i8, i8[:]), cache=True)
def main():
    n = int(input())
    a = list(map(int, input().split()))
    df = defaultdict(lambda : 0)
    
    
    for ai in a:
        primes = get_prime_factors(ai)
        for prime in primes:
            df[prime] += 1
    if df.values():
        val = max(df.values())
        if val == 1:
            print("pairwise coprime")
        elif val == n:
            print("not coprime")
        else:
            print("setwise coprime")
    else:
        print("pairwise coprime")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from numba import njit, b1, i4, i8, f8

def get_prime_factors(x):
    out = set()
    if x < 1:
        return out
    while not x%2:
        out.add(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.add(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.add(x)
    return out


def main():
    n = int(input())
    a = list(map(int, input().split()))
    df = defaultdict(lambda : 0)
    
    @njit((i8, i8, i8[:]), cache=True)
    for ai in a:
        primes = get_prime_factors(ai)
        for prime in primes:
            df[prime] += 1
    if df.values():
        val = max(df.values())
        if val == 1:
            print("pairwise coprime")
        elif val == n:
            print("not coprime")
        else:
            print("setwise coprime")
    else:
        print("pairwise coprime")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

x = max(A)
hurui = [x]*(x+1)
for i in range(2, x+1):
    for j in range(i, x+1, i):
        hurui[j] = min(i, hurui[j])

cnt = Counter()
for i in range(N):
    num = A[i]
    while num > 1:
        x = hurui[num]
        while num%x == 0:
            num //= x
        cnt[x] += 1

a = cnt.most_common(1)[0][1]
if a == 1:
    print("pairwise coprime")
elif a < N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

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

x = max(A)
hurui = [x]*(x+1)
for i in range(2, x+1):
    for j in range(i, x, i):
        hurui[j] = min(i, hurui[j])

cnt = Counter()
for i in range(N):
    num = A[i]
    while num > 1:
        x = hurui[num]
        while num%x == 0:
            num //= x
        cnt[x] += 1

a = cnt.most_common(1)[0][1]
if a == 1:
    print("pairwise coprime")
elif a < N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

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

x = max(A)
hurui = [x]*(x+1)
for i in range(2, N+1):
    for j in range(i, x, i):
        hurui[j] = min(i, hurui[j])

cnt = Counter()
for i in range(N):
    num = A[i]
    while num > 1:
        x = hurui[num]
        while num%x == 0:
            num //= x
        cnt[x] += 1

a = cnt.most_common(1)[0][1]
if a == 1:
    print("pairwise coprime")
elif a < N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

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

def lcm(a,b): 
    return (a*b) // math.gcd(a,b) 
for _ in range(1):
    n=inin()
    l=ain()
    f1,f2=0,0
    gc=l[0]
    d=dd(int)
	if(l.count(1)>0):gc=1
    else:
      for i in range(1,n):
        gc=math.gcd(gc,l[i])
    if(gc!=1):print("not coprime")
    else:
        lp=SieveOfEratosthenes(int(math.sqrt(max(l)))+2)
        for i in l:
          if(i!=1):
            for j in lp:
              if(i%j==0):
                if(d[j]==1):
                  f1=1
                  break
                d[j]=1
            if(f1):break
        if(f1):
            print("setwise coprime")
        else:
            print("pairwise coprime")
        
        
    
    
    

 
    
    
    
    
        
        
    
    
    
    


    




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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def prime_factor(n):
    factors = []
    while n%2==0:
        factors.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            factors.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        factors.append(n)
    return set(factors)

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

n=int(input())
L=list(map(int,input().split()))
val = L[0]
for i in range(1,n):
    val=math.gcd(L[i],val)
if val!=1:
    print('not coprime')
    sys.exit()

d={}
for i in range(n):
    factors = prime_factor(L[i])
    for j in factors:
        if j not in d.keys():
            d[j]=1
        else:
            print('setwise coprime')
            sys.exit()
print('pairwise coprime')

Submission status: Runtime Error

Solution code:
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
input()
u = set()
i = None
a = [int(x) for x in input().split() if x > '1']
if len(a) > 1:
  for x in :
    s = set()
    while x > 1:
      p = spf[x]
      if p in u:
        r = 'setwise'
      s.add(p)
      x //= p
    u |= s
    i = (i or s) & s
  if i:
    r = 'not'
print(r, 'coprime')

Submission status: Runtime Error

Solution code:
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
def main():
    n = int(input())
    a = [int(t) - 1 for t in input().split()]
    b = [1] * (n + 1)
    for i in range(n, 1, -1):
        b[i - 1] = lcm(b[i], a[i - 1])
    flag = 1
    for i in range(n - 1):
        if math.gcd(a[i], b[i + 1]) != 1:
            flag = 0
            break
    g = a[0]
    for i in range(n):
        g = math.gcd(g, a[i])
    if flag == 0:
        if g == 1:
            flag = 2
    ans = "not coprime"
    if flag == 1:
        ans = "pairwise coprime"
    elif flag == 2:
        ans = "setwise coprime"
    print(ans)
main()

Submission status: Runtime Error

Solution code:
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
input()
u = set()
i = None
for x in map(int, input().split()):
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
  i = (i or s) & s
print(('not' if i else r) + ' coprime')

Submission status: Runtime Error

Solution code:
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
input()
u = set()
i = None
for x in map(int, input().split()):
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
  i = (i or s) & s
print('not' if i else r, 'coprime')
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
input()
u = set()
i = None
for x in map(int, input().split()):
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
  i = (i or s) & s
print(('not' if i else r) + ' coprime')

Submission status: Runtime Error

Solution code:
import math
from collections import defaultdict

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

M= 10**6 +1
S = [1] *M
for i in range(2, M):
    if S[i] == 1:
        for j in range(i, M, i):
            if S[j] == 1:
                S[j] = i

isPairwise = True
f = [0] *M
for i in range(0, N):
    p = S[A[i]]
    if f[p] > 0:
        isPairwise = False
        break
    f[p] += 1

gcd=A[0]
for i in range(1, N):
    gcd = math.gcd(gcd, A[i])
isSetwise = (gcd == 1)

if isPairwise:
    z = 'pairwise coprime'
elif isSetwise:
    z = 'setwise coprime'
else:
    z = 'not coprime'
print(z)

Submission status: Runtime Error

Solution code:
import math
from collections import defaultdict

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

M= 10**6 +1
S = [1] *M
for i in range(2, M):
    if S[i] == 1:
        for j in range(i, M, i):
            if S[j] == 1:
                S[j] = i

isPairwise = True
f = [0] *M
for i in range(0, N):
    p = S[A[i]]
    if f[p] > 0:
        isPairwise = False
        break
    f[p] += 1

gcd=A[0]
for i in range(1, N):
    gcd = math.gcd(gcd, A[i])
isSetwise = (gcd == 1)

if isPairwise:
    z = 'pairwise coprime'
elif isSetwise:
    z = 'setwise coprime'
else:
    z = 'not coprime'
print(z)