問題: エラトステネスのふるい (Python)

エラトステネスのふるい (Python)

問題

整数 n を入力として受け取り、エラトステネスのふるいを使って n 以下の素数をすべて求めてください。素数の個数と、素数を小さい順に空白区切りで表示します。

入力例

出力例

50以下の素数は15個あります
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

残り時間: 00:00

速度: 0 文字/分

参照コード

コピーはできません。自分でタイピングしてください。

def sieve(n):
    """エラトステネスのふるいで n 以下の素数を求める"""
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= n:
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
        i += 1
    return [k for k in range(n + 1) if is_prime[k]]

def main():
    n = int(input())
    primes = sieve(n)
    print(f"{n}以下の素数は{len(primes)}個あります")
    print(" ".join(map(str, primes)))

if __name__ == "__main__":
    main()

エラトステネスのふるい (Python)

問題

入力例

出力例

参照コード

入力エリア