< uruneaさんのAI生成コード置き場

エラトステネスの篩

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

def sieve_of_eratosthenes(n):
    if n < 2:
        return []

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

    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False

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

    return primes


Q = int(input())
prime_list = sieve_of_eratosthenes(Q)
print(len(prime_list))
for i in prime_list:
    print(i, end=" ")