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:
# E - Coprime

import math
from functools import reduce
from itertools import chain
from collections import Counter

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

if reduce(math.gcd, a) > 1:
    print("not coprime")
    exit()

def primes_under(n):
    plist = []
    isprime = [1] * (n + 1)
    for p in range(2, n + 1):
        if isprime[p]:
            plist.append(p)
            for q in range(p + p, n + 1, p):
                isprime[q] = 0
    return plist

primes = primes_under(10 ** 6)

def factors(n):
    """Return the list of prime factors of n."""
    fac = set()
    sqrtn = math.sqrt(n)
    i = 0
    while primes[i] <= sqrtn:
        if n % primes[i] == 0:
            fac.add(primes[i])
            n //= primes[i]
        else:
            i += 1
    if n > 1:
        fac.add(n)
    return fac

c = Counter(chain.from_iterable(map(factors, a)))
if max(c.values(), default=0) > 1:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

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

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

def is_pairwise_coprime():
    s = set()
    for ai in a:
        p = set(prime_factorize(ai))
        ns = s | p
        if len(s) + len(p) != len(ns):
            return False
        s = ns
    return True

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

def is_setwise_coprime():
    return reduce(gcd, a) == 1


if is_pairwise_coprime():
    print('pairwise coprime')
elif is_setwise_coprime():
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5)
        data = [i for i in range(2, n + 1)]
        while data[0]:
            p = data[0]
            if limit <= p:
                return D
            for i, d in enumerate(data):
                mod = d % p
                if mod != 0:
                    continue
                else:
                    D[d] = p
                    del data[i]
        return D



    N = I()
    A = LI()
    D = defaultdict()
    num_list = [0] * (10 ** 6 + 1)
    
    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()
        
    A_ = set(A)
    A_.discard(1)
    if len(A_) >= 90000:
        print("setwise coprime")
        exit()
    
    max_a = max(A)
    if max_a == 1:
        print('pairwise coprime')
        exit()
    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        while a != 1:
            if D.get(a) is None:
                D[a] = a
            x = D[a]
            if num_list[x] == 1:
                print('setwise coprime')
                exit()
            num_list[x] = 1
            a //= x

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    if n == 1:
        return {1: 1}

    prime_dict = {}
    for i in range(2, int(n**0.5)+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()

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

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()

    p_cnt = defaultdict(int)
    cnt = 0
    for a in A:
        if a == 1:
            continue
        AP = prime_fact(a)
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from math import gcd
from functools import reduce

PC = True
SC = True

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


for i in range(N):
  for j in range(N-1, i, -1):
    if A[i] < np.sqrt(A[j]):
      break
    if gcd(A[i],A[j]) != 1:
      PC = False
      break
        
p = reduce(gcd, A)
if p != 1:
  SC = False
      
if PC == True:
  print('pairwise coprime')
else:
  if SC == True:
    print('setwise coprime')
  else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
# E - Coprime

import math
from functools import reduce
from itertools import chain
from collections import Counter

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

if reduce(math.gcd, a) > 1:
    print("not coprime")
    exit()

def factors(n):
    """Return the list of prime factors of n."""
    fac = set()
    d = 2
    while d <= math.sqrt(n):
        if n % d == 0:
            fac.add(d)
            n //= d
        else:
            d += 1
    if n > 1:
        fac.add(n)
    return fac

c = Counter(chain.from_iterable(map(factors, a)))
if max(c.values(), default=0) > 1:
    print("setwise coprime")
else:
    print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n, ela):
    if n == 1:
        return {1: 1}

    prime_dict = {}
    for i in ela:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


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 not input_list[serial]:
            continue

        if serial >= sqrt:
            return input_list

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


def main():
    N = NI()
    A = NLI()
    ela = sieve_of_erastosthenes(1001)
    ela = [i for i, b in enumerate(ela) if b]

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

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()

    p_cnt = defaultdict(int)
    PD_list = defaultdict(dict)
    cnt = 0
    for a in A:
        if a == 1:
            continue

        if PD_list[a]:
            AP = PD_list[a]
        else:
            AP = prime_fact(a, ela)
            PD_list[a] = AP
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import defaultdict
    def get_sieve_of_eratosthenes(n, D):
        limit = int(n ** 0.5)
        data = [i for i in range(2, n + 1)]
        while data[0]:
            p = data[0]
            if limit <= p:
                return D
            for i, d in enumerate(data):
                mod = d % p
                if mod != 0:
                    continue
                else:
                    D[d] = p
                    del data[i]
        return D



    N = I()
    A = LI()
    D = defaultdict()
    num_list = [0] * (10 ** 6 + 1)

    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()
    max_a = max(A)
    if max_a == 1:
        print('pairwise coprime')
        exit()
    D = get_sieve_of_eratosthenes(max_a, D)
    for a in A:
        while a != 1:
            if D.get(a) is None:
                D[a] = a
            x = D[a]
            if num_list[x] == 1:
                print('setwise coprime')
                exit()
            num_list[x] = 1
            a //= x

    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
N=int(input())
A=list(map(int,input().split()))
l=[0]*1000001
pr=[]
for i in range(2,1000001):
    if l[i]:
        continue
    pr.append(i)
    for j in range(i**2,1000001,i):
        l[j]=1
lp=len(pr)
l=[0]*lp
g=gcd(A[0],A[1])
for i in A:
    g=gcd(g,i)
if g>1:
    print("not coprime")
    exit()
for i in A:
    t=i
    for j in range(lp):
        pj=pr[j]
        if pj>t:
            break
        if t%pj==0:
            if l[j]:
                print("setwise coprime")
                exit()
            l[j]=1
            while 1:
                t//=pj
                if t%pj:
                    break
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
from numba import njit, i8 
import numpy as np

n = int(input())
alist = list(map(int,input().split()))
alist = np.array(alist)
a_max = max(alist)

D = [i for i in range(a_max+1)]
D = np.array(D)
D[0] = 1
D[1] = 1

@njit(i8[:](i8,i8[:]),cache=True)
def factor(n,D):
    f = set()
    f.add(n)
    while n > 1:
        f.add(D[n])
        n //= D[n]
    f.add(1)
    return np.array(list(f))

@njit(i8(i8,i8), cache=True)
def gcf(a,b):
    if a == 0:
        return b
    return gcf(b % a,a)

@njit((i8,i8[:],i8[:]),cache=True)
def main(n,alist,D):
    a_max = max(alist)
    p = 2
    top = math.ceil(math.sqrt(a_max))
    for i in range(2,top+1):
        if D[i] == i:
            p = i
            mul_p = p
            while mul_p <= a_max:
                D[mul_p] = min(p,D[mul_p])
                mul_p += p
    factor_set = set()
    pairwise = True
    for i in range(n):
        a = alist[i]

        a_factor = factor(a,D)
        for f in a_factor:
            if f != 1 and f in factor_set:
                pairwise = False
                break
            factor_set.add(f)

        if pairwise == False:
            break
    if pairwise == True: 
        print("pairwise coprime")
    else:
        #setwise
        now = alist[0]
        for i in range(1,n-1):
            now = gcf(now,gcf(alist[i],alist[i+1]))

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

main(n,alist,D)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def _make_prime_numbers(N: int):
    # N以下の素数を列挙 -> set
    # まずエラトステネスの篩を作成
    is_prime = [True] * (N + 1)
    is_prime[0] = False  # 0と1は素数ではない
    is_prime[1] = False
    for i in range(2, int(N ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * 2, N + 1, i):  # iの倍数は素数でない
                is_prime[j] = False

    primes = []
    for i, flg in enumerate(is_prime):
        if flg:
            primes.append(i)

    return primes


primes = _make_prime_numbers(10**6)


from bisect import bisect_left


def fast_factorization(N: int):
    # -> List[Tuple[int,int]] (素数,冪数)を格納
    # 素数配列primesを使ってO(log N)で因数分解
    if N == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = N
    for p in primes[:bisect_left(primes, N**(1 / 2)) + 1]:
        if temp % p == 0:
            cnt = 0
            while temp % p == 0:
                cnt += 1
                temp //= p
            arr.append((p, cnt))
            if temp == 1:  # 早期終了
                break

    if temp != 1:  # √Nより大きい素因数はたかだか1個ある
        arr.append((temp, 1))
    if arr == []:  # 自身が素数だった場合
        arr.append((temp, 1))

    return arr


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from math import gcd


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
for a in A:
    g_set = gcd(g_set, a)
    for p, n in fast_factorization(a):
        if cnt[p] != 0:
            flg = 0
        cnt[p] += n



if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
from numba import njit, i8 
import numpy as np

n = int(input())
alist = list(map(int,input().split()))
alist = np.array(alist)
a_max = max(alist)

D = [i for i in range(a_max+1)]
D = np.array(D)
D[0] = 1
D[1] = 1

@njit(i8[:](i8,i8[:]),cache=True)
def factor(n,D):
    f = set()
    f.add(n)
    while n > 1:
        f.add(D[n])
        n //= D[n]
    f.add(1)
    return np.array(list(f))

@njit(i8(i8,i8), cache=True)
def gcf(a,b):
    if a == 0:
        return b
    return gcf(b % a,a)

def main(n,alist,D):
    a_max = max(alist)
    p = 2
    top = math.ceil(math.sqrt(a_max))
    for i in range(2,top+1):
        if D[i] == i:
            p = i
            mul_p = p
            while mul_p <= a_max:
                D[mul_p] = min(p,D[mul_p])
                mul_p += p
    factor_set = set()
    pairwise = True
    for i in range(n):
        a = alist[i]

        a_factor = factor(a,D)
        for f in a_factor:
            if f != 1 and f in factor_set:
                pairwise = False
                break
            factor_set.add(f)

        if pairwise == False:
            break
    if pairwise == True: 
        print("pairwise coprime")
        exit()

    #setwise
    now = alist[0]
    for i in range(1,n-1):
        now = gcf(now,gcf(alist[i],alist[i+1]))

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

main(n,alist,D)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from math import gcd
    _ = int(input())
    A = [int(i) for i in input().split()]

    def prime_factorize(n):
        for i in range(2, n+1):
            if i*i > n:
                break
            if n % i != 0:
                continue
            while n % i == 0:
                n //= i
            B[i] += 1
        if n != 1:
            B[n] += 1
    maxA = max(A)
    B = [0] * (maxA + 1)
    for a in A:
        prime_factorize(a)

    g = A[0]
    for a in A:
        g = gcd(g, a)

    if g != 1:
        print("not coprime")
    elif max(B) <= 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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

    counts = [0] * (10**6 + 1)
    for a in A:
        counts[a] += 1

    counts = np.array(counts, dtype=np.int64)

    ans = 0
    for i in range(2, 10**6+1):
        co_primes = counts[i::i].sum()
        if ans < co_primes:
            ans = co_primes

    if ans == 1:
        print("pairwise coprime")
    elif ans < n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
alist = list(map(int,input().split()))

a_max = max(alist)
D = [i for i in range(a_max+1)]
D[0] = 1
D[1] = 1
p = 2
top = math.ceil(math.sqrt(a_max))
for i in range(2,top+1):
    if D[i] == i:
        p = i
        mul_p = p
        while mul_p <= a_max:
            D[mul_p] = min(p,D[mul_p])
            mul_p += p

def factor(n):
    f = set()
    f.add(n)
    while n > 1:
        f.add(D[n])
        n //= D[n]
    f.add(1)
    return list(f)

factor_set = set()
pairwise = True
for i in range(n):
    a = alist[i]

    a_factor = factor(a)
    for f in a_factor:
        if f != 1 and f in factor_set:
            pairwise = False
            break
        factor_set.add(f)

    if pairwise == False:
        break
if pairwise == True: 
    print("pairwise coprime")
    exit()

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

#setwise
now = alist[0]
for i in range(1,n-1):
    now = gcf(now,gcf(alist[i],alist[i+1]))

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

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
alist = list(map(int,input().split()))

mod = 10**9 + 7
prod = 1

a_max = max(alist)
D = [i for i in range(a_max+1)]
D[0] = 1
D[1] = 1
p = 2
top = math.ceil(math.sqrt(a_max))
for i in range(2,top+1):
    p = i
    mul_p = p
    while mul_p <= a_max:
        D[mul_p] = min(p,D[mul_p])
        mul_p += p

def factor(n):
    f = set()
    f.add(n)
    while n > 1:
        f.add(D[n])
        n //= D[n]
    f.add(1)
    return list(f)

factor_set = set()
pairwise = True
for i in range(n):
    a = alist[i]

    a_factor = factor(a)
    for f in a_factor:
        if f != 1 and f in factor_set:
            pairwise = False
            break
        factor_set.add(f)

    if pairwise == False:
        break
if pairwise == True: 
    print("pairwise coprime")
    exit()

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

#setwise
now = alist[0]
for i in range(1,n-1):
    now = gcf(now,gcf(alist[i],alist[i+1]))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def _make_minimum_prime(N: int):
    # xの最小の素因数表を作成
    min_prime = [N + 114514] * (N + 1)
    min_prime[0] = 0  # 0と1は素数ではない
    min_prime[1] = 1
    for i in range(2, int(N ** 0.5) + 1):
        if min_prime[i] == N + 114514:  # 素数だったら更新
            for j in range(i, N + 1, i):  # iの倍数は素数でない
                min_prime[j] = min(min_prime[j], i)
    return min_prime


min_prime = _make_minimum_prime(10**6)


def fast_factorization(N: int):
    # -> List[Tuple[int,int]] (素数,冪数)を格納
    # 最小素数配列min_primeを使ってO(log N)で因数分解
    if N == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    tmp = N
    while tmp != 1:
        p = min_prime[tmp]
        cnt = 0
        while tmp % p == 0:
            cnt += 1
            tmp //= p
        arr.append((p, cnt))

    return arr


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from math import gcd


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
for a in A:
    g_set = gcd(g_set, a)
    if flg:
        for p, n in fast_factorization(a):
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
alist = list(map(int,input().split()))

mod = 10**9 + 7
prod = 1

a_max = max(alist)
D = [i for i in range(a_max+1)]
D[0] = 1
D[1] = 1
p = 2
for i in range(2,math.ceil(math.sqrt(a_max))+1):
    p = i
    mul_p = p
    while mul_p <= a_max:
        D[mul_p] = min(p,D[mul_p])
        mul_p += p

def factor(n):
    f = set()
    f.add(n)
    while n > 1:
        f.add(D[n])
        n //= D[n]
    f.add(1)
    return list(f)

factor_set = set()
pairwise = True
for i in range(n):
    a = alist[i]

    a_factor = factor(a)
    for f in a_factor:
        if f != 1 and f in factor_set:
            pairwise = False
            break
        factor_set.add(f)

    if pairwise == False:
        break
if pairwise == True: 
    print("pairwise coprime")
    exit()

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

#setwise
now = alist[0]
for i in range(1,n-1):
    now = gcf(now,gcf(alist[i],alist[i+1]))

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


def gcd(x, y):
    if x > y:
        x, y = y, x
    while y != 0:
        tmp = x % y
        x = y
        y = tmp
    return x


n = A[0]
for i in range(1, N):
    n = gcd(n, A[i])
if n != 1:
    print('not coprime')
    exit()

d = np.zeros(max_a+10)
for a in A:
    d[a] += 1

for i in range(2, max_a+1):
    if sum(d[i::i]) >= 2:
        print('setwise coprime')
        exit()
print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
alist = list(map(int,input().split()))

mod = 10**9 + 7
prod = 1

a_max = max(alist)
D = [math.inf]*(a_max+1)
D[0] = 1
D[1] = 1
p = 2
for i in range(1,a_max+1):
    if D[i] == math.inf:
        p = i
        mul_p = p
        while mul_p <= a_max:
            D[mul_p] = min(p,D[mul_p])
            mul_p += p


def factor(n):
    f = set()
    f.add(n)
    while n > 1:
        f.add(D[n])
        n //= D[n]
    f.add(1)
    return list(f)

factor_set = set()
pairwise = True
for i in range(n):
    a = alist[i]

    a_factor = factor(a)
    for f in a_factor:
        if f != 1 and f in factor_set:
            pairwise = False
            break
        factor_set.add(f)

    if pairwise == False:
        break
if pairwise == True: 
    print("pairwise coprime")
    exit()

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

#setwise
now = alist[0]
for i in range(1,n-1):
    now = gcf(now,gcf(alist[i],alist[i+1]))

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

Submission status: Time Limit Exceeded

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


def divisor(n):
    l = []
    i = 1
    while True:
        if n % i == 0:
            l.append(i)
            if i * i != n:
                l.append(n / i)
        i += 1
        if i * i >= n:
            break
    return sorted(l)


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

gcd_of_all = gcd(a[0], a[1])
for i in range(2, n):
    gcd_of_all = gcd(gcd_of_all, a[i])

if gcd_of_all != 1:
    print("not coprime")
    exit()

s = set()

for i in range(n):
    l = divisor(a[i])
    for j in range(len(l)):
        if l[j] == 1:
            continue
        if l[j] in s:
            print("setwise coprime")
            exit()
        else:
            s.add(l[j])

print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

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

for i in range(N):
    f(A[i])

cnt = 1
for i, v in d.items():
    if v != 1:
        cnt = max(cnt, v)
        
if cnt == N:
    print('not coprime')
elif cnt == 1:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def _make_prime_numbers(N: int):
    # N以下の素数を列挙 -> set
    # まずエラトステネスの篩を作成
    is_prime = [True] * (N + 1)
    is_prime[0] = False  # 0と1は素数ではない
    is_prime[1] = False
    for i in range(2, int(N ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * 2, N + 1, i):  # iの倍数は素数でない
                is_prime[j] = False

    primes = []
    for i, flg in enumerate(is_prime):
        if flg:
            primes.append(i)

    return primes


primes = _make_prime_numbers(10**6)


def fast_factorization(N: int):
    # -> List[Tuple[int,int]] (素数,冪数)を格納
    # 素数配列primesを使ってO(log N)で因数分解
    if N == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = N
    for p in primes:
        if temp % p == 0:
            cnt = 0
            while temp % p == 0:
                cnt += 1
                temp //= p
            arr.append((p, cnt))
            if temp == 1 or p**2 > N:  # 早期終了
                break

    if temp != 1:  # √Nより大きい素因数はたかだか1個ある
        arr.append((temp, 1))
    if arr == []:  # 自身が素数だった場合
        arr.append((temp, 1))

    return arr


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
import random
from math import gcd


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
for a in A:
    g_set = gcd(g_set, a)
    if flg:
        for p, n in fast_factorization(a):
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def _make_prime_numbers(N: int):
    # N以下の素数を列挙 -> set
    # まずエラトステネスの篩を作成
    is_prime = [True] * (N + 1)
    is_prime[0] = False  # 0と1は素数ではない
    is_prime[1] = False
    for i in range(2, int(N ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * 2, N + 1, i):  # iの倍数は素数でない
                is_prime[j] = False

    primes = set()
    for i, flg in enumerate(is_prime):
        if flg:
            primes.add(i)

    return primes


primes = _make_prime_numbers(10**6)


def fast_factorization(N: int):
    # -> List[Tuple[int,int]] (素数,冪数)を格納
    # 素数配列primesを使ってO(log N)で因数分解
    if N == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = N
    for p in primes:
        if temp % p == 0:
            cnt = 0
            while temp % p == 0:
                cnt += 1
                temp //= p
            arr.append((p, cnt))
            if temp == 1 or p**2 > N:  # 早期終了
                break

    if temp != 1:  # √Nより大きい素因数はたかだか1個ある
        arr.append((temp, 1))
    if arr == []:  # 自身が素数だった場合
        arr.append((temp, 1))

    return arr


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
import random
from math import gcd


N = a_int()
A = ints()

# setかはすぐわかる
# setでなければ not coprime
# pairは互いに素かをみればいいのか
# つまり因数分解して足してったときにすべての素数のべき数が1以下であれば良い

g_set = 0
cnt = defaultdict(lambda: 0)
flg = 1  # pairwiseであるフラグ
for a in A:
    g_set = gcd(g_set, a)
    if flg:
        for p, n in fast_factorization(a):
            if cnt[p] != 0:
                flg = 0
            cnt[p] += n


# print(cnt)
# for v in cnt.values():
#     if v > 1:
#         flg = 0
#         break

if g_set > 1:
    print('not coprime')
elif flg:
    print('pairwise coprime')
else:
    print('setwise coprime')