AtCoder-ABC215 D - Coprime 2【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210821233817p:plain

AtCoder Beginner Contest215のD問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 215 - AtCoder

AtCoder Beginner Contest215 D - Coprime 2

D - Coprime 2

問題文

長さ N の正整数列 A=(A1,A2,…,AN) が与えられるので、以下の条件を満たす 1 以上 M 以下の整数 k を全て求めてください。

全ての 1≤i≤N を満たす整数 i について、 gcd(Ai,k)=1 である。

制約

・入力は全て整数
・1 ≤ N,M ≤ 10^5
・1 ≤ Ai ≤ 10^5

解答例

# 約数をdivに加える
def make_divisors(n):
    i = 1
    while i*i <= n:
        if n % i == 0:
            div.add(i)
            if i != n // i:
                div.add(n//i)
        i += 1
    return


N, M = map(int,input().split())

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

# 約数列挙
div = set()

# Aiの約数を求める
for i in range(N):
    make_divisors(A[i])

# set型divから配列ansへ変換
Div = list(div)

# 答えの配列(1~M)
res = [True for i in range(M)]

# 約数の倍数をFalseに
for i in range(len(Div)):
    # Div[i]が1ならスキップ
    if Div[i] == 1:
        continue
    k = 1
    while Div[i] * k <= M:
        res[Div[i] * k - 1] = False
        k += 1

# 解答の配列(1は加えておく)
ans = [1]
for k in range(1,M):
    # resがTrueならINDEXをansに追加
    if res[k]:
        ans.append(k+1)

#答えの数と値を出力
print(len(ans))
for i in range(len(ans)):
    print(ans[i])