Problem:


Score : 500 points

Problem Statement

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

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

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

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

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

Constraints

2 \leq N \leq 10^6

1 \leq A_i\leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

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

Sample Input 1

3
3 4 5

Sample Output 1

pairwise coprime

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

Sample Input 2

3
6 10 15

Sample Output 2

setwise coprime

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

Sample Input 3

3
6 10 16

Sample Output 3

not coprime

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



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Runtime Error

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    maxA = max(A)
    prime = [i % 2 != 0 for i in range(maxA+1)]
    prime[2] = True
    f = [False] * (maxA+1)
    for i in range(3, int(maxA**.5)+1):
        if prime[i] == False:
            continue
        p = i * 2
        while p <= maxA:
            prime[p] = False
            p += i

    def gcd(x, y):
        if y == 0:
            return x
        return gcd(y, x % y)

    pairwise_coprime = A[0]
    setwise_coprime = A[0]
    for An in A[1:]:
        setwise_coprime = gcd(setwise_coprime, An)
        if setwise_coprime == 1:
            break
    
    for An in A:
        # print('An = {}'.format(An))
        if f[An]:
            break
        elif prime[An]:
            f[An] = True
        else:
            for i in range(2, An // 2 + 1):
                if prime[An]:
                    if f[An]:
                        if setwise_coprime == 1:
                            print('setwise coprime')
                            return
                        else:
                            print('not coprime')
                            return
                    else:
                        f[An] = True
                        break
                if f[An]:
                    if setwise_coprime == 1:
                        print('setwise coprime')
                        return
                    else:
                        print('not coprime')
                        return
                elif An % i == 0:
                    # print('i={}'.format(i))
                    if f[i]:
                        if setwise_coprime == 1:
                            print('setwise coprime')
                            return
                        else:
                            print('not coprime')
                            return
                    f[i] = True
                    while An // i == 0:
                        An //= i
        # print(f)
    print('pairwise coprime')

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
N = int(input())
A = list(map(int,input().rstrip().split(" ")))
M = int(math.sqrt(max(A))) + 1
sosuu = set()
sosuu.add(2)
for i in range(3,M,2):
    for j in sosuu:
        if i % j == 0:
            break
    else:
        sosuu.add(i)
pair = True
setw = True
counter = 0
lis = [0 for i in range(10 ** 6)]
for q in range(len(A)):
    i = A[q]
    remset = set()
    for j in sosuu:
        if i % j == 0:
            while i % j == 0:
                i = i // j
            lis[j] += 1
            if lis[j] == 2:
                pair = False
        else:
            if lis[j] >= 2 or pair == False:
                remset.add(j)
    if i != 0:
        lis[i] += 1
        if lis[i] == 2:
            pair = False
    for j in remset:
        sosuu.remove(j)
for i in range(10 ** 6):
    if lis[i] == N:
        setw = False

if pair:
    print("pairwise coprime")
elif setw:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Runtime Error

Solution code:
import bisect
import sys
import math
input = sys.stdin.readline
import functools

from collections import defaultdict

############ ---- Input Functions ---- ############

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

############ ---- Solution ---- ############

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

def solve():
    N = inp()
    AA = inlt()

    AA = [v for v in AA if v > 1]
    if len(AA) == 0:
        return "pairwise coprime"
    
    mult = AA[0]
    gcd_cum = AA[0]
    pairwise = True

    for i in range(1, N):
        if i == 1 or gcd_cum == 1:
            if pairwise:
                g = gcd(mult, AA[i])
                if g != 1:
                    pairwise = False
                mult = mult * (AA[i] // g)
            else:
                break
        gcd_cum = gcd(gcd_cum, AA[i])
    
    if gcd_cum == 1 and pairwise:
        return "pairwise coprime"

    if gcd_cum == 1:
        return "setwise coprime"
    
    return "not coprime"

    

if len(sys.argv) > 1 and sys.argv[1].startswith("input"):
    f = open("./" + sys.argv[1], 'r')
    input = f.readline

res = solve()
print(str(res))