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 math

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

def gen_primes(limit):
    p = [] # それまでに生成した素数
    for i in range(2, limit+1):
        if i == 2 or all([i%j != 0 for j in p if j <= int(i**.5)]):
            p.append(i)
            yield i

for p in gen_primes(int(max(a)**.5)):
    if sum([i%p == 0 for i in a]) >= 2:
        break
else:
    print('pairwise coprime')
    exit()

gcd = a[0]
for i in a[1:]:
    gcd = math.gcd(gcd, i)
    if gcd == 1:
        print('setwise coprime')
        break
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

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

def gen_primes(limit):
    p = [] # それまでに生成した素数
    for i in range(2, limit+1):
        if i == 2 or all([i%j != 0 for j in p if j <= int(i**.5)]):
            p.append(i)
            yield i

factors = []
gcd = a[0]
for A in a:
    for p in gen_primes(int(A**.5)):
        if A%p == 0:
            factors.append(p)
            break
    else:
        factors.append(A)
    gcd = math.gcd(gcd, A)

if len(factors) == len(set(factors)):
    print('pairwise coprime')
elif gcd == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

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

def gen_primes(limit):
    p = [] # それまでに生成した素数
    for i in range(2, limit+1):
        if i == 2 or all([i%j != 0 for j in p if j <= int(i**.5)]):
            p.append(i)
            yield i

factors = []
gcd = a[0]
for A in a:
    for p in gen_primes(int(max(a)**.5)):
        if A%p == 0:
            factors.append(p)
            break
    else:
        factors.append(A)
    gcd = math.gcd(gcd, A)

if len(factors) == len(set(factors)):
    print('pairwise coprime')
elif gcd == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

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

def gen_primes(limit):
    prime_table = [True] * (limit + 1)
    prime_table[0] = False
    prime_table[1] = False
    for i in range(2, int(limit**.5)+1):
        prime_table[i+i::i] = [False] * (limit//i-1)
    return prime_table

primes = gen_primes(int((10**6)**.5))
factors = []
gcd = a[0]
for A in a:
    for i,p in enumerate(primes[2:], 2):
        if p and A%i == 0:
            factors.append(i)
            break
    else:
        factors.append(A)
    gcd = math.gcd(gcd, A)

if len(factors) == len(set(factors)):
    print('pairwise coprime')
elif gcd == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

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

f1 = True
f2 = True

c = [0] * (10**6+5)
for a in A:
  c[a] = 1
for i in range(2, 10**6+5):
  cnt = 0
  for j in range(i, 10**6+5, i):
    cnt += c[j]
  if cnt > 1:
    f1 = False


g = 0
for i in range(len(A)):
  g = gcd(g, A[i])
if g != 1:
  f2 = False

if f1:
  print("pairwise coprime")
elif f2:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

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

f1 = True
f2 = True

c = [0] * (10**6+5)
for a in A:
  c[a] = 1
for i in range(2, 10**6+5):
  cnt = 0
  for j in range(i, 10**6+5, i):
    cnt += c[j]
  if cnt > 1:
    f1 = False


g = 1
for i in range(len(A)):
  g = gcd(g, A[i])
if g != 1:
  f2 = False

if f1:
  print("pairwise coprime")
elif f2:
  print("setwise coprime")
else:
  print("not coprime")

Submission status: Wrong Answer

Solution code:
from math import gcd
from functools import reduce

n = int(input())
A = list(map(int, input().split()))
res = ['pairwise coprime', 'setwise coprime', 'not coprime']

MAX = 10 ** 6 + 1000
dp = [i for i in range(MAX)]
# dp[x]はxを割り切る最小の素数
print(dp[:10])
for x in range(2, MAX):
    if dp[x] < x: continue
    for y in range(x + x, MAX, x):
        if dp[y] == y:
            dp[y] = x

def get_factor(n):
    factors = []
    while n > 1:
        factors.append(dp[n])
        n //= dp[n]
    return factors

prime_factors = []
for a in A:
    factor = get_factor(a)
    factor_set = list(set(factor))
    prime_factors.extend(factor_set)

if len(prime_factors) == len(set(prime_factors)):
    print(res[0])
elif reduce(gcd, A) == 1:
    print(res[1])
else:
    print(res[2])

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

A_max = max(A)
prime = [[] for _ in range(A_max + 1)]
for i in range(2,A_max + 1):
    if prime[i] == []:
        n = i
        while n <= A_max:
            prime[n].append(i)
            n += i

li = [0] * (A_max + 1)
for a in A:
    for p in prime[a]:
        li[p] += 1

if max(li) == 1:
    print('pairwise coprime')
elif max(li) == N:
    print('not coprime')
else:
    print('setwise coprime')

Submission status: Wrong Answer

Solution code:
from math import gcd
def lcm(a,b):
    return a*b//gcd(a,b)

def main():
    n = int(input())
    A = list(map(int,input().split()))
    LCM = 1
    GCD = A[-1]
    flag = True
    for a in A[::-1]:
        if gcd(LCM,a) > 1:
            flag = False
            break
        LCM = lcm(LCM,a)
        GCD = gcd(GCD,a)
    if flag:
        print("pairwise coprime")
    elif GCD == 1:
        print("setwise coprime")
    else:
        print("not coprime")
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd

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

num = 10 ** 6
is_prime = [0] * (num + 1)
is_prime[0] = 1
is_prime[1] = 1

for i in range(2, num + 1):
    if is_prime[i] != 0:
        continue

    cnt = 2
    while i * cnt <= num:
        is_prime[i * cnt] += 1
        cnt += 1


pairwise = True
for a in A:
    if is_prime[a] > 1:
        pairwise = False
        break

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

if pairwise:
    print('pairwise coprime')
elif g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import gcd

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

num = 10 ** 1
is_prime = [True] * (num + 1)
is_prime[0] = False
is_prime[1] = False

for i in range(2, num + 1):
    if not is_prime[i]:
        continue

    cnt = 2
    while i * cnt <= num:
        is_prime[i * cnt] = False
        cnt += 1

primes = [i for i, p in enumerate(is_prime) if p]

pairwise = True
for p in primes:
    cnt = 0
    for a in A:
        if a % p == 0:
            cnt += 1

    if cnt > 1:
        pairwise = False
        break

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

if pairwise:
    print('pairwise coprime')
elif g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

def eratosthenes():
    erat = [0 for _ in range(max_a+1)]
    lim = int(math.sqrt(max_a))
    pair = True
    for i in range(2, lim+1):
        cnt = 0
        if not erat[i]:
            for res in range(i, max_a+1, i):
                if res in set_a:
                    cnt += 1
                erat[res] = i
                if cnt > 1:
                    pair = False
                    break
        if not pair:
            break
    return pair


n = int(input())
a = [int(x) for x in input().split()]
max_a = max(a)
set_a = set(a)

if eratosthenes() and len(set_a) == n - max(0, a.count(1)-1):
    print('pairwise coprime')
else:
    res = a[0]
    for i in range(n):
        res = math.gcd(res, a[i])
    if res == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

def eratosthenes():
    erat = [0 for _ in range(max_a+1)]
    lim = int(math.sqrt(max_a))
    pair = True
    for i in range(2, lim+1):
        cnt = 0
        if not erat[i]:
            for res in range(i, max_a+1, i):
                if res in set_a:
                    cnt += 1
                erat[res] = i
                if cnt > 1:
                    pair = False
                    break
        if not pair:
            break
    return pair


n = int(input())
a = [int(x) for x in input().split()]
max_a = max(a)
set_a = set(a)

if eratosthenes() and len(set_a) == n - (a.count(1)-1):
    print('pairwise coprime')
else:
    res = a[0]
    for i in range(n):
        res = math.gcd(res, a[i])
    if res == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

def eratosthenes():
    erat = [0 for _ in range(max_a+1)]
    lim = int(math.sqrt(max_a))
    pair = True
    for i in range(2, lim+1):
        cnt = 0
        if not erat[i]:
            for res in range(i, max_a+1, i):
                if res in set_a:
                    cnt += 1
                erat[i] = i
                if cnt > 1:
                    pair = False
                    break
        if not pair:
            break
    return pair


n = int(input())
a = [int(x) for x in input().split()]
max_a = max(a)
set_a = set(a)

if eratosthenes() and len(set_a) == n:
    print('pairwise coprime')
else:
    res = a[0]
    for i in range(n):
        res = math.gcd(res, a[i])
    if res == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

def eratosthenes():
    erat = [0 for _ in range(max(a)+1)]
    cnt = {1: 1}
    lim = int(math.sqrt(max(set_a)))
    for i in range(2, lim+1):
        if not erat[i]:
            for res in range(i, max(set_a)+1, i):
                if res in set_a:
                    cnt[res] = cnt.get(res, 0) + 1
                erat[i] = i
    return cnt


n = int(input())
a = [int(x) for x in input().split()]
set_a = set(a)

ans = eratosthenes()

if max(ans.values()) == 1 and len(set_a) == n:
    print('pairwise coprime')
else:
    res = a[0]
    for i in range(n):
        res = math.gcd(res, a[i])
    if res == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

def eratosthenes():
    cnt = {1: 1}
    lim = int(math.sqrt(max(set_a)))
    for i in range(2, lim+1):
        for res in range(i, max(set_a)+1, i):
            if res in set_a:
                cnt[res] = cnt.get(res, 0) + 1
    return cnt


n = int(input())
a = [int(x) for x in input().split()]
set_a = set(a)

ans = eratosthenes()

if max(ans.values()) == 1 and len(set_a) == n:
    print('pairwise coprime')
else:
    res = a[0]
    for i in range(n):
        res = math.gcd(res, a[i])
    if res == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

def eratosthenes():
    erat = [0 for _ in range(max(a)+1)]
    lim = int(math.sqrt(max(a)))
    for i in range(2, lim+1):
        res = i
        while res <= max(a):
            if erat[res] == 0:
                erat[res] = i
            res += i
    for i in range(max(a)+1):
        if erat[i] == 0:
            erat[i] = i
    return erat        

n = int(input())
a = [int(x) for x in input().split()]

erat = eratosthenes()
cnt = dict()
for i in range(n):
    cnt[erat[a[i]]] = cnt.get(erat[a[i]], 0) + 1

if max(cnt.values()) == 1:
    print('pairwise coprime')
else:
    res = a[0]
    for i in range(1, n):
        res = math.gcd(res, a[i])
    if res == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

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

def soinsuu(n):
    visited=defaultdict(int)
    for i in range(2,round(n**.5)+1):
        while n%i==0:
            n//=i
            visited[i]+=1
    if n>1:
        visited[n]+=1
    return(visited)

N=int(input())
A=list(map(int,input().split()))
visited=set()
flg=False
for a in A:
    for i in soinsuu(a):
        if i in visited:
            flg=True
            break
        else:
            visited.add(i)

    if flg:
        break
else:
    print("pairwise coprime")
    exit()

visited=soinsuu(A[0])
for a in A[1:]:
    data=soinsuu(a)
    for i in data:
        visited[i]-=data[i]

if [i for i in visited if visited[i]>0]:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

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

def soinsuu_set(n):

    visited=set()
    for i in range(2,round(n**.5)+1):
        if n%i==0:
            visited.add(i)
        while n%i==0:
            n//=i
    if n>1:
        visited.add(n)
    return(visited)



N=int(input())

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

visited=set()
flg=False
for a in A:
    for i in soinsuu_set(a):
        if i in visited:
            flg=True
            break
        else:
            visited.add(i)

    if flg:
        break
else:
    print("pairwise coprime")
    exit()

visited=soinsuu_set(A[0])
for a in A[1:]:
    for i in soinsuu_set(a):
        if i in visited:
            visited.remove(i)
if visited:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

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


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append(i)

    if temp != 1:
        arr.append(temp)

    if arr == []:
        arr.append(n)

    return set(arr)


def gcd(*numbers):
    return reduce(math.gcd, numbers)


def main():
    N = int(input())
    As = list(map(int, input().split()))
    As = np.array(As)

    ans = 'not coprime'

    if gcd(*As) == 1:
        ans = 'pairwise coprime'
        for i in range(N - 1):
            Ai = factorization(As[i])
            for j in range(i + 1, N):
                Aj = factorization(As[j])
                judge = Ai & Aj
                if judge != set():
                    ans = 'setwise coprime'
                    break
            else:
                continue

            break

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append(i)

    if temp != 1:
        arr.append(temp)

    if arr == []:
        arr.append(n)

    return set(arr)


def gcd(*numbers):
    return reduce(math.gcd, numbers)


def main():
    N = int(input())
    As = list(map(int, input().split()))
    As = np.array(As)

    ans = 'pairwise coprime'

    for i in range(N - 1):
        Ai = factorization(As[i])
        for j in range(i + 1, N):
            Aj = factorization(As[j])
            judge = Ai & Aj
            if judge != set():
                ans = 'setwise coprime'
                break
        else:
            continue

        break

    if (ans == 'setwise coprime') and (gcd(*As) != 1):
        ans = 'not coprime'

    print(ans)
    return





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd

# test1 = gcd(40, 20, 1)
# test2 = gcd(60, 40, 1)
# test3 = gcd(50, 3, 1)

# print(test1, test2, test3)

def f(n, ais):
    common_divisor = ais[0]
    for (i, ai) in enumerate(ais):
        common_divisor = gcd(ai, common_divisor)
        for (j, aj) in enumerate(ais[i+1:]):
            if gcd(ai, aj) != 1:
                for aiu in ais[i+1:]:
                    common_divisor = gcd(aiu, common_divisor)
                if common_divisor == 1:
                    return 'setwise coprime'
                else:
                    return 'not coprime'
        # print(common_divisor)
    return 'pairwise coprime'

def make_prime_list():
    l = [2]
    for i in range(3, 100, 2):
        for j in l:
            if i % j == 0:
                break;
        else:
            l.append(i)
    return l;

def find_prime(n, l):
    result = set()
    for p in l:
        if n % p == 0:
            result.add(p)
            while n % p == 0:
                n = n // p
        if p >= n:
            return result
    return result

# l = make_prime_list()
# print(find_prime(60, l))
# print(find_prime(1, l))
# print(find_prime(7, l))

def f(n, ais):
    prime_list = make_prime_list()
    koremadenosoinsuu = set()
    koremadenogcd = ais[0]
    pairwise_coprime = True
    for ai in ais:
        if pairwise_coprime:
            ai_factors = find_prime(ai, prime_list)
            if not ai_factors.isdisjoint(koremadenosoinsuu):
                pairwise_coprime = False
            koremadenosoinsuu = koremadenosoinsuu.union(ai_factors)
        koremadenogcd = gcd(koremadenogcd, ai)
    if pairwise_coprime:
        return 'pairwise coprime'
    elif koremadenogcd == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'

# def test(n, ais, r):
#     result = f(n, ais)
#     print('{} n={}, ais={}, result={}'.format(result == r, n, ais, result))

# r1 = 'pairwise coprime'
# r2 = 'setwise coprime'
# r3 = 'not coprime'

# test(2, [6, 6], r3)
# test(3, [4, 7, 3], r1)
# test(3, [2, 3, 4], r2)
# test(3, [2, 4, 6], r3)

# test(3, [3, 4, 5], r1)
# test(3, [6, 10, 15], r2)
# test(3, [6, 10, 16], r3)

# test(2, [100, 1], r1)
# test(3, [8, 1, 800], r2)
# test(3, [1, 1, 1], r1)
# test(4, [2, 3, 5, 7], r1)
# test(4, [2, 3, 5, 10], r2)

# test(3, [100, 10, 1], r2)

# test(3, [1000000, 777777, 11], r2)

n = int(input())
ais = list(map(int, input().split(' ')))
print(f(n, ais))

Submission status: Wrong Answer

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

M = 10**6
P = [0]*(M+1)
for i in range(2, M+1):
    if P[i] == 1:
        continue
    P[i] = -1
    j = 2*i
    while j <= M:
        P[j] = 1
        j += i

L = [0]*(M+1)
for a in A:
    L[a] += 1

num = 0
for i in range(2, M+1):
    if P[i] > -1:
        continue
    cnt = 0
    j = i
    while j <= M:
        cnt += L[j]
        j += i
    num = max(num, cnt)


if num == 1:
    print("pairwise coprime")
elif num == N:
    print("not coprime")
else:
    print("setwise coprime")

Submission status: Wrong Answer

Solution code:
from sys import stdin

input = stdin.readline
import math

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

    cur = 0
    for i in a:
        cur = math.gcd(i, cur)
    if cur > 1:
        print('not coprime')
        return
    m = max(a)
    prime = [True] * (m+1)
    c = {}
    for i in a:
        c[i] = c.get(i,0) + 1
    for i in range(2,math.ceil(m**0.5)+1):
        if prime[i]:
            cnt = 0
            for j in range(i,m+1,i):
                prime[j] = False
                cnt += c.get(j,0)
                if cnt > 1:
                    print('setwise coprime')
                    return
    print('pairwise coprime')
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

# エラトステネスの篩
#############################################################
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
#############################################################

# 素因数分解、リストで返す
#############################################################
def prime_factorize(n, prime_list):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f in prime_list and f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a.sort()
    return a
#############################################################

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

data = set(get_sieve_of_eratosthenes(10**6))

primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i], data)
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

# print(primes)

if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Wrong Answer

Solution code:
from sys import stdin

input = stdin.readline
import math

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

    cur = 0
    for i in a:
        cur = math.gcd(i, cur)
    if cur != 1:
        print('not coprime')
        return
    m = max(a)
    prime = [True] * (m+1)
    c = {}
    for i in a:
        c[i] = c.get(i,0) + 1
    for i in range(2,math.ceil(m**0.5)+1):
        if prime[i]:
            cnt = 0
            for j in range(i,m+1,i):
                prime[j] = False
                cnt += c.get(j,0)
                if cnt > 1:
                    print('setwise coprime')
                    return
    print('pairwise coprime')

solve()

Submission status: Wrong Answer

Solution code:
from sys import stdin

input = stdin.readline
import math

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

    cur = 0
    for i in a:
        cur = math.gcd(i, cur)
    if cur != 1:
        print('not coprime')
        return
    m = max(a)
    prime = [True] * (m+1)
    c = {}
    for i in a:
        c[i] = c.get(i,0) + 1

    for i in range(2,m+1):
        if prime[i]:
            cnt = 0
            for j in range(i*i,m+1,i):
                prime[j] = False
                cnt += c.get(j,0)
                if cnt > 1:
                    print('setwise coprime')
                    return
    print('pairwise coprime')

solve()

Submission status: Wrong Answer

Solution code:
from sys import stdin

input = stdin.readline
import math

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

    cur = 0
    for i in a:
        cur = math.gcd(i, cur)
    if cur != 1:
        print('not coprime')
        return
    m = max(a)
    prime = [True] * (m+1)
    c = {}
    for i in a:
        c[i] = c.get(i,0) + 1

    for i in range(2,math.ceil(m**0.5)+1):
        if prime[i]:
            cnt = 0
            for j in range(i*i,m+1,i):
                prime[j] = False
                cnt += c.get(j,0)
                if cnt > 1:
                    print('setwise coprime')
                    return
    print('pairwise coprime')

solve()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import accumulate

input = stdin.readline
from collections import Counter
import math

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

    cur = 0
    for i in a:
        cur = math.gcd(i, cur)
    if cur != 1:
        print('not coprime')
        return
    m = max(a)
    prime = [True] * (m+1)
    c = {i:1 for i in a}
    for i in range(2,math.ceil(m**0.5)+1):
        if prime[i]:
            cnt = 0
            for j in range(i*i,m+1,i):
                prime[j] = False
                cnt += c.get(j,0)
                if cnt > 1:
                    print('setwise coprime')
                    return
    print('pairwise coprime')

solve()

Submission status: Wrong Answer

Solution code:
from math import sqrt
from math import ceil
def mpfli(N): #minimum prime factor listのこと
    li = [i for i in range(N+1)]
    li2 = [i for i in range(N+1)]
    for i in range(2,ceil(sqrt(N+1))):
        for j in range(2*i, N + 1):
            if li[j]== li2[j]:
                if li[j] % li[i] == 0:
                    li[j] = li[i]
    return li


def pfac(n): #mpf = mpfli(N+1)
    S = set()
    while n != 1:
        m = mpf[n]
        S = S.union({m})
        n = n // m
    return S


def pairwise_coprime(A):
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            if pfac(A[i]) & pfac(A[j]) != {}:
                return False
            else:
                return True


def setwise_coprime(A):
    S = pfac(A[0])
    for i in range(1, len(A)):
        S = S & pfac(A[i])
    if S != {}:
        return False
    else:
        return True


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


N = int(input())
A = list(map(int, input().split()))
mpf = mpfli(max(A[n] for n in range(len(A))))


main()

Submission status: Wrong Answer

Solution code:
from math import sqrt
from math import ceil
def mpfli(N): #minimum prime factor listのこと
    li = [i for i in range(N+1)]
    li2 = [i for i in range(N+1)]
    for i in range(2,ceil(sqrt(N+1))):
        for j in range(2*i, N + 1):
            if li[j]== li2[j]:
                if li[j] % li[i] == 0:
                    li[j] = li[i]
    return li


def pfac(n): #高速素因数集合。 先に mpfli(N)がmpfとして与えられているという前提のコード
    S = set()
    while n != 1:
        m = mpf[n]
        S = S.union({m})
        n = n // m
    return S


def paerwise_coprime(A):
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            if pfac(A[i]) & pfac(A[j]) != {}:
                return False
            else:
                return True


def setwise_coprime(A):
    S = pfac(A[0])
    for i in range(1, len(A)):
        S = S & pfac(A[i])
    if S != {}:
        return False
    else:
        return True


def main():
    mpf = mpfli(10**6+1)
    N = input()
    A = list(map(int, input().split()))
    if pairwise_coprime(A):
        print('pairwise coprime')
    elif setwise_coprime(A):
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Wrong Answer

Solution code:
import math

def gcd_list(nums):
  gcd = nums[0]
  for i in range(1,len(nums)):
    gcd = math.gcd(gcd,nums[i])
  return gcd

def prime_fact(N):
  M = N
  primes = []
  K = 2

  while K*K <= M:
    while N%K == 0:
      primes.append(K)
      N = N//K
    K += 1
  
  if N != 1:
    primes.append(N)

  return primes

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

if gcd_list(A) != 1:
  print("not coprime")
  
else:
  primes = set(prime_fact(A[0]))
  ans = "pairwise coprime"
  for i in range(1,N):
    for j in list(primes):
      if A[i]%j == 0:
        ans = "setwise coprime"
        break
        break
  print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 07:10:00 2020

@author: liang
"""


# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

"""
コーナーケース１:
    重複があるとき　not coprime
    ただし、1の重複は除く
"""
import math
C = 10**6
N = int(input())
judge = [False]*(C+1)
A = [int(x) for x in input().split()]

f = False
for a in A:
    if judge[a] == True and a != 1:
        f = True
    judge[int(a)]=True


#print(judge[:10])
def solve(f):
    
    ans = A[0]
    #線形探索 O(N)
    for i in range(N):
        ans = math.gcd(ans,A[i])
    #print("ans",a)
    if ans != 1:
        return "not coprime"
    
    #重複時
    if f:
        return "not coprime"
    flag = True
    #エラトステネスの篩 O(N log N)
    for i in range(2,C+1):
        count = 0
       #if d[i] == True:
        for j in range(i,C+1,i):
            if judge[j] == True:
                count += 1
            if count == 2:
                flag = False
                break
        #        d[j] = False
        if not flag:
            break
    
    if flag == True:
        return "pairwise coprime"
    
    return "setwise coprime"

print(solve(f))
#print(len(A))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

"""
コーナーケース１:
    重複があるとき　not coprime
    ただし、1の重複は除く
"""
import math
C = 10**6
#T = int(math.sqrt(C)*10**3)+1
N = int(input())
judge = [0]+[False]*C
A =list()
f = False
for a in input().split():
    if judge[int(a)] == True and int(a) != 1:
        f = True
    judge[int(a)]=True
    A.append(int(a))
#d = [False]+[True]*C

#print(judge[:10])
def solve(f):
    #重複時
    if f:
        return "not coprime"
    flag = True
    #エラトステネスの篩 O(N log N)
    for i in range(2,C+1):
        count = 0
       #if d[i] == True:
        for j in range(i,C+1,i):
            if judge[j] == True:
                count += 1
            if count == 2:
                flag = False
                break
        #        d[j] = False
        if not flag:
            break
    
    if flag == True:
        return "pairwise coprime"
    ans = A[0]
    #線形探索 O(N)
    for i in range(N):
        ans = math.gcd(ans,A[i])
    #print("ans",a)
    if ans == 1:
        return "setwise coprime"
    return "not coprime"

print(solve(f))
#print(len(A))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 18 00:26:07 2020

@author: liang
"""

"""
コーナーケース１:
    重複があるとき　not coprime
    ただし、1の重複は除く
"""
import math
C = 10**6
#T = int(math.sqrt(C)*10**3)+1
N = int(input())
judge = [0]+[False]*C
A =list()
f = False
for a in input().split():
    if judge[int(a)] == True and int(a) != 1:
        f = True
    judge[int(a)]=True
    A.append(int(a))
d = [False]+[True]*C

#print(judge[:10])
def solve(f):
    #重複時
    if f:
        return "not coprime"
    flag = True
    #エラトステネスの篩 O(N log N)
    for i in range(2,C+1):
        count = 0
        if d[i] == True:
            for j in range(i,C+1,i):
                if judge[j] == True:
                    count += 1
                if count == 2:
                    flag = False
                    break
                d[j] = False
        if not flag:
            break
    
    if flag == True:
        return "pairwise coprime"
    ans = A[0]
    #線形探索 O(N)
    for i in range(N):
        ans = math.gcd(ans,A[i])
    if ans == 1:
        return "setwise coprime"
    return "not coprime"

print(solve(f))