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: Wrong Answer

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split()))

    if 1 in A:
        countone = 0
        for i in A:
            if i == 1:
                countone += 1
        if countone == len(A):
            print('pairwise coprime')
        else:
            print('not coprime')
        sys.exit()


    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


    def prime_factor_table(n):
        table = [0] * (n + 1)
        for i in range(2, n + 1):
            if table[i] == 0:
                for j in range(i + i, n + 1, i):
                    table[j] = i
        return table

    def prime_factor(n, prime_factor_table):
        prime_count = collections.Counter()

        while prime_factor_table[n] != 0:
            prime_count[prime_factor_table[n]] += 1
            n //= prime_factor_table[n]
        prime_count[n] += 1

        return prime_count

    table = prime_factor_table(10**6+10)

    numset = set()
    for i in A:
        thedic = prime_factor(i, table)
        for l in thedic.keys():
            flag = True
            if l in numset:
                flag = False
                break
        if flag:
            tmpset = set(thedic.keys())
            numset |= tmpset
        else:
            break
    if flag:
        print('pairwise coprime')
        sys.exit()
    else:
        flag = True
        theset = set(prime_factor(A[0], table).keys())
        for i in A[1:]:
            thedic = prime_factor(i, table)
            theset = theset & set(thedic.keys())
            if len(theset) == 0:
                print('setwise coprime')
                flag = False
                break
    if flag:
        print('not coprime')



if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split()))
    
    if 1 in A:
        print('pairwise corprime')
        sys.exit()


    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


    def prime_factor_table(n):
        table = [0] * (n + 1)
        for i in range(2, n + 1):
            if table[i] == 0:
                for j in range(i + i, n + 1, i):
                    table[j] = i
        return table

    def prime_factor(n, prime_factor_table):
        prime_count = collections.Counter()

        while prime_factor_table[n] != 0:
            prime_count[prime_factor_table[n]] += 1
            n //= prime_factor_table[n]
        prime_count[n] += 1

        return prime_count

    table = prime_factor_table(10**6+10)

    numset = set()
    for i in A:
        thedic = prime_factor(i, table)
        for l in thedic.keys():
            flag = True
            if l in numset:
                flag = False
                break
        if flag:
            tmpset = set(thedic.keys())
            numset |= tmpset
        else:
            break
    if flag:
        print('pairwise coprime')
        sys.exit()
    else:
        flag = True
        theset = set(prime_factor(A[0], table).keys())
        for i in A[1:]:
            thedic = prime_factor(i, table)
            theset = theset & set(thedic.keys())
            if len(theset) == 0:
                print('setwise coprime')
                flag = False
                break
    if flag:
        print('not coprime')



if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from math import gcd
import time

#pri_arr[i]におけるiの素因数のうち最大の数を持つ配列をつくる
#pri_arrはこんな感じになる↓
#[0, 0, 2, 3, 2, 5, 3, 7, 2, 3,...]
def make_prime_arr(max_a):
    pri_arr = [0] * max_a
    #start_time = time.time()
    for i in range(2, max_a):
        if(pri_arr[i] != 0):
            continue
        for j in range (i, max_a, i):
            pri_arr[j] = i
    #end_time = time.time()
    #print(end_time - start_time)
    return pri_arr


#pairwiseかどうかを判定する関数
def is_pairwise(a_arr, pri_arr, max_a):
    flg_arr = [0] * (max_a)
    for a_ele in a_arr:
        x = a_ele
        y = -1
        while x != 1:
            if(y != pri_arr[x]):
                flg_arr[pri_arr[x]] += 1
            if flg_arr[pri_arr[x]] > 1:
                return False
            x = int(x/pri_arr[x])
            y = x
    return True


#setwiseかどうかを判定する関数
def is_setwise(a_arr, N):
    entire_gcd = a_arr[0]
    for i in range(1, N):
        entire_gcd = gcd(entire_gcd, a_arr[i])
    if entire_gcd != 1:
        return False        
    return True


def main():
    N = int(input())
    a_arr = list(map(int, input().split(" ")))
    max_a = 10**6 + 1
    pri_arr = make_prime_arr(max_a)
    if is_pairwise(a_arr, pri_arr, max_a):
        print("pairwise coprime")
    elif is_setwise(a_arr, N):
        print("setwise coprime")
    else:
        print("not coprime")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

import math
G = A[0]

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

if G > 1:
	print('not coprime')
	exit()
  
V = set(A)
if len(V) < N or len(A) > 78498:
	print('setwise coprime')
	exit()

Primes = []

def Sieve(n): 
	prime = [True for i in range(n + 1)] 
	p = 2
	while (p * p <= n): 
		if (prime[p] == True): 
			for i in range(p * 2, n + 1, p): 
				prime[i] = False
		p += 1
	prime[0]= False
	prime[1]= False
    # Print all prime numbers 
	for p in range(n + 1): 
		if prime[p]: 
			Primes.append(p)

Sieve(math.floor(max(A)/2)+1)

for i in range (0, len(Primes)):
	count = 0
	for j in range (0, N):
		if A[j]%Primes[i] == 0:
			count+=1
	if count > 1:
		print('setwise coprime')
		exit()

if min(A) == 1:
	print('setwise coprime')
else:
	print('pairwise coprime')

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split()))
    
    if 1 in A:
        print('not comprise')
        sys.exit()

    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


    def prime_factor_table(n):
        table = [0] * (n + 1)
        for i in range(2, n + 1):
            if table[i] == 0:
                for j in range(i + i, n + 1, i):
                    table[j] = i
        return table

    def prime_factor(n, prime_factor_table):
        prime_count = collections.Counter()

        while prime_factor_table[n] != 0:
            prime_count[prime_factor_table[n]] += 1
            n //= prime_factor_table[n]
        prime_count[n] += 1

        return prime_count

    table = prime_factor_table(10**6+10)

    numset = set()
    for i in A:
        thedic = prime_factor(i, table)
        for l in thedic.keys():
            flag = True
            if l in numset:
                flag = False
                break
        if flag:
            tmpset = set(thedic.keys())
            numset |= tmpset
        else:
            break
    if flag:
        print('pairwise coprime')
        sys.exit()
    else:
        flag = True
        theset = set(prime_factor(A[0], table).keys())
        for i in A[1:]:
            thedic = prime_factor(i, table)
            theset = theset & set(thedic.keys())
            if len(theset) == 0:
                print('setwise coprime')
                flag = False
                break
    if flag:
        print('not coprime')



if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(input())
    A = 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の倍数を除去
            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 prime_factor_table(n):
        table = [0] * (n + 1)
        for i in range(2, n + 1):
            if table[i] == 0:
                for j in range(i + i, n + 1, i):
                    table[j] = i
        return table

    def prime_factor(n, prime_factor_table):
        prime_count = collections.Counter()

        while prime_factor_table[n] != 0:
            prime_count[prime_factor_table[n]] += 1
            n //= prime_factor_table[n]
        prime_count[n] += 1

        return prime_count

    table = prime_factor_table(10**6+10)

    numset = set()
    for i in A:
        thedic = prime_factor(i, table)
        for l in thedic.keys():
            flag = True
            if l in numset:
                flag = False
                break
        if flag:
            tmpset = set(thedic.keys())
            numset |= tmpset
        else:
            break
    if flag:
        print('pairwise coprime')
        sys.exit()
    else:
        flag = True
        theset = set(prime_factor(A[0], table).keys())
        for i in A[1:]:
            thedic = prime_factor(i, table)
            theset = theset & set(thedic.keys())
            if len(theset) == 0:
                print('setwise coprime')
                flag = False
                break
    if flag:
        print('not coprime')



if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from math import gcd
import time

#pri_arr[i]におけるiの素因数のうち最大の数を持つ配列をつくる
#pri_arrはこんな感じになる↓
#[0, 0, 2, 3, 2, 5, 3, 7, 2, 3,...]
def make_prime_num(max_a):
    pri_arr = [0] * max_a
    #start_time = time.time()
    for i in range(2, max_a):
        if(pri_arr[i] != 0):
            continue
        for j in range (i, max_a, i):
            pri_arr[j] = i
    #end_time = time.time()
    #print(end_time - start_time)
    return pri_arr


#pairwiseかどうかを判定する関数
def is_pairwise(input_arr, pri_arr, max_a):
    flg_arr = [0] * (max_a + 1)
    for input_ele in input_arr:
        x = input_ele
        y = 0
        while x != 1:
            if(y != pri_arr[x]):
                flg_arr[pri_arr[x]] += 1
            if flg_arr[pri_arr[x]] > 1:
                return False
            x = int(x/pri_arr[x])
            y = x
    return True


#setwiseかどうかを判定する関数
def is_setwise(input_arr, N):
    entire_gcd = input_arr[0]
    for i in range(1, N):
        entire_gcd = gcd(entire_gcd, input_arr[i])
    if entire_gcd != 1:
        return False        
    return True


def main():
    N = int(input())
    input_arr = list(map(int, input().split(" ")))
    max_a = 10**6 + 1
    pri_arr = make_prime_num(max_a)
    if is_pairwise(input_arr, pri_arr, max_a):
        print("pairwise coprime")
    elif is_setwise(input_arr, N):
        print("setwise coprime")
    else:
        print("not coprime")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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):
        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 list(primes)
    n = int(input())
    A = [int(x) for x in input().split()]
    len_A = len(A)
    # setwise coprimeの条件(1ならOK)
    g = 0
    for a in A:
        g = gcd(g, a)
    # 素数列挙
    num = 10**6+1
    primes = prime_set(num)
    # 全部素因数分解
    prime_list = [0] * (num+1)
    pairwise_f = True
    ll = list()
    set_A = set(A)
    set_primes = set(primes)
    diff_A = set_A - set_primes
    for a in diff_A:
        l = []
        tmp = a
        # nsq = int(a ** 0.5 + 0.5) + 1
        for i in primes:
            if  i*i > a:
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                prime_list[i] += 1
                l.append(i)
                if prime_list[i] == 2:
                    break
        if tmp != 1:
            prime_list[tmp] += 1
            l.append(tmp)
            if prime_list[tmp] == 2:
                break
        if l == []:
            if a != 1:
                prime_list[a] += 1
                l.append(a)
                if prime_list[a] == 2:
                    break  
    set_prime_list = set(prime_list)
    if set_prime_list != set([0]) and set_prime_list != set([0, 1]):
        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: Wrong Answer

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 list(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)
        if tmp != 1:
            l.append(tmp)
        if l == []:
            if n != 1:
                l.append(n)
        return 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)
    # 素数列挙
    num = 10**6+1
    primes = prime_set(num)
    # 全部素因数分解
    prime_list = [0] * (num+1)
    pairwise_f = True
    ll = list()
    for a in A:
        l = []
        tmp = a
        # nsq = int(a ** 0.5 + 0.5) + 1
        for i in primes:
            if  i*i > a:
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                prime_list[i] += 1
                l.append(i)
        if tmp != 1:
            prime_list[tmp] += 1
            l.append(tmp)
        if l == []:
            if a != 1:
                prime_list[n] += 1
                l.append(a)
    if set([0, 1]) != set(prime_list):
        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: Wrong Answer

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 list(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)
        if tmp != 1:
            l.append(tmp)
        if l == []:
            if n != 1:
                l.append(n)
        return 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)
    # 素数列挙
    num = 10**6+1
    primes = prime_set(num)
    # 全部素因数分解
    prime_list = [0] * (num+1)
    pairwise_f = True
    ll = list()
    for a in A:
        l = []
        tmp = a
        nsq = int(a ** 0.5 + 0.5) + 1
        for i in primes:
            if  i > nsq: 
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                prime_list[i] += 1
                l.append(i)
        if tmp != 1:
            prime_list[tmp] += 1
            l.append(tmp)
        if l == []:
            if a != 1:
                prime_list[n] += 1
                l.append(a)
    if set([0, 1]) != set(prime_list):
        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: Wrong Answer

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 list(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)
        if tmp != 1:
            l.append(tmp)
        if l == []:
            if n != 1:
                l.append(n)
        return 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)
    # 素数列挙
    num = 10**6+1
    primes = prime_set(num)
    # 全部素因数分解
    prime_list = [0] * (num+1)
    pairwise_f = True
    ll = list()
    for a in A:
        l = []
        tmp = a
        nsq = int(n ** 0.5 + 0.5) + 1
        for i in primes:
            if  i > nsq: 
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                prime_list[i] += 1
                l.append(i)
        if tmp != 1:
            prime_list[tmp] += 1
            l.append(tmp)
        if l == []:
            if n != 1:
                prime_list[n] += 1
                l.append(n)
    if set([0, 1]) != set(prime_list):
        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: Wrong Answer

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 list(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)
        if tmp != 1:
            l.append(tmp)
        if l == []:
            if n != 1:
                l.append(n)
        return 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)
    # 素数列挙
    num = 10**6+1
    primes = prime_set(num)
    # 全部素因数分解
    prime_list = [0] * (num+1)
    pairwise_f = True
    ll = list()
    for a in A:
        l = []
        tmp = a
        nsq = int(n ** 0.5 + 0.5) + 1
        for i in primes:
            if  i > nsq: 
                break 
            if tmp%i == 0:
                while tmp%i == 0:
                    tmp //= i
                prime_list[i] += 1
                l.append(i)
                if prime_list[i] > 1:
                    pairwise_f = False
        if tmp != 1:
                prime_list[tmp] += 1
                l.append(tmp)
                if prime_list[tmp] > 1:
                    pairwise_f = False  
        if l == []:
            if n != 1:
                prime_list[n] += 1
                l.append(n)
                if prime_list[n] > 1:
                    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: Wrong Answer

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:]:
        if len(af & factorization(a, primes)) == 0:
            continue
        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: Wrong Answer

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:]:
        if len(af & factorization(a, primes)) == 0:
            continue
        else:
            pairwise_f = False
            break
    if pairwise_f:
        print('pairwise coprime')
    else:
        if g == 1:
            print('setwise coprime')
        else:
            print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import chain
def main():
  
    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
    for a in A:
        if a == A[0]:
            af = factorization(a, primes)
        else:
            if len(af & factorization(a, primes)) == 0:
                continue
            else:
                pairwise_f = False
                break
    if pairwise_f:
        print('pairwise coprime')
    else:
        if g == 1:
            print('setwise coprime')
        else:
            print('not coprime')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 p[j]==2:
            f=1
            break
    if 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: Wrong Answer

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 p[i]==2:
            f=1
            break
    if 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")