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: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
pairwise_flag = 1
for i in range(N-1):
  for j in range(i+1,N):
    if(math.gcd(A[i],A[j]) == 1):
      continue
    else:
      pairwise_flag = 0
      break
if(pairwise_flag == 1):
  print("pairwise coprime")
else:
  a = A[0]
  for i in range(1,N):
    a = math.gcd(a,A[i])
  if(a==1):
    print("setwise coprime")
  else:
    print("not coprime")

Submission status: Time Limit Exceeded

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


def PrimeFactor(n):
    ret=set()
    for i in range(2,int(-(-n**0.5//1))+1):
        if i!=2 and i%2==0:
            continue
        cnt=0
        while n%i==0:
            cnt+=1
            n//=i
        if cnt!=0:
            ret.add(i)
    if n!=1:
        ret.add(n)
    return ret

AND = set(PrimeFactor(A[0]))
d = {}
ans = -1
fin = False
for a in A:
    l = PrimeFactor(a)
    AND = AND & set(l)
    for x in l:
        if x in d:
            if d[x] >= 1:
                ans = 2
        else:
            d[x] = 1



if len(AND) == 0 and ans == -1:
    print("pairwise coprime")
elif len(AND)==0:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

# def
def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

def str_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

def int_map():
    return map(int,input().split())

def int_list():
    return list(map(int,input().split()))

def print_space(l):
    return print(" ".join([str(x) for x in l]))

# import
import numpy as np
import collections as col

import math
from functools import reduce

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

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

# main code
N = int(input())
A = int_list()

AA = [x for x in A if not x == 1]

b = gcd(*A)

s = set()

if not b == 1:
    print("not coprime")
else:
    num = 0
    for aa in AA:
        v = factorization(aa)
        vnum = len(v)
        num += vnum
        for i in range(0,vnum):
            s.add(v[i][0])
        
        if not num == len(s):
            print("setwise coprime")
            exit()
    
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
N = int( input() )
A = sorted( list(map(int, input().split())))
ans = A[0]
# http://www.ysr.net.it-chiba.ac.jp/~yashiro/sosu/
P = list( map( int, "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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997".split(" ")))
L = []
def factorization(n):
    temp = n
    K = []
    for p in P:
      if p > int(-(-n**0.5//1))+1:
        break
      if temp%p==0:
        cnt=0
        while temp % p == 0:
          cnt+=1
          temp //= p
        if p in L:
          return True
        K.append( p )
    if temp!=1:
      if temp in L:
        return True
      K.append( temp )
    if L==[]:
      L.append( n )
    L.extend( K )
    return False

cnt = 0
for i in range(1, N):
    ans = math.gcd(ans, A[i])
    if ans == 1:
      break
    else:
      cnt += 1
if ans != 1:
  ret = "not coprime"
else:
  if cnt > 0:
    ret = "setwise coprime"
  else:
    ret = "pairwise coprime"
    for a in A:
      if factorization( a ):
        ret = "setwise coprime"
        break
print( ret )

Submission status: Time Limit Exceeded

Solution code:
import math

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

    pairwise_flag=0
    setwise_flag=1

    for i in range(N-1):
        g=A[i]
        for j in range(i+1,N):
            g=math.gcd(g,A[j])

        if i==0 and g==1:
            setwise_flag=0

        if g!=1:
            pairwise_flag=1
            break

    if pairwise_flag==0:
        print("pairwise coprime")
    elif setwise_flag==0:
        print("setwise coprime")
    else:
        print("not coprime")

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import math
    def primes(n):
        ass = []
        is_prime = [True] * (n + 1)
        is_prime[0] = False
        is_prime[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if not is_prime[i]:
                continue
            for j in range(i * 2, n + 1, i):
                is_prime[j] = False
        for i in range(len(is_prime)):
            if is_prime[i]:
                ass.append(i)
        return ass

    def divisor(n):
        ass = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                if i != 1:
                    ass.append(i)
                if i ** 2 == n:
                    continue
                ass.append(n // i)
        return ass


    n = int(input())
    a = list(map(int, input().split()))
    pair = False
    divisors = set(divisor(a[0]))
    ggcd = a[0]
    for i in range(1, n):
        divs = set(divisor(a[i]))
        if len(divs & divisors) != 0:
            pair = True
        else:
            divisors = set(list(divisors) + list(divs))
        ggcd = math.gcd(ggcd, a[i])
    if ggcd != 1:
        print("not coprime")
    else:
        if pair:
            print("setwise coprime")
        else:
            print("pairwise coprime")
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n=int(input())

A=list(map(int,input().split()))
from math import sqrt
def eratosu(n):
  if not isinstance(n,int):
    raise TypeError("nがint型になってねえぞ")
  if n<2:
    raise ValueError('nが2よりちっちぇえぞ')
  prime = []
  limit = sqrt(n)
  data = [i+1 for i in range(1, n)]  #2,3,4,...,n
  while True:
    p = data[0]
    if limit <= p:
        return prime + data
    prime.append(p)
    data = [e  for e in data if e % p != 0]
PRIME=eratosu(10**6+10)
@lru_cache(maxsize=10**10)
def bunkai(n):
    if n==1:return []
    ans=[]
    temp=n
    #そんな早くしなくてよかったり、何回もするわけじゃないなら、
    #for i in range(2,int(sqrt(n))+1): とかで
    primelist= PRIME
    for i in primelist:
        if i>sqrt(n):break
        if temp % i ==0:
            ji=0
            while temp%i==0:
                ji+=1
                temp//=i
            ans.append(i)
    if ans==[]:return([n])  #素数のとき
    if temp!=1:
        ans.append(temp)  #4*5882353とか
    return ans

flag=1
seen={i:0 for i in PRIME}
#print(bunkai(3))
for i in A:
    for l in bunkai(i):
        now=l
        if now==1:continue
        if seen[now]!=0:
            flag=0
        seen[now]+=1
if flag:
    print("pairwise coprime")
elif max(seen.values())!=n:
    print("setwise coprime")
else:
    print("not coprime")

#print(seen)

Submission status: Time Limit Exceeded

Solution code:
import math

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


def get_sieve_of_eratosthenes(n):
    if n < 2:
        return []
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


f_l = get_sieve_of_eratosthenes(A_L[-2])

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

Submission status: Time Limit Exceeded

Solution code:
import math 
def findMaxGCD(arr, n): 
    high = max(arr) 
    divisors = [0] * (high + 1) 
    for i in range(n) : 

        for j in range(1, int(math.sqrt(arr[i])) + 1): 

            if (arr[i] % j == 0) : 

                divisors[j] += 1
                if (j != arr[i] // j): 
                    divisors[arr[i] // j] += 1
                    
    pairwise_coprime=True
    setwise_coprime=True
    for i in range(2,high):
        if (divisors[i] >= 2): 
            pairwise_coprime=False
        if divisors[i]==n:
            setwise_coprime=False
    if pairwise_coprime:
        print('pairwise coprime')
    elif setwise_coprime:
        print('setwise coprime')
    else:
        print('not coprime')
            
n = int(input())
a= [int(i) for i in input().split()]
findMaxGCD(a, n)

Submission status: Time Limit Exceeded

Solution code:
import math

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

cnt = 0
for i in range(0,N-1):
    for j in range(i+1,N):
        if math.gcd(A[i], A[j]) != 1:
            cnt += 1
            break


if cnt == 0:
    print('pairwise coprime')
    exit()

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

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

print('not coprime')

Submission status: Time Limit Exceeded

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

pl =[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

def fact(n):
    arr = []
    temp = n
    for i in pl:
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)
 
    if temp!=1:
        arr.append(temp)
 
    if arr==[]:
        arr.append(n)
 
    return arr
  
dp = [0]*(10**6)
#pairwise
for i in range(n):
    for j in fact(al[i]):
        dp[j] +=1

dpp = dp[2:]
 
if max(dpp)<=1:
    print("pairwise coprime")
 
elif max(dpp) ==n:
    print("not coprime")
    
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
##https://www.codechef.com/viewsolution/20131475

from math import gcd

def main():
    n = int(input())
    A = list(map(int , input().split()))
    N = max(A)+1

    sv = [i for i in range(N)]
    for i in range(2 , N) :
        if i * i >= N : break
        if sv[i] < i : continue
        for j in range(i * i , N , i) :
            sv[j] = min(sv[j] , i)

    def getPrimes(a) :
        pr = []
        if a == 1 : return pr
        pr.append(sv[a])
        while a > 1 :
            if sv[a] != pr[-1] :
                pr.append(sv[a])
            a //= sv[a]
        return pr

    np = [0] * N
    F = [0] * N


    for a in A :
        pr = getPrimes(a)
        for i in range(1 << len(pr)) :
            prod , nb = 1 , 0
            for j in range(len(pr)) :
                if i & (1<<j) :
                    prod *= pr[j]
                    nb += 1
            F[prod] += 1
            np[prod] = nb

    ans = 0
    for i in range(N) :
        cnt = F[i]
        cnt = (cnt * (cnt-1))//2
        if np[i] & 1 : ans -= cnt
        else : ans += cnt

    if ans == (n*(n-1))//2:
        print("pairwise coprime")
        exit()

    A.sort()
    d = A[0]

    for i in A:
        d = gcd(i,d)
        if d == 1 or d > 10**3:
            break

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

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
from functools import reduce
import math

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

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


pair = list(itertools.combinations(A, 2))

base = []
for i in range(len(pair)):
    if(pair[i][0] < pair[i][1]):
        base.append(pair[i])



for i in range(len(base)):
    if(math.gcd(base[i][0], base[i][1]) != 1):
        if(gcd_list(A) == 1):
            print("setwise coprime")
            break
        else:
            print("not coprime")
            break
    else:
        print("pairwise coprime")
        break

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
l = [0 for _ in range(10**6+2)]

import itertools
prime_list = []
def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
    
    return prime_list
    
eratosthenes_sieve(10**6+2)

def fac(n):
    temp = n
    for i in prime_list:
        if temp>= i:
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                l[i] += 1
        else:
            break
    if temp!=1:
        l[temp] += 1

for i in range(n):
    fac(a[i])
bit = 0
for i in l:
    if i==n:
        print("not coprime")
        exit()
    if i!=0 and i!=1:
        bit =1 

if bit==1:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections
n=int(input())
a=list(map(int,input().split()))
l=[]
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)

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

    return arr

for i in range(n):
    k=factorization(a[i])
    l.append(k)


l=list(itertools.chain.from_iterable(l))
c=len(l)
cl = collections.Counter(l)
cl1=cl.most_common()[0][1]
if c==n:print('pairwise coprime')
elif cl1<n:print('setwise coprime')
else:print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
l = input()
a = l.split(' ')

chk = 0

for i in range(n):
    for j in range(i+1,n):
        if(math.gcd(int(a[i]), int(a[j]))!=1):
            chk = 1
            break

tmp = int(a[0])

for i in range(1,n):
    tmp = math.gcd(tmp, int(a[i]))


if(chk==0):
    print("pairwise coprime")

elif(tmp==1):
    print("setwise coprime")

else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

ruiseki=1
for i in range(n):
  ruiseki=ruiseki*a[i]

if setwise_coprime(a)==1:
  for i in range(n):
    num=math.gcd(a[i],(ruiseki//a[i])%a[i])
    if num!=1:
      print("setwise coprime")
      sys.exit()
  print("pairwise coprime")
else:
  print("not coprime")
  sys.exit()

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()
used = [False] * (10**6+1)

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

input_list = sieve_of_erastosthenes(int(-(-10**3//1))+1)
prime_list = [i for i, b in enumerate(input_list) if b == True]

def factorization(n):
    arr = []
    temp = n
    for i in prime_list:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

# a.sort(reverse=True)
g = a[0]
arr = factorization(a[0])
for i in arr:
    used[i] = True

pair = True
for i in range(n-1):
    g = gcd(g, a[i+1])
    # 一度でも互いに素でない組合せが出たらpariwise coprimeではない
    if pair:
        arr = factorization(a[i+1])
        for i in arr:
            if i == 1: continue
            if used[i]: pair=False
            used[i] = True
if g > 1:
    print('not coprime')
    exit(0)
if not pair:
    print('setwise coprime')
    exit(0)
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
##https://www.codechef.com/viewsolution/20131475

from math import gcd

def main():
    n = int(input())
    A = list(map(int , input().split()))
    N = max(A)+1

    sv = [i for i in range(N)]
    for i in range(2 , N) :
        if i * i >= N : break
        if sv[i] < i : continue
        for j in range(i * i , N , i) :
            sv[j] = min(sv[j] , i)

    def getPrimes(a) :
        pr = []
        if a == 1 : return pr
        pr.append(sv[a])
        while a > 1 :
            if sv[a] != pr[-1] :
                pr.append(sv[a])
            a //= sv[a]
        return pr

    np = [0] * N
    F = [0] * N


    for a in A :
        pr = getPrimes(a)
        for i in range(1 << len(pr)) :
            prod , nb = 1 , 0
            for j in range(len(pr)) :
                if i & (1<<j) :
                    prod *= pr[j]
                    nb += 1
            F[prod] += 1
            np[prod] = nb

    ans = 0
    for i in range(N) :
        cnt = F[i]
        cnt = (cnt * (cnt-1))//2
        if np[i] & 1 : ans -= cnt
        else : ans += cnt

    if ans == (n*(n-1))//2:
        print("pairwise coprime")
        exit()

    A.sort()
    d = A[0]

    for i in A:
        d = gcd(i,d)
        if d == 1 or d > 10**4:
            break

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

main()

Submission status: Time Limit Exceeded

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()



def main():
	nn=II()
	A=LI()
	ans="pairwise coprime"

	n = 1000000
	primes = set(range(2, n+1))
	for i in range(2, int(n**0.5+1)):
		primes.difference_update(range(i*2, n+1, i))
	primes=list(primes)

	#print(primes)


	B=set(range(1,10**6+1))
	C=set()
	for i in A:
		a=set()
		for j in primes:
			if j>i:
				break
			elif i%j==0:
				a.add(j)




		B&=a
		if C&a:
			ans="setwise coprime"
		C|=a

	if B:
		ans="not coprime"

	print(ans)





















if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import bisect
import itertools
import decimal

# import numpy as np

# sys.setrecursionlimit(10 ** 6)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===
# N以下の素数列挙
def make_prime_nums(n):
    prime_nums = [2 if n >= 2 else None]
    for i in range(3, n + 1):
        for p in prime_nums:
            if p >= int(i ** (1 / 2)) + 1:
                prime_nums.append(i)
                break
            if i % p == 0:
                break
    return prime_nums


def main():
    n = ni()
    a = na()

    prime = make_prime_nums(10 ** 3)

    pc = True
    tc = True

    for pi in prime:
        cnt = 0
        for i in range(n):
            flg = False
            while a[i] % pi == 0:
                a[i] //= pi
                flg = True
            if flg:
                cnt += 1
        if cnt > 1:
            pc = False
        if cnt == n:
            tc = False
            break

    ca = collections.Counter(a)
    for k, v in ca.items():
        if k > 1:
            if ca[k] > 1:
                pc = False
            if ca[k] == n:
                tc = False
                break

    if pc:
        print("pairwise coprime")
    elif tc:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def erat():
    tmp = [False if i == 0 or i == 1 else True for i in range(10 ** 3)]
    for i in range(2, 10 ** 3):
        if tmp[i]:
            for j in range(2 * i, 10 ** 3, i):
                tmp[j] = False
            yield i

a = {}
for i in erat():
    for j in range(N):
        if A[j] % i == 0:
            while not A[j] % i:
                A[j] //= i
            if i in a:
                a[i] += 1
            else:
                a[i] = 1

for i in range(N):
    if A[i] != 1:
        if A[i] in a:
            a[A[i]] += 1
        else:
            a[A[i]] = 1

if max(a.values()) == 1:
    print('pairwise coprime')
elif max(a.values()) != N:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
##https://www.codechef.com/viewsolution/20131475

from math import gcd

def main():
    n = int(input())
    A = list(map(int , input().split()))
    N = max(A)+1

    sv = [i for i in range(N)]
    for i in range(2 , N) :
        if i * i >= N : break
        if sv[i] < i : continue
        for j in range(i * i , N , i) :
            sv[j] = min(sv[j] , i)

    def getPrimes(a) :
        pr = []
        if a == 1 : return pr
        pr.append(sv[a])
        while a > 1 :
            if sv[a] != pr[-1] :
                pr.append(sv[a])
            a //= sv[a]
        return pr

    np = [0] * N
    F = [0] * N


    for a in A :
        pr = getPrimes(a)
        for i in range(1 << len(pr)) :
            prod , nb = 1 , 0
            for j in range(len(pr)) :
                if i & (1<<j) :
                    prod *= pr[j]
                    nb += 1
            F[prod] += 1
            np[prod] = nb

    ans = 0
    for i in range(N) :
        cnt = F[i]
        cnt = (cnt * (cnt-1))//2
        if np[i] & 1 : ans -= cnt
        else : ans += cnt

    if ans == (n*(n-1))//2:
        print("pairwise coprime")
        exit()

    A.sort()
    d = A[0]

    for i in A:
        d = gcd(i,d)
        if d == 1 or d > 10**5:
            break

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

main()

Submission status: Time Limit Exceeded

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

a = [A[0]]
for i, _b in enumerate(A[1:], 1):
    for _a in a:
        _gcd = math.gcd(_a, _b)
        if _gcd != 1:
            c = _gcd
            for _c in A[i:]:
                c = math.gcd(c, _c)
                if c == 1:
                    print('setwise coprime')
                    break
            else:
                print('not coprime')
            break
    else:
        a.append(_b)
        continue
    break
else:
    print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys

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

a = max(A)//2
check = 0
for i in range(2,a+1) :
    B = list(map(lambda x : x%i , A))
    if B.count(0) == N :
        print("not coprime")
        sys.exit()
    elif B.count(0) >= 2 :
        check = 1

if check == 0 :
    print("pairwise coprime")
else :
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

N = int(input())
A = [int(i) for i in input().split()]
ans = 0
set = A[0]
pair = a = A[0]

for i in range(N-1):
    pair = gcd(a,A[i+1])
    a=a*A[i+1]
    if(pair!=1):
        break

for i in range(N-1):
    set = gcd(set,A[i+1])

if(pair == 1):
    print("pairwise coprime")
elif(set == 1):
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

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

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

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

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

count = 0
done = set()
ppdone = set(range(N))
for n in A:
    pdone = set()
    dup = False
    a = 2
    while a * a <= n:
        if n % a == 0:
            while n % a == 0:
                n //= a
            if a in done:
                dup = True
            else:
                done.add(a)
            if a in ppdone:
                pdone.add(a)
        a += 1
    if n != 1:
        if n in done:
            dup = True
        else:
            done.add(n)
        if n in ppdone:
            pdone.add(n)
    ppdone = pdone
    if dup:
        count += 1
if count == 0:
    print("pairwise coprime")
elif ppdone:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
def pairWiseCoprime(n,A):
	for i in range(n-1):
		for j in range(i+1,n):
			if gcd(A[i],A[j])==1:
				continue
			return False
	return True
def setWiseCoprime(n,A):
	if n<2:
		return True
	res=gcd(A[0],A[1])
	for i in range(2,n):
		res=gcd(res,A[i])
	return res==1
def solve(n,A):
	mod=10**9+7

	if pairWiseCoprime(n,A):
		return "pairwise coprime"
	elif setWiseCoprime(n,A):
		return "setwise coprime"
	else:
		return "not coprime"


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

Submission status: Time Limit Exceeded

Solution code:
from math import *
n=int(input())
l=list(map(int,input().split()))
l.sort()
g=l[0]
for i in range(1,n):
    g=gcd(g,l[i])
if(g!=1):
    print("not coprime")
else:
    f=0
    p=l[-1]
    for i in range(n-2,-1,-1):
        if(gcd(p,l[i])!=1):
            f=1
            break
        p*=l[i]
    if(f==1):
        print('setwise coprime')
    else:
        print('pairwise coprime')