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 numpy as np

N = int(input())
A = input().split()

count = np.zeros(1001,dtype=int)

for i in A:
  Ai = int(i)
  for j in range(2, 1001):
    if Ai % j == 0:
      count[j]  += 1

mc = max(count) 
if mc == 1:
  print("pairwise coprime")
elif mc < N:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

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

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

dvs = []
for i in As:
  dvs+=make_divisors(i)
com = Counter(dvs).most_common()
res=0
for i in com[1:]:
  if i[1] == N:
    res = 2
    break
  elif i[1] >1:
    res = 1
if res == 0:
  print("pairwise coprime")
elif res == 1:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from math import gcd

def Eratos(n):
    F = [True for _ in range(n+1)]
    F[0],F[1] = False,False
    for i in range(2,int(sqrt(n))+1):
        if F[i]:
            for j in range(2,n//i+1):
                F[i*j] = False

    P = []
    for i in range(2,n+1):
        if F[i]:
            P.append(i)
    return P

def fact(n):#return P={p | pはnの素因数}
    P = Eratos(n)
    ret = set()
    for i in range(len(P)):
        if n % P[i] == 0:
            ret.add(P[i])
        if P[i] > n:
            break
    return ret

def GCD(A,N):
    g = A[0]
    for i in range(N):
        g = gcd(g,A[i])
        if g == 1:
            return 1
    return g

def solve(A,N):
    ans = ["pairwise coprime","setwise coprime","not coprime"]
    ans_id = 0
    P = set()
    pc_flag = True
    for i in range(N):
        P_tmp = fact(A[i])
        if len(P & P_tmp) == 0:
            P = P.union(P_tmp)
        else:
            ans_id += 1
            pc_flag = False
            break

    if pc_flag:
        return ans[ans_id]
    else:
        if GCD(A,N) == 1:
            return ans[ans_id]
        else:
            ans_id += 1
            return ans[ans_id]

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

    print(solve(A,N))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
def eratosthenes(N):
    from collections import deque
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    ret = []
    for i in range(N+1):
        if work[i]:
            ret.append(i)
            for j in range(2* i, N+1, i):
                work[j] = False
    return ret

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

def main():
    N = int( input())
    A = list( map( int, input().split()))
    g = A[0]
    for a in A:
        g = gcd(a, g)
    if g > 1:
        print("not coprime")
        return
    E = eratosthenes(10**3)
    EE = [0]*len(E)
    R = []
    for a in A:
        for i, e in enumerate(E):
            if a%e == 0:
                if EE[i] > 0:
                    print("setwise coprime")
                    return
                EE[i] = 1
            while a%e == 0:
                a //= e
        if a > 1:
            R.append(a)
    R.sort()
    for i in range(len(R)-1):
        if R[i] == R[i+1]:
            print("setwise coprime")
            return
    print("pairwise coprime")
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def gcd(a, b):
  return a if b == 0 else gcd(b, a % b)

def lcm(a, b):
  return a * b // gcd(a, b)

l, g, mul = 1, 0, 1
for i in ar:
  l = lcm(i, l)
  g = gcd(g, i)
  mul *= i

print('pairwise coprime' if l == mul else 'setwise coprime' if g == 1 else 'not coprime')

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
def eratosthenes(N):
    from collections import deque
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    ret = []
    for i in range(N+1):
        if work[i]:
            ret.append(i)
            for j in range(2* i, N+1, i):
                work[j] = False
    return ret

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

def main():
    N = int( input())
    A = list( map( int, input().split()))
    # A.sort()
    g = A[0]
    for a in A:
        g = gcd(a, g)
    if g > 1:
        print("not coprime")
        return
    # for i in range(N-1):
    #     if A[i] == A[i+1]:
    #         print("setwise coprime")
    #         return
    E = eratosthenes(10**3)
    for e in E:
        cnt = 0
        s = set()
        for i in range(N):
            if A[i]%e == 0:
                cnt += 1
            while A[i]%e == 0:
                A[i] //= e
            if A[i] in s:
                print("setwise coprime")
                return
            if A[i] > 1:
                s.add(A[i])
        if cnt > 1:
            print("setwise coprime")
            return
    # A.sort()
    # for i in range(N-1):
    #     if A[i] == A[i+1] and A[i] > 1:
    #         print("setwise coprime")
    #         return
    print("pairwise coprime")
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from math import gcd

def fact(n):#return P={p | pはnの素因数}
    P = set()
    for i in range(2,int(sqrt(n))+1):
        if n % i == 0:
            P.add(i)
            while n % i == 0:
                n //= i
        if n == 1:
            break
    if n != 1:
        P.add(n)
    return P

def GCD(A,N):
    g = A[0]
    for i in range(N):
        g = gcd(g,A[i])
        if g == 1:
            return 1
    return g

def solve(A,N):
    ans = ["pairwise coprime","setwise coprime","not coprime"]
    ans_id = 0
    P = set()
    pc_flag = True
    for i in range(N):
        P_tmp = fact(A[i])
        for p in P_tmp:
            if p in P:
                ans_id += 1
                pc_flag = False
                break
            else:
                P.add(p)
        P_tmp.clear()
        if not pc_flag:
            break

    if pc_flag:
        return ans[ans_id]

    if not pc_flag:
        if GCD(A,N) == 1:
            return ans[ans_id]
        else:
            ans_id += 1
            return ans[ans_id]

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

    print(solve(A,N))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#import sys
#input = sys.stdin.readline
from math import gcd
def eratosthenes(N):
    from collections import deque
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    ret = []
    for i in range(N+1):
        if work[i]:
            ret.append(i)
            for j in range(2* i, N+1, i):
                work[j] = False
    return ret

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

def main():
    N = int( input())
    A = list( map( int, input().split()))
    # A.sort()
    g = A[0]
    for a in A:
        g = gcd(a, g)
    if g > 1:
        print("not coprime")
        return
    # for i in range(N-1):
    #     if A[i] == A[i+1]:
    #         print("setwise coprime")
    #         return
    E = eratosthenes(10**3)
    for e in E:
        cnt = 0
        for i in range(N):
            if A[i]%e == 0:
                cnt += 1
            while A[i]%e == 0:
                A[i] //= e
        if cnt > 1:
            print("setwise coprime")
            return
    A.sort()
    for i in range(N-1):
        if A[i] == A[i+1] and A[i] > 1:
            print("setwise coprime")
            return
    print("pairwise coprime")
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
def eratosthenes(N):
    from collections import deque
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    ret = []
    for i in range(N+1):
        if work[i]:
            ret.append(i)
            for j in range(2* i, N+1, i):
                work[j] = False
    return ret

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

def main():
    N = int( input())
    A = list( map( int, input().split()))
    # A.sort()
    g = A[0]
    for a in A:
        g = gcd(a, g)
    if g > 1:
        print("not coprime")
        return
    # for i in range(N-1):
    #     if A[i] == A[i+1]:
    #         print("setwise coprime")
    #         return
    E = eratosthenes(10**3)
    for e in E:
        cnt = 0
        for i in range(N):
            if A[i]%e == 0:
                cnt += 1
            while A[i]%e == 0:
                A[i] //= e
        if cnt > 1:
            print("setwise coprime")
            return
    A.sort()
    for i in range(N-1):
        if A[i] == A[i+1] and A[i] > 1:
            print("setwise coprime")
            return
    print("pairwise coprime")
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def eratosthenes(N):
    from collections import deque
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    ret = []
    for i in range(N+1):
        if work[i]:
            ret.append(i)
            for j in range(2* i, N+1, i):
                work[j] = False
    return ret

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

def main():
    N = int( input())
    A = list( map( int, input().split()))
    # A.sort()
    g = A[0]
    for a in A:
        g = gcd(a, g)
    if g > 1:
        print("not coprime")
        return
    # for i in range(N-1):
    #     if A[i] == A[i+1]:
    #         print("setwise coprime")
    #         return
    E = eratosthenes(10**3)
    for e in E:
        cnt = 0
        for i in range(N):
            if A[i]%e == 0:
                cnt += 1
            while A[i]%e == 0:
                A[i] //= e
        if cnt > 1:
            print("setwise coprime")
            return
    A.sort()
    for i in range(N-1):
        if A[i] == A[i+1] and A[i] > 1:
            print("setwise coprime")
            return
    print("pairwise coprime")
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from math import gcd

def fact(n):#return P={p | pはnの素因数}
    P = set()
    for i in range(2,int(sqrt(n))+1):
        if n % i == 0:
            P.add(i)
            while n % i == 0:
                n //= i
            if n == 1:
                break
    if n != 1:
        P.add(n)
    return P

def GCD(A,N):
    g = A[0]
    for i in range(N):
        g = gcd(g,A[i])
        if g == 1:
            return 1
    return g

def solve(A,N):
    ans = ["pairwise coprime","setwise coprime","not coprime"]
    ans_id = 0
    P = set()
    pc_flag = True
    for i in range(N):
        P_tmp = fact(A[i])
        if len(P & P_tmp) == 0:
            P = P | P_tmp
            P_tmp.clear()
        else:
            ans_id += 1
            pc_flag = False
            break

    if pc_flag:
        return ans[ans_id]

    if not pc_flag:
        if GCD(A,N) == 1:
            return ans[ans_id]
        else:
            ans_id += 1
            return ans[ans_id]

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

    print(solve(A,N))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from math import gcd 

n = int(input())
A = list(map(int, input().split()))
pr = [True]*(10**6+5)

def prime_fact(x):
    memo = [0]*(x+1)
    primes = []
    if x <= 1: return False
    for i in range(2, x+1):
        if memo[i]:
            continue
        primes.append(i)
        memo[i] = i
        for j in range(i*i, x+1, i):
            if memo[j]:
                continue
            memo[j] = i
    a = x
    b = []
    while a > 1:
        b.append(memo[a])
        a //= memo[a]
    return b


for a in A:
    if a == 1: continue
    for p in set(prime_fact(a)):
        if not pr[p]:
            break
        pr[p] = False
    else:
        continue
    break
else:
    print('pairwise coprime')
    exit()

if reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

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

maxA = max(A) + 1

C = [0] * maxA

g = 0

for a in A:
    C[a] += 1
    g = math.gcd(g, a)

pairwise = True

for i in range(2, maxA):
    cnt = 0
    for j in range(i, maxA, i):
        cnt += C[j]

    if cnt > 1:
        pairwise = False

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

if g == 1:
    print("setwise coprime")

else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    if a < b:
        return gcd(b, a)
    elif a % b == 0:
        return b
    else:
        r = a % b
        return gcd(b, r)

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

p1 = A[0]
p2 = A[0]
p3 = A[0]
for i in range(1, N):
    p1 *= A[i]
    p2 = gcd(A[i], p2)
    p3 = p3 * A[i] // gcd(A[i], p3)

flg_set = p2 == 1
flg_pair = p1 == p3
if flg_set:
    if flg_pair:
        print("pairwise coprime")
    else:
        print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    from itertools import combinations

    def prime_factorization_turple(n: int):
        """
        入力された整数nを素因数分解し，タプルを要素とするリストで返却
        Parameters
        ----------
        n : int
            素因数分解したい整数
        Returns
        -------
        prime_factorization_lst : lst
            [(素因数,累乗)]の形で素因数が列挙された素因数分解結果
        """
        fct = set()     # prime factor
        b, e = 2, 0  # base factor
        while b * b <= n:
            while n % b == 0:
                n //= b
                e += 1
            if e > 0:
                fct.add(b)
            b += 1
            e = 0
        if n > 1:
            fct.add(n)
        return fct

    _ = int(input())
    A = sorted([int(x) for x in input().split()])

    # Aの素因数分解
    fac_A = [prime_factorization_turple(a) for a in A]

    # pairwiseの判定
    pairwise_coprime = True
    for a, b in combinations(fac_A, 2):
        for i in a:
            if i in b:
                pairwise_coprime = False
                break
        if pairwise_coprime is False:
            break
    if pairwise_coprime:
        print('pairwise coprime')
        return

    # setwise
    setwise_coprime = True
    for b in fac_A[0]:
        cnt = 0
        for a in A:
            if a % b == 0:
                cnt += 1
        if cnt == len(A):
            setwise_coprime = False
            break

    if setwise_coprime:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


class Prime:
    @staticmethod
    def trial_division(x):
        if x % 2 == 0:
            return True
        for p in range(3, int(x**0.5 + 1), 2):
            if x % p == 0:
                return False
        return True

    @staticmethod
    def factorization(x):
        ret = {}
        i = 0
        while True:
            if x % 2:
                break
            x //= 2
            i += 1
        if i:
            ret[2] = i
        f = 3
        while True:
            if f * f > x:
                break
            i = 0
            while True:
                if x % f:
                    if i:
                        ret[f] = i
                    f += 2
                    break
                x //= f
                i += 1
        if x > 1:
            ret[x] = 1
        return ret

    @staticmethod
    def miller_rabin(n):
        def suspect(a, t, n):
            x = pow(a, t, n)
            n1 = n - 1
            while t != n1 and x != 1 and x != n1:
                x = pow(x, 2, n)
                t <<= 1
            return t & 1 or x == n1

        if n == 2:
            return True
        if n < 2 or n % 2 == 0:
            return False
        d = (n - 1) >> 1
        while d & 1 == 0:
            d >>= 1

        if n < 2**32:
            check_list = (2, 7, 61)
        elif n < 2**48:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23)
        else:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)

        for i in check_list:
            if i >= n:
                break
            if not suspect(i, d, n):
                return False
        return True


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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    from itertools import combinations

    def prime_factorization_turple(n: int):
        """
        入力された整数nを素因数分解し，タプルを要素とするリストで返却
        Parameters
        ----------
        n : int
            素因数分解したい整数
        Returns
        -------
        prime_factorization_lst : lst
            [(素因数,累乗)]の形で素因数が列挙された素因数分解結果
        """
        fct = set()     # prime factor
        b, e = 2, 0  # base factor
        while b * b <= n:
            while n % b == 0:
                n //= b
                e += 1
            if e > 0:
                fct.add(b)
            b += 1
            e = 0
        if n > 1:
            fct.add(n)
        return fct

    _ = int(input())
    A = sorted([int(x) for x in input().split()])

    # Aの素因数分解
    fac_A = [prime_factorization_turple(a) for a in A]

    # pairwiseの判定
    pairwise_coprime = True
    for a, b in combinations(fac_A, 2):
        for i in a:
            if i in b:
                pairwise_coprime = False
                break
        if pairwise_coprime is False:
            break

    # setwise
    setwise_coprime = True
    for b in fac_A[0]:
        cnt = 0
        for a in A:
            if a % b == 0:
                cnt += 1
        if cnt == len(A):
            setwise_coprime = False
            break

    if pairwise_coprime:
        print('pairwise coprime')
    elif setwise_coprime:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
*A, = map(int, input().split())
m = max(2, max(A))
P = {p: True for p in range(2, m + 1)}
for i in range(2, m + 1):
    for j in range(2 * i, m + 1, i):
        P[j] = False
P = {p: 0 for p in P if P[p]}
for a in A:
    for p in P:
        if a % p == 0:
            P[p] += 1
s = max(P.values())
if s <= 1:
    print('pairwise coprime')
elif s < n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

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


class Prime:
    @staticmethod
    def trial_division(x):
        if x % 2 == 0:
            return True
        for p in range(3, int(x**0.5 + 1), 2):
            if x % p == 0:
                return False
        return True

    @staticmethod
    def factorization(x):
        ret = set()
        while True:
            if x % 2:
                break
            x //= 2
            ret.add(2)
        for p in range(3, int(x**0.5 + 1), 2):
            while True:
                if x % p:
                    break
                x //= p
                ret.add(p)
        if x > 1:
            ret.add(x)
        return ret

    @staticmethod
    def miller_rabin(n):
        def suspect(a, t, n):
            x = pow(a, t, n)
            n1 = n - 1
            while t != n1 and x != 1 and x != n1:
                x = pow(x, 2, n)
                t <<= 1
            return t & 1 or x == n1

        if n == 2:
            return True
        if n < 2 or n % 2 == 0:
            return False
        d = (n - 1) >> 1
        while d & 1 == 0:
            d >>= 1

        if n < 2**32:
            check_list = (2, 7, 61)
        elif n < 2**48:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23)
        else:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)

        for i in check_list:
            if i >= n:
                break
            if not suspect(i, d, n):
                return False
        return True


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

Submission status: Time Limit Exceeded

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


class Prime:
    @staticmethod
    def trial_division(x):
        if x % 2 == 0:
            return True
        for p in range(3, int(x**0.5 + 1), 2):
            if x % p == 0:
                return False
        return True

    @staticmethod
    def factorization(x):
        ret = {}
        i = 0
        while True:
            if x % 2:
                break
            x //= 2
            i += 1
        if i:
            ret[2] = i
        for p in range(3, int(x**0.5 + 1), 2):
            i = 0
            while True:
                if x % p:
                    if i:
                        ret[p] = i
                    break
                x //= p
                i += 1
        if x > 1:
            ret[x] = 1
        return ret

    @staticmethod
    def miller_rabin(n):
        def suspect(a, t, n):
            x = pow(a, t, n)
            n1 = n - 1
            while t != n1 and x != 1 and x != n1:
                x = pow(x, 2, n)
                t <<= 1
            return t & 1 or x == n1

        if n == 2:
            return True
        if n < 2 or n % 2 == 0:
            return False
        d = (n - 1) >> 1
        while d & 1 == 0:
            d >>= 1

        if n < 2**32:
            check_list = (2, 7, 61)
        elif n < 2**48:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23)
        else:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)

        for i in check_list:
            if i >= n:
                break
            if not suspect(i, d, n):
                return False
        return True


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

Submission status: Time Limit Exceeded

Solution code:
import math

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

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
    while search_list[0] <= math.sqrt(number):
        #search_listの先頭の値が√nの値を超えたら終了
        #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        for i in range(number // head_num):
            index = head_num * (i + 1)
            if D[index] == index:
                D[index] = head_num
        search_list = [num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list


def factrization_prime(number):
    div = D[number]
    s = math.sqrt(number)
    while div <= s:
        div_cnt = 0
        while number % div == 0:
            div_cnt += 1
            number //= div
        ans_array[div] += 1
        if number == 1:
            break
        div = D[number]
    if number > 1:
        ans_array[number] += 1

# thre = pow(10, 6) + 1
thre = max(a_array) + 1
ans_array = [0] * thre
D = list(range(thre + 1))

prime_list = get_primenumber(thre)
# print(D[:10])
for a in a_array:
    factrization_prime(a)

max_ans_array = max(ans_array)
if max_ans_array == 1:
    print('pairwise coprime')
elif max_ans_array < n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int,input().split())))
    d = [1 for i in range(a[-1])]
    for i in range(2,a[-1]+1):
        if d[i-1] == 1:
            for j in range(1,a[-1]//i+1):
                if d[i*j-1] == 1:
                    d[i*j-1] = i
    prm = [0 for i in range(a[-1])]
    for i in range(n):
        p = []
        while a[i] != 1:
            p.append(d[a[i]-1])
            a[i] = a[i] // d[a[i]-1]
        p = set(p)
        for p_ in p:
            prm[p_-1] += 1
    flg = 0
    for i in range(1,len(prm)):
        if prm[i] == n:
            print('not coprime')
            return
        if prm[i]>1:
            flg = 1
    if flg==1:
        print('setwise coprime')
        return
    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import math
    n = int(input())
    a = sorted(list(map(int,input().split())))
    g=a[0]
    for i in range(1,n):
        g = math.gcd(g,a[i])
    if g > 1:
        print('not coprime')
        return
    d = [1 for i in range(a[-1])]
    for i in range(2,a[-1]+1):
        if d[i-1] == 1:
            for j in range(1,a[-1]//i+1):
                if d[i*j-1] == 1:
                    d[i*j-1] = i
    prm = [0 for i in range(a[-1])]
    for i in range(n):
        p = []
        while a[i] != 1:
            p.append(d[a[i]-1])
            a[i] = a[i] // d[a[i]-1]
        p = set(p)
        for p_ in p:
            prm[p_-1] += 1
    for i in range(1,len(prm)):
        if prm[i]>1:
            print('setwise coprime')
            return
    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N=I()
  A=LI()

  l=[0]*1000100
  for x in A:
    l[x]+=1

  pairwise=True
  for i in range(2,1000100):
    cnt=0
    for j in range(i+1,1000100):
      cnt+=l[j]
    if cnt>1:
      pairwise=False

  if pairwise:
    return 'pairwise coprime'

  g=0
  for x in A:
    g=math.gcd(g,x)

  if g==1:
    return 'setwise coprime'

  return 'not coprime'

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    import math
    n = int(input())
    a = sorted(list(map(int,input().split())))
    g=a[0]
    for i in range(1,n):
        g = math.gcd(g,a[i])
    if g > 1:
        print('not coprime')
        return
    d = [1 for i in range(a[-1])]
    for i in range(2,a[-1]):
        if d[i-1] == 1:
            for j in range(1,a[-1]//i+1):
                if d[i*j-1] == 1:
                    d[i*j-1] = i
    prm = [0 for i in range(a[-1])]
    for i in range(n):
        p = []
        while a[i] != 1:
            p.append(d[a[i]-1])
            a[i] = a[i] // d[a[i]-1]
        p = set(p)
        for p_ in p:
            prm[p_-1] += 1
    for i in range(1,len(prm)):
        if prm[i]>1:
            print('setwise coprime')
            return
    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from math import gcd
from functools import reduce
from collections import Counter
import heapq


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def sieve(n):
    """
    n以下の素数を昇順に列挙する
    """
    prime_divisors = [1 for i in range(n+1)]
    for i in range(2, n+1):
        if prime_divisors[i] == 1:
            for j in range(i, n+1, i):
                prime_divisors[j] = i
    return prime_divisors


def solve(N, A):
    prime_divisors = sieve(max(A))
    c = Counter()
    for a in A:
        p = a
        d = Counter()
        while p > 1:
            q = prime_divisors[p]
            d[q] = 1
            p //= q
        c += d
    if len(c) == 0 or c.most_common()[0][1] == 1:
        return "pairwise coprime"
    if reduce(gcd, A) == 1:
        return "setwise coprime"
    return "not coprime"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import math

n = int(input())
a = list(map(int, input().split()))
m = max(a)
fre = [0 for _ in range(m+1)]

for i in range(n):
    fre[a[i]] += 1

# pairwise coprime
pairwise = True
for i in range(2, len(fre)):
    cnt = 0 
    for j in range(i, m+1, i): 
        cnt += fre[j]
    if cnt > 1:
        pairwise = False
if pairwise:
    print('pairwise coprime')
    exit()

# setwise coprime
ans = math.gcd(a[0],a[1])
for i in range(2, n): 
   ans = math.gcd(ans, a[i])
if ans == 1:
    print('setwise coprime')
    exit()

print('not coprime')