AtCoder Beginner Contest 215 D - Coprime 2【Python】

https://atcoder.jp/contests/abc215/tasks/abc215_d

AtCoder ProblemsでDifficulty: 736、Solve Probability: 35%でした。

正数列Aを素因数分解して各素因数を一つの集合に管理し、エラトステネスのふるいを少し変えて各素因数の倍数であるものをふるい落としていくようにしたところ解くことができました。
algo-method.com

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

res = set()
def prime_factorize(N):

    # √N まで試し割っていく
    for p in range(2, N):
        # p * p <= N の範囲でよい
        if p * p > N:
            break

        # N が p で割り切れないならばスキップ
        if N % p != 0:
            continue

        # N の素因数 p に対する指数を求める
        e = 0
        while N % p == 0:

            # N を p で割る
            N //= p

        # 答えに追加
        res.add(p)

    # 素数が最後に残ることがありうる
    if N != 1:
        res.add(N)

for i in range(N):
    prime_factorize(A[i])

def edit_Eratosthenes(N):
    # テーブル
    isprime = [True] * (N+1)

    # 0を予めふるい落としておく
    isprime[0] = False

    # ふるい　pはAの各素因数
    for p in sorted(list(res)):
        # すでにp の倍数であるものはスキップする
        if not isprime[p]:
            continue

        # p の倍数からラベルを剥奪
        q = p# * 2
        while q <= N:
            isprime[q] = False
            q += p

    return isprime

res2 = edit_Eratosthenes(10**5)

print(sum(res2[:M+1]))
for i in range(1, M + 1):
    if res2[i]:
        print(i)