ABC 177 E - Coprime

整数からなる配列が与えられたとき，「どの2つをとっても互いに素」になっているかを判定する．

atcoder.jp

解説

まず，各 $a = 2, 3, \ldots $ について，配列内に $a$ の倍数が何個あるかを調べる．どの $a$ についても $a$ の倍数が $2$ 個以上存在しないなら，どの $2$ つをとっても互いに素である．また，配列の大きさ $n$ に対して，どの $a$ についても $a$ の倍数が $n$ 個未満なら，配列全体の最大公約数は $1$ である．

実装

sum(C[a::a]) で $a$ から $a$ 個とばしに和をとれる．

Submission #16397508 - AtCoder Beginner Contest 177

n = int(input())
*A, = map(int, input().split())
m = max(A)
C = [0 for a in range(m + 1)]
for a in A:
    C[a] += 1
s = 0
for a in range(2, m + 1):
    s = max(s, sum(C[a::a]))
if s < 2:
    print('pairwise coprime')
elif s < n:
    print('setwise coprime')
else:
    print('not coprime')