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 sys


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


def is_prime_MR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1 << 32 else [
        2, 3, 5, 7, 11, 13, 17
    ] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1:
            continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1:
                return 0
            t <<= 1
    return 1


def find_factor_rho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):

        def f(x):
            return (x * x + c) % n

        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if is_prime_MR(g):
                return g
            elif is_prime_MR(n // g):
                return n // g
            return find_factor_rho(g)


def prime_factor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k:
            ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2**20:
            while n > 1:
                if is_prime_MR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = find_factor_rho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k
    if n > 1:
        ret[n] = 1
    if rhoFlg:
        ret = {x: ret[x] for x in sorted(ret)}
    return ret


input = sys.stdin.buffer.readline

N = int(input())
A = list(map(int, input().split()))
g = 0
for a in A:
    g = gcd(g, a)

if g > 1:
    print('not coprime')
    exit()

X = [0] * 1001001
for a in A:
    for p in prime_factor(a):
        if X[p]:
            print('setwise coprime')
            exit()
        X[p] = 1

print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:

def main():
    from itertools import chain
    import sys
    input = sys.stdin.readline

    def gcd(x, y):
        if y == 0:
            return x
        return gcd(y, x % y)
    # 6n+1, 6n-1でも求めて、素数**2+素数*kはふるいおとす
    def prime_set(N):
        """
        Nまでの素数のsetを返す
        """
        if N < 4:
            return ({}, {}, {2}, {2, 3})[N]
        Nsq = int(N ** 0.5 + 0.5) + 1
        primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
        for i in range(5, Nsq, 2):
            if i in primes:
                primes -= set(range(i * i, N + 1, i * 2))
        return primes

    def factorization(n, prime_set):
        l = []
        tmp = n
        nsq = int(n ** 0.5 + 0.5) + 1
        for i in prime_set:
            if  i > nsq: 
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                l.append(i)
            i += 1
        if tmp != 1:
            l.append(tmp)
        if l == []:
            if n != 1:
                l.append(n)
        return set(l)
    n = int(input())
    A = [int(x) for x in input().split()]

    # setwise coprimeの条件(1ならOK)
    g = 0
    for a in A:
        g = gcd(g, a)
    # 素数列挙
    primes = prime_set(10**6+1)
    # 全部素因数分解
    pairwise_f = True
    af = factorization(A[0], primes)
    af_l = len(af)
    for a in A[1:]:
        f = factorization(a, primes)
        af_l += len(f)
        af = af | f
    if af_l != len(af):
        pairwise_f = False
    if pairwise_f:
        print('pairwise coprime')
    elif g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    from itertools import chain
    import sys
    input = sys.stdin.readline

    def gcd(x, y):
        if y == 0:
            return x
        return gcd(y, x % y)
    # 6n+1, 6n-1でも求めて、素数**2+素数*kはふるいおとす
    def prime_set(N):
        """
        Nまでの素数のsetを返す
        """
        if N < 4:
            return ({}, {}, {2}, {2, 3})[N]
        Nsq = int(N ** 0.5 + 0.5) + 1
        primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
        for i in range(5, Nsq, 2):
            if i in primes:
                primes -= set(range(i * i, N + 1, i * 2))
        return primes

    def factorization(n, prime_set):
        l = []
        tmp = n
        nsq = int(n ** 0.5 + 0.5) + 1
        for i in prime_set:
            if  i > nsq: 
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                l.append(i)
            i += 1
        if tmp != 1:
            l.append(tmp)
        if l == []:
            if n != 1:
                l.append(n)
        return set(l)
    n = int(input())
    A = [int(x) for x in input().split()]

    # setwise coprimeの条件(1ならOK)
    g = 0
    for a in A:
        g = gcd(g, a)
    # 素数列挙
    primes = prime_set(10**6+1)
    # 全部素因数分解
    pairwise_f = True
    af = factorization(A[0], primes)
    for a in A[1:]:
        f = factorization(a, primes)
        if len(af & f) == 0:
            af = af | f
        else:
            pairwise_f = False
            break
    if pairwise_f:
        print('pairwise coprime')
    elif g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
f=0
n=int(input())
a=list(map(int,input().split()))
p = [0]*10**6
for i in range(0, len(a)):
    for j in range(2, int(math.sqrt(a[i]))+1):
        if a[i] % j == 0:
            p[j] += 1
    if max(p)>1:
        f=1
        break
if f==0:
    print("pairwise coprime")
else:
    _gcd=a[0]
    for i  in range(1,len(a)):
        _gcd=math.gcd(_gcd,a[i])
    if _gcd==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
import math
f=0
n=int(input())
a=list(map(int,input().split()))
p = [0]*10**6
for i in range(0, len(a)):
    for j in range(2, int(math.sqrt(a[i]))+2):
        if a[i] % j == 0:
            p[i] += 1
    if max(p)>1:
        f=1
        break
if f==0:
    print("pairwise coprime")
else:
    _gcd=a[0]
    for i  in range(1,len(a)):
        _gcd=math.gcd(_gcd,a[i])
    if _gcd==1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

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

M = 10**6

import math

import random

X = random.sample(range(N), N)

setwise = A[0]
for i in range(1,N):
    setwise = math.gcd(setwise,A[i])
    
PrimeFactorss = [[] for _ in range(M+1)]
for i in range(2, M+1):
    if len(PrimeFactorss[i]) == 0:
        for x in range(i, M+1, i):
            PrimeFactorss[x].append(i)
num_list = [0]*(M+1)

for i in range(N):
    num_list[A[i]] += 1

pairwise = [0]*N

for i in range(N):
    i = X[i]
    num_list[A[i]] -= 1
    for j in PrimeFactorss[A[i]]:
        for k in range(j,M+1,j):

            if num_list[k]==1:
                pairwise[i] += 1
                break
                
    num_list[A[i]] += 1
    
    if pairwise[i]>0:
        break
    
if sum(pairwise) == 0:
    print("pairwise coprime")
elif setwise == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

M = 10**6

import math

setwise = A[0]
for i in range(1,N):
    setwise = math.gcd(setwise,A[i])
    
PrimeFactorss = [[] for _ in range(M+1)]
for i in range(2, M+1):
    if len(PrimeFactorss[i]) == 0:
        for x in range(i, M+1, i):
            PrimeFactorss[x].append(i)
num_list = [0]*(M+1)

for i in range(N):
    num_list[A[i]] += 1

pairwise = [0]*N

for i in range(N):
    num_list[A[i]] -= 1
    for j in PrimeFactorss[A[i]]:
        for k in range(j,M+1,j):

            if num_list[k]==1:
                pairwise[i] += 1
                break
                
    num_list[A[i]] += 1
    
    if pairwise[i]>0:
        break
    
if sum(pairwise) == 0:
    print("pairwise coprime")
elif setwise == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

M = 10**6

import math

setwise = A[0]
for i in range(1,N):
    setwise = math.gcd(setwise,A[i])
    
PrimeFactorss = [[] for _ in range(M+1)]
for i in range(2, M+1):
    if len(PrimeFactorss[i]) == 0:
        for x in range(i, M+1, i):
            PrimeFactorss[x].append(i)
num_list = [0]*(M+1)

for i in range(N):
    num_list[A[i]] += 1

pairwise = [0]*N

for i in range(N):
    num_list[A[i]] -= 1
    for j in PrimeFactorss[A[i]]:
        for k in range(j,M+1,j):

            if num_list[k]==1:
                pairwise[i] += 1
                break
                
    num_list[A[i]] += 1
    
if sum(pairwise) == 0:
    print("pairwise coprime")
elif setwise == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

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

M = 10**6

import math

setwise = A[0]
for i in range(1,N):
    setwise = math.gcd(setwise,A[i])
    
PrimeFactorss = [[] for _ in range(M+1)]
for i in range(2, M+1):
    if len(PrimeFactorss[i]) == 0:
        for x in range(i, M+1, i):
            PrimeFactorss[x].append(i)
num_list = [0]*(M+1)

for i in range(N):
    num_list[A[i]] += 1

pairwise = [0]*N

for i in range(N):
    num_list[A[i]] -= 1
    for j in PrimeFactorss[A[i]]:
        for k in range(j,M+1,j):

            if num_list[k]==1:
                pairwise[i] += 1
                
    num_list[A[i]] += 1
    
if sum(pairwise) == 0:
    print("pairwise coprime")
elif setwise == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
MAX_A = 10**6 + 1
MAX_P = MAX_A // 2
is_prim = [i%2==1 for i in range(MAX_P)]
is_prim[1] = False; is_prim[2] = True
for i in range(3, MAX_P):
    if not is_prim[i]: continue
    for j in range(i+i, MAX_P, i): is_prim[j] = False

def solve():
    c = 0
    C = [0] * MAX_A
    for a in A:
        for p in range(MAX_P):
            if not is_prim[p]: continue
            if a%p: continue
            if a < p*p: break
            C[p] += 1
            c = max(c, C[p])
    if c <= 1: return "pairwise"
    elif c <= n-1: return "setwise"
    return "not"

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Time Limit Exceeded

Solution code:
MAX_A = 10**6 + 1
MAX_P = MAX_A // 2
is_prim = [i%2==1 for i in range(MAX_P)]
is_prim[1] = False; is_prim[2] = True
for i in range(3, MAX_P):
    if not is_prim[i]: continue
    for j in range(i+i, MAX_P, i): is_prim[j] = False

def solve():
    c = 0
    C = [0] * MAX_A
    for a in A:
        # for p in [i for i in range(MAX_P) if is_prim[i] and a%i==0]:
        for p, f in zip(range(MAX_P), is_prim):
            if not f: continue
            if a%p: continue
            C[p] += 1
            c = max(c, C[p])
    if c <= 1: return "pairwise"
    elif c <= n-1: return "setwise"
    return "not"

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Time Limit Exceeded

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

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

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

pc = True

fac = [0]*(10**6+1)
for a in A:
    lst = factorize(a)
    for p in lst:
        if not fac[p[0]]:
            fac[p[0]] = 1
        else:
            pc = False
            break
    if not pc:
        break
if pc:
    print('pairwise coprime')
else:
    g = A[0]
    for i in range(1,n):
        g = gcd(g, A[i])
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
MAX_A = 10**6 + 1
MAX_P = MAX_A // 2
is_prim = [i%2==1 for i in range(MAX_P)]
is_prim[1] = False; is_prim[2] = True
for i in range(3, MAX_P):
    if not is_prim[i]: continue
    for j in range(i+i, MAX_P, i): is_prim[j] = False

def solve():
    c = 0
    C = [0] * MAX_A
    for a in A:
        for p in [i for i in range(MAX_P) if is_prim[i] and a%i==0]:
            C[p] += 1
            c = max(c, C[p])
    if c <= 1: return "pairwise"
    elif c <= n-1: return "setwise"
    return "not"

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Time Limit Exceeded

Solution code:
import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

p=[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,1009]

import math

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の倍数を除去
        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

p=get_primenumber(20000)

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()


for pp in p:
    lap=0
    for ai in ap:
        if  ai%pp==0:
            lap+=1
        if lap>=2:
            print("setwise coprime")
            sys.exit()
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

p=[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,1009]

import math

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の倍数を除去
        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

p=get_primenumber(78498)

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()


for pp in p:
    lap=0
    for ai in ap:
        if  ai%pp==0:
            lap+=1
        if lap>=2:
            print("setwise coprime")
            sys.exit()
print("pairwise coprime")

Submission status: Time Limit Exceeded

Solution code:
P = [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 prime_factors(N):
    ret = []
    for p in P:
        while N % p == 0:
            ret.append(p)
            N //= p
    if N > 1:
        ret.append(N)
    return ret


N = 10 ** 6  # int(input())
A = [10 ** 6] * N  # list(map(int, input().split()))
S = []
for p in P:
    S.append(sum([1 for a in A if a % p == 0]))
print(S)

Submission status: Time Limit Exceeded

Solution code:
import functools
from math import gcd
N = int(input())
A = list(map(int, input().split()))
MAX = 10 ** 6 + 10

prime_list = [i for i in range(MAX + 1)]
p = 2
while p * p <= MAX:
    if prime_list[p] == p:
        for q in range(2*p, MAX+1, p):
            if prime_list[q] == q:
                prime_list[q] = p
    p += 1

prime = set()
cnt = 0
for a in A:
    tmp = set()
    while a > 1:
        tmp.add(prime_list[a])
        a //= prime_list[a]
    prime = prime | tmp
    cnt += len(tmp)

if len(prime) == cnt:
    print("pairwise coprime")
elif functools.reduce(gcd, A) == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    a, b = sorted([a, b], reverse=True)
    if b == 0:
        return a
    else:
        r = a % b
        ans = gcd(b, r)
        return ans

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

pw, sw = False, False
d, l, P = 0, 1, 1
for i in range(N):
    d = gcd(A[i], d)
    P = P * A[i]
    l = (A[i] * l) // gcd(A[i], l)

if d == 1:
    sw = True
    if P == l:
        pw = True

if sw:
    if pw:
        print('pairwise coprime')
    else:
        print('setwise coprime')
else:
    print('not coprime')

Submission status: Time Limit Exceeded

Solution code:
import math

MAX=10**6+3
table = list(range(MAX))
i=2
n=MAX
while i<=n:
    table[i] = 2
    i+=2

p=3
while p*p<=n:
    if table[p]<p:
        continue
    x=p
    while x<=n:
        table[x]=p
        x+=p
    p+=2

def primeFactorSet(n):
    result = set()
    while table[n]!=1:
        result.add(table[n])
        n //= table[n]
    return result
    

n = int(input())
A = list(map(int,input().split()))
pairwise = True
flags = [False for _ in range(MAX)]

for i in range(n):
    a=A[i]
    if pairwise:
        t = primeFactorSet(a)
        for p in t:
            if flags[p]:
                pairwise = False
                break
            flags[p]=True
    if i==0:
        g=a
    else:
        g=math.gcd(g,a)
    
if g>1:
    print("not coprime")
elif pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
# In[]:
import math
from functools import reduce


# In[]:
def gcd_list(numbers):
    return reduce(math.gcd, numbers)


# In[]:
N = int(input())
input_str = input()
input_list = input_str.split()
input_int = [int(x) for x in input_list]

# In[]:
gcd_all = gcd_list(input_int)
if gcd_all != 1:
    print('not coprime')
else:
    flag = 0
    for idx, i in enumerate(input_int):
        for j in input_int[idx+1:]:
            if math.gcd(i, j) != 1:
                flag = 1
                break
        else:
            continue
        break
    if flag == 1:
        print('setwise coprime')
    elif flag == 0:
        print('pairwise coprime')

Submission status: Time Limit Exceeded

Solution code:
import math

MAX=10**6+3
table = list(range(MAX))
i=2
n=MAX
while i<=n:
    table[i] = 2
    i+=2

p=3
while p*p<=n:
    if table[p]<p:
        continue
    x=p
    while x<=n:
        table[x]=p
        x+=p

def primeFactorSet(n):
    result = set()
    while table[n]!=1:
        result.add(table[n])
        n //= table[n]
    return result
    

n = int(input())
A = list(map(int,input().split()))
pairwise = True
flags = [False for _ in range(MAX)]

for i in range(n):
    a=A[i]
    if pairwise:
        t = primeFactorSet(a)
        for p in t:
            if flags[p]:
                pairwise = False
                break
            flags[p]=True
    if i==0:
        g=a
    else:
        g=math.gcd(g,a)
    
if g>1:
    print("not coprime")
elif pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")

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()

  g=0
  for x in A:
    g=math.gcd(g,x)
  if g>1:
    return 'not coprime'

  sosu=[0]*1000100
  for x in A:
    if x==1:
      continue
    sosu[x]+=1
    if sosu[x]>1:
      return 'setwise coprime'
    for y in range(2,int(math.sqrt(x))+1):
      if x%y!=0:
        continue
      z=x//y
      if y==z:
        sosu[y]+=1
        if sosu[y]>1:
          return 'setwise coprime'
      else:
        sosu[y]+=1
        if sosu[y]>1:
          return 'setwise coprime'
        sosu[z]+=1
        if sosu[z]>1:
          return 'setwise coprime'

  return 'pairwise coprime'

# main()
print(main())

Submission status: Time Limit Exceeded

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

A.sort()
R = A[-2]

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(R+1)
l = 0

for i in range(2, R+1):
    if checked[i]:
        continue
    
    # 調べる範囲を狭める
    while A[l] < i and l < N-1:
        l += 1
    if l == N-1:
        break
    
    # iで割り切れるAiの個数を数える
    tmp = 0
    for j in range(l, N):
        if A[j]%i == 0:
            tmp += 1
    # 2個以上あればnot pairwise coprime
    # N個あれば not setwise coprime
    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    
    if is_setwise_coprime == False:
        break
    
    # iの倍数はチェック済みにする
    n = i
    while n < R+1:
        checked[n] = 1
        n += i
    # print(checked, l)
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:
MAX_A = 10**6 + 1

# 素数と個数を求める
def factorize(n):
    res = []
    for i in range(2,n):
        if i*i > n: break
        if n%i: continue
        res += [[i,0]]
        while n%i == 0:
            n //= i
            res[-1][1] += 1
    if n != 1: res += [[n,1]]
    return res

def solve():
    max_c = 0
    C = [0] * MAX_A
    for a in A:
        for p, c in factorize(a):
            C[p] += 1
            max_c = max(max_c, C[p])
    if max_c <= 1: return 'pairwise'
    elif max_c <= n-1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Time Limit Exceeded

Solution code:
MAX_A = 10**6 + 1

def factorize(n):
    res = []
    for i in range(2,n):
        if i*i > n: break
        if n%i: continue
        res += [[i,0]]
        while n%i == 0:
            n //= i
            res[-1][1] += 1
    if n != 1: res += [[n,1]]
    return res

def solve():
    C = [0] * MAX_A
    for a in A:
        for p, c in factorize(a): C[p] += 1
    max_c = max(C)
    if max_c <= 1: return 'pairwise'
    elif max_c <= n-1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')

Submission status: Time Limit Exceeded

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

max_A = max(A)

import math

def factorization(n):
    arr = []
    temp = n
    for i in prime_list:
        if i > n:
            break

        if temp % i == 0:
            arr.append(i)

    return arr

def primes(n):
    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
    return [i for i in range(n + 1) if is_prime[i]]

prime_list = primes(max_A)
prime_list.sort()

all_fact = []
for a in A:
    fact = factorization(a)
    all_fact += fact

if len(all_fact) == len(set(all_fact)):
    print("pairwise coprime")
else:
    ans = A[0]
    for i in range(1, N):
        ans = math.gcd(ans, A[i])
    if ans == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

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

max_A = max(A)

import itertools
import math
#
# ans_list = 1
not_pair = False
not_set = False
#
# for combi in itertools.combinations(A, 2):
#     ans = math.gcd(combi[0], combi[1])
#     if ans != 1:
#         not_pair = True
#         if ans_list == 1:
#             ans_list = ans
#         else:
#             ans_list = math.gcd(ans, ans_list)
#             if ans_list != 1:
#                 not_set = True
#                 break
#
# if not not_pair:
#     print("pairwise coprime")
# elif not not_set:
#     print("setwise coprime")
# else:
#     print("not coprime")

def factorization(n):
    arr = []
    temp = n
    for i in prime_list:
        if i > n:
            break

        if temp % i == 0:
            arr.append(i)

    return arr

def primes(n):
    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
    return [i for i in range(n + 1) if is_prime[i]]

prime_list = primes(max_A)
prime_list.sort()

fact_list = []
all_fact = []
set_fact = set(factorization(A[0]))
for a in A:
    fact = factorization(a)
    fact_list.append(fact)
    all_fact += fact
    set_fact = set_fact & set(fact)


# print(set_fact)

if len(all_fact) == len(set(all_fact)):
    print("pairwise coprime")
else:
    ans = A[0]
    for i in range(1, N):
        ans = math.gcd(ans, A[i])
    if ans == 1:
        print("setwise coprime")
    else:
        print("not coprime")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
M = max(a)+1
if M == 2:
    print("pairwise coprime")
    exit()
count = [0]*(M)

for i in range(2,M):
    if count[i] == 0:
        for j in range(i,M,i):
            if count[j] == 0:
                count[j] = i
check = [0]*(M)
for i in a:
    x = i
    while x > 1:
        check[count[x]] += 1
        y = count[x]
        while x%y == 0:
            x //= y
ans = max(check)
if ans == 1:
    print("pairwise coprime")
elif ans == n:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Time Limit Exceeded

Solution code:
MAX_A = 10**6 + 1
# is_prim = [True] * MAX_A
# is_prim[0] = is_prim[1] = False
# for i in range(2, MAX_A):
#     if not is_prim[i]: continue
#     for j in range(i+i, MAX_A, i): is_prim[j] = False

# 素数と個数を求める
def factorize(n):
    res = []
    for i in range(2,n):
        if i*i > n: break
        if n%i: continue
        res += [[i,0]]
        while n%i == 0:
            n //= i
            res[-1][1] += 1
    if n != 1: res += [[n,1]]
    return res

def solve():
    # prim = [i for i in range(1100) if is_prim[i]]
    C = [0] * MAX_A
    for a in A:
        for p,c in factorize(a): C[p] += 1
    max_c = max(C)
    if max_c <= 1: return 'pairwise'
    elif max_c <= n-1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')